Dynamic reduction heuristics for the rectangle packing area minimization problem
Dynamic reduction heuristics for the rectangle packing area minimization problem
复制标题
矩形堆积面积最小化问题的动态约简启发法
DOI：
10.1016/j.ejor.2014.09.042
复制
发表时间：
2015-03
影响因子：
6.4
通讯作者：
Li, Chumin
中科院分区：
文献类型：
--
作者：
He, Kun;Ji, Pengli;Li, Chumin
矩形布局面积最小化问题是VLSI布图规划中的一个关键子问题。这个问题将一组给定大小的轴对齐的二维矩形项放置到矩形平面上，使得没有两个项重叠，并且包络矩形的面积最小化。本文提出了一种动态约简算法，通过动态确定包络矩形的尺寸，将原问题的一个实例转化为矩形装箱问题的一系列实例。我们定义了一个损伤度来评估候选位置可能产生的负面影响，我们提出了一个最小的伤害第一的方法来解决矩形包装问题。接下来，我们采用了一种压缩方法，通过交替地向左和向下移动项目，使我们可以获得一个更小的包络矩形，从而压缩所得到的布局。我们还显示了可行性，紧凑性，非劣性，和停止性能的压缩方法。在11个MCNC和GSRC基准和文献中报道的28个实例上进行了全面的实验。实验结果表明，该算法具有较高的效率和有效性，特别是在大规模的数百个项目的实例。
The rectangle packing area minimization problem is a key sub-problem of floorplanning in VLSI design. This problem places a set of axis aligned two-dimensional rectangular items of given sizes onto a rectangular plane such that no two items overlap and the area of the enveloping rectangle is minimized. This paper presents a dynamic reduction algorithm that transforms an instance of the original problem to a series of instances of the rectangle packing problem by dynamically determining the dimensions of the enveloping rectangle. We define an injury degree to evaluate the possible negative impact for candidate placements, and we propose a least injury first approach for solving the rectangle packing problem. Next, we incorporate a compacting approach to compact the resulting layout by alternatively moving the items left and down toward a bottom-left corner such that we may obtain a smaller enveloping rectangle. We also show the feasibility, compactness, non-inferiority, and halting properties of the compacting approach. Comprehensive experiments were conducted on 11 MCNC and GSRC benchmarks and 28 instances reported in the literature. The experimental results show the high efficiency and effectiveness of the proposed dynamic reduction algorithm, especially on large-scale instances with hundreds of items.
登录
查看更多内容
DOI：
10.1016/j.ejor.2012.08.006
发表时间：
2013-02
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Andreas Bortfeldt
通讯作者：
Andreas Bortfeldt
DOI：
10.1109/tsmcb.2006.883268
发表时间：
2007-02
期刊：
IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
影响因子：
--
作者：
Maolin Tang;X. Yao
通讯作者：
Maolin Tang;X. Yao
DOI：
10.1109/dac.2000.855354
发表时间：
2000-06
期刊：
Proceedings 37th Design Automation Conference
影响因子：
--
作者：
Yun-Chih Chang;Yao-Wen Chang;G. Wu;Shu-Wei Wu
通讯作者：
Yun-Chih Chang;Yao-Wen Chang;G. Wu;Shu-Wei Wu
DOI：
10.1109/tvlsi.2004.840760
发表时间：
2005-02
影响因子：
2.8
作者：
Jai-Ming Lin;Yao-Wen Chang
通讯作者：
Jai-Ming Lin;Yao-Wen Chang
DOI：
10.1287/ijoc.1060.0192
发表时间：
2007-07
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
David Pisinger
通讯作者：
David Pisinger