G-88-12
A Two-Phase Heuristic for Two Dimentional Cutting-Stock Problem
, , , and BibTeX reference
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. We 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.
Published April 1988 , 20 pages
This cahier was revised in February 1990