A new heuristic algorithm for rectangle packing

被引：68

作者：

Huang, Wenqi ^{[1
]}

Chen, Duanbing ^{[1
]}

Xu, Ruchu ^{[1
]}

机构：

[1] Huazhong Univ Sci & Technol, Coll Comp Sci, Wuhan 430074, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2007年 / 34卷 / 11期

基金：

中国国家自然科学基金;

关键词：

rectangle packing; heuristic algorithm; caving degree; corner-occupying action;

D O I：

10.1016/j.cor.2005.12.005

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem. (C) 2006 Elsevier Ltd. All rights reserved.

引用

页码：3270 / 3280

页数：11

共 19 条

[1]

Chang YC, 2000, DES AUT CON, P458

[2] AN ANALYTICAL MODEL FOR THE CONTAINER LOADING PROBLEM [J].

CHEN, CS ;

LEE, SM ;

SHEN, QS .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 80 (01) :68-76

[3]

FEKETE SP, IN PRESS OPERATIONS

[4]

GUO PN, 1999, DAC 99, P268, DOI DOI 10.1145/309847.309928

[5] Corner block list: An effective and efficient topological representation of non-slicing floorplan [J].

Hong, XL ;

Huang, G ;

Cai, YC ;

Gu, JC ;

Dong, SQ ;

Cheng, CK ;

Gu, J .

ICCAD - 2000 : IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN, 2000, :8-12

[6] An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem [J].

Hopper, E ;

Turton, BCH .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 128 (01) :34-57

[7] A genetic algorithm for a 2D industrial packing problem [J].

Hopper, E ;

Turton, B .

COMPUTERS & INDUSTRIAL ENGINEERING, 1999, 37 (1-2) :375-378

[8] Two personification strategies for solving circles packing problem [J].

Huang, WQ ;

Xu, RC .

SCIENCE IN CHINA SERIES E-TECHNOLOGICAL SCIENCES, 1999, 42 (06) :595-602

[9]

HUANG WQ, 1997, SCI CHINA SER E, V27, P179

[10] Corner sequence - A P-admissible floorplan representation with a worst case linear-time packing scheme [J].

Lin, JM ;

Chang, YW ;

Lin, SP .

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2003, 11 (04) :679-686

← 1 2 →