A new placement heuristic for the orthogonal stock-cutting problem

• 成果类型: Article
• 署名作者: Burke, EK; Kendall, G; Whitwell, G
• 署名单位: University of Nottingham
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1040.0109
• 发表日期: 2004
• 页码: 655-671
• 关键词: production/scheduling : cutting stock/trim; production/scheduling : approximations/heuristic; computers/computer science : artificial intelligence

摘要

This paper presents a new best-fit heuristic for the two-dimensional rectangular stock-cutting problem and demonstrates its effectiveness by comparing it against other published approaches. A placement algorithm usually takes a list of shapes, sorted by some property such as increasing height or decreasing area, and then applies a placement rule to each of these shapes in turn. The proposed method is not restricted to the first shape encountered but may dynamically search the list for better candidate shapes for placement. We suggest an efficient implementation of our heuristic and show that it compares favourably to other heuristic and metaheuristic approaches from the literature in terms of both solution quality and execution time. We also present data for new problem instances to encourage further research and greater comparison between this and future methods.