Article ID: | iaor20115030 |
Volume: | 213 |
Issue: | 1 |
Start Page Number: | 52 |
End Page Number: | 65 |
Publication Date: | Aug 2011 |
Journal: | European Journal of Operational Research |
Authors: | Lewis R, Song X, Dowsland K, Thompson J |
Keywords: | programming: branch and bound, heuristics: local search |
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.