A two-phase heuristic for the two-dimensional cutting-stock problem

A two-phase heuristic for the two-dimensional cutting-stock problem

0.00 Avg rating0 Votes
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: , , ,
Abstract:

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.

Reviews

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