Article ID: | iaor19912065 |
Country: | United Kingdom |
Volume: | 42 |
Issue: | 1 |
Start Page Number: | 39 |
End Page Number: | 47 |
Publication Date: | Jan 1991 |
Journal: | Journal of the Operational Research Society |
Authors: | Loulou R., Soumis F., Chauny F., Sadones S. |
The two-dimensional cutting-stock problem consists of laying out a specified list of rectangular pieces on rectangular sheets, in such a way as to minimize the number of sheets used. A pattern is a combination of piece widths whose sum does not exceed the sheet’s width. The authors present a new heuristic algorithm for this problem based on an approach with two phases: strategic phase and tactical phase. The first phase takes a global view of the problem and proposes a list of patterns to the second phase, which in turn is in charge of actually laying out these patterns on sheets. The strategic module relaxes the global problem to a one-dimensional cutting-stock problem and solves it using linear programming, while the tactical module is a recursive algorithm based on repeated knapsack operations and other heuristics.