An exact approach to the Strip-Packing problem

An exact approach to the Strip-Packing problem

0.00 Avg rating0 Votes
Article ID: iaor2007393
Country: United States
Volume: 15
Issue: 3
Start Page Number: 310
End Page Number: 319
Publication Date: Jun 2003
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: cutting stock
Abstract:

We consider the problem of orthogonally packing a given set of rectangular items into a given strip, by minimizing the overall height of the packing. The problem is NP-hard in the strong sense, and finds several applications in cutting and packing. We propose a new relaxation that produces good lower bounds and gives information to obtain effective heuristic algorithms. These results are used in a branch-and-bound algorithm, which was able to solve test instances from the literature involving up to 200 items.

Reviews

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