Journal article
Multi-dimensional Bin Packing Problems with Guillotine Constraints
The problem addressed in this paper is the decision problem of determining if a set of multi-dimensional rectangular boxes can be orthogonally packed into a rectangular bin while satisfying the requirement that the packing should be guillotine cuttable. That is, there should exist a series of face parallel straight cuts that can recursively cut the bin into pieces so that each piece contains a box and no box has been intersected by a cut.
The unrestricted problem is known to be NP-hard. In this paper we present a generalization of a constructive algorithm for the multi-dimensional bin packing problem, with and without the guillotine constraint, based on constraint programming.
Language: | English |
---|---|
Year: | 2010 |
Pages: | 1999-2006 |
ISSN: | 1873765x and 03050548 |
Types: | Journal article |
DOI: | 10.1016/j.cor.2010.01.017 |
ORCIDs: | Pisinger, David |