A Two-phase Heuristic for the Two-dimensional Cutting-stock Problem
作者:
ChaunyFabien,
LoulouRichard,
SadonesSylvie,
SoumisFrançois,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1991)
卷期:
Volume 42,
issue 1
页码: 39-47
ISSN:0160-5682
年代: 1991
DOI:10.1057/jors.1991.5
出版商: Taylor&Francis
关键词: Two-Dimensional Layout;Cutting-Stock;Optimization;Nesting;Packing
数据来源: Taylor
摘要:
AbstractThe 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.
点击下载:
PDF (4498KB)
返 回