An exact method for the 2D guillotine strip packing problem

An exact method for the 2D guillotine strip packing problem

0.00 Avg rating0 Votes
Article ID: iaor20104149
Volume: 2009
Issue: 732010
Start Page Number: 1
End Page Number: 20
Publication Date: Jan 2009
Journal: Advances in Operations Research
Authors: ,
Abstract:

We consider the two-dimensional strip packing problem with guillotine cuts. The problem consists in packing a set of rectangular items on one strip of width W and infinite height. The items packed without overlapping must be extracted by a series of cuts that go from one edge to the opposite edge (guillotine constraint). To solve this problem, we use a dichotomic algorithm that uses a lower bound, an upper bound, and a feasibility test algorithm. The lower bound is based on solving a linear program by introducing new valid inequalities. A new heuristic is used to compute the upper bound. Computational results show that the dichotomic algorithm, using the new bounds, gives good results compared to existing methods.

Reviews

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