A new placement heuristic for the orthogonal stock-cutting problem
A new placement heuristic for the orthogonal stock-cutting problem
复制标题
DOI：
10.1287/opre.1040.0109
复制
发表时间：
2004-07-01
影响因子：
2.7
通讯作者：
Whitwell, G
中科院分区：
文献类型：
--
作者：
Burke, EK;Kendall, G;Whitwell, G
本文提出了一种新的最佳拟合启发式的二维矩形下料问题，并证明了其有效性，通过比较它与其他已发表的方法。放置算法通常采用一系列形状，按某种属性（如增加高度或减少面积）进行排序，然后依次对每个形状应用放置规则。所提出的方法不限于遇到的第一个形状，但可以动态地搜索更好的候选形状的放置列表。我们提出了一个有效的实现我们的启发式，并表明它相比，从文献中的解决方案的质量和执行时间方面的其他启发式和元启发式方法。我们还提供了新问题实例的数据，以鼓励进一步的研究和这种方法与未来方法之间的比较。
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.