Improved local search algorithms for the rectangle packing problem with general spatial costs
Improved local search algorithms for the rectangle packing problem with general spatial costs
复制标题
DOI：
10.1016/j.ejor.2004.02.020
复制
发表时间：
2004-05
期刊：
影响因子：
--
通讯作者：
S. Imahori;M. Yagiura;T. Ibaraki
中科院分区：
文献类型：
--
作者：
S. Imahori;M. Yagiura;T. Ibaraki
具有一般空间费用的矩形装箱问题是将给定的矩形在平面内无重叠地装箱，使得矩形的最大费用最小。这个问题是非常一般的，各种类型的包装问题和调度问题都可以用这种形式表示。对于这个问题，我们之前已经提出了使用一对矩形排列来表示解的局部搜索算法。在本文中，我们提出了加速技术，以评估解决方案在不同的街区。矩形装箱问题和实际调度问题的计算结果表明，所提出的技术具有良好的前景。
The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.