Multi-dimensional Bin Packing Problems with Guillotine Constraints

Publication: Research - peer-reviewJournal article – Annual report year: 2010

View graph of relations

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.
Original languageEnglish
JournalComputers & Operations Research
Publication date2010
Volume37
Issue11
Pages1999-2006
ISSN0305-0548
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 4

Keywords

  • constraint programming, packing, cutting
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 5163064