Heuristics for Solving the 2D Rectangle Packing Area Minimization Problem Basing on a Dynamic Reduction Method
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper addresses an NP-hard layout optimization problem with a high computational complexity: the two-dimensional rectangle packing area minimization problem (RPAMP), which is a core issue of floorplanning problem in the very-large-scale integration (VLSI) design. First, by dynamically designing the two dimensions of the large rectangular frame, the study reduces the solving of a RPAMP to the solving of a series of two-dimensional rectangle packing decision problems (RPDP). Then, based on a best-fit-degree approach for the RPDP, the designs a least-damage-first algorithm for the RPDP, which further takes the consideration of the current placement's impact on global compaction and of its negative effect on local space's integrity. Next, by combining the method of dynamically designing two dimensions of the rectangular frame, a final dynamic reduction algorithm is proposed for solving the RPAMP. Experiments were on 15 RPAMP instances (including the well-known MCNC instances and GSRC instances). Computational results show that the proposed algorithm refreshed the current best solutions on nine instances. At the same time it also matchs the current best records on two other instances. The obtained average filling rate is 98.50%, which improved the current best results reported in the literature by 0.85%.

    Reference
    Related
    Cited by
Get Citation

何琨,姬朋立,李初民.求解二维矩形Packing面积最小化问题的动态归约算法.软件学报,2013,24(9):2078-2088

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 03,2012
  • Revised:January 25,2013
  • Adopted:
  • Online: September 07,2013
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063