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

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

0.00 Avg rating0 Votes
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: , , ,
Keywords: programming: branch and bound, heuristics: local search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.