Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

An investigation into two bin packing problems with ordering and orientation implications

Lewis, Rhyd ORCID:, Song, Xiang ORCID:, Dowsland, Kathryn Anne and Thompson, Jonathan Mark 2011. An investigation into two bin packing problems with ordering and orientation implications. European Journal of Operational Research 213 (1) , pp. 52-65. 10.1016/j.ejor.2011.03.016

[thumbnail of Lewis,_R_Investigation_into_2_Bin_PackPaper.pdf]
PDF - Submitted Pre-Print Version
Download (941kB) | Preview


This paper considers variants of the one-dimensional bin packing (and stock cutting) problem in which both the ordering and orientation of items in a container influences the validity and quality of a solution. Two new real-world problems of this type are introduced, the first that involves the creation of wooden trapezoidal-shaped trusses for use in the roofing industry, the second that requires the cutting and scoring of rectangular pieces of cardboard in the construction of boxes. To tackle these problems, two variants of a local search-based approximation algorithm are proposed, the first that attempts to determine item ordering and orientation via simple heuristics, the second that employs more accurate but costly branch-and-bound procedures. We investigate the inevitable trade-off between speed and accuracy that occurs with these variants and highlight the circumstances under which each scheme is advantageous.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Uncontrolled Keywords: Packing; Cutting; Grouping problems; Local search; Heuristics
Publisher: Elsevier
ISSN: 0377-2217
Last Modified: 03 Nov 2023 07:27

Citation Data

Cited 13 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics