A new placement heuristic for the orthogonal stock-cutting problem

摘要

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.