Groupe d’études et de recherche en analyse des décisions


A Two-Phase Heuristic for Two Dimentional Cutting-Stock Problem

, , et

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.

, 20 pages

Ce cahier a été révisé en février 1990