A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

0.00 Avg rating0 Votes
Article ID: iaor20091159
Country: United Kingdom
Volume: 35
Issue: 4
Start Page Number: 1281
End Page Number: 1291
Publication Date: Apr 2008
Journal: Computers and Operations Research
Authors: , , ,
Keywords: programming: branch and bound, heuristics
Abstract:

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.

Reviews

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