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, Song, Xiang, 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

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: 04 Jun 2017 02:22

Citation Data

Cited 11 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