A new heuristic recursive algorithm for the strip rectangular packing problem

被引：83

作者：

Zhang, DF ^{[1
]}

Kang, Y

Deng, AS

机构：

[1] Xiamen Univ, Dept Comp Sci, Xiamen 361005, Peoples R China

[2] Yunnan Univ, Sch Software, Kunming 650091, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 08期

关键词：

packing problems; recursion; heuristic;

D O I：

10.1016/j.cor.2005.01.009

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T (n) = theta(n(3)). The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：2209 / 2217

页数：9

共 17 条

[1] AN EXACT TWO-DIMENSIONAL NON-GUILLOTINE CUTTING TREE-SEARCH PROCEDURE [J].

BEASLEY, JE .

OPERATIONS RESEARCH, 1985, 33 (01) :49-64

[2]

BELOV G, 2003, THESIS TU DRESDEN

[3] TWO-DIMENSIONAL FINITE BIN-PACKING ALGORITHMS [J].

BERKEY, JO ;

WANG, PY .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1987, 38 (05) :423-429

[4] On the two-dimensional knapsack problem [J].

Caprara, A ;

Monaci, M .

OPERATIONS RESEARCH LETTERS, 2004, 32 (01) :5-14

[5]

Cormen T. H., 2001, Introduction to Algorithms, V2nd

[6] New approaches to nesting rectangular patterns [J].

Dagli, CH ;

Poshyanonda, P .

JOURNAL OF INTELLIGENT MANUFACTURING, 1997, 8 (03) :177-190

[7] PACKING PROBLEMS [J].

DOWSLAND, KA ;

DOWSLAND, WB .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 56 (01) :2-14

[8]

FEKETE SP, 2004, 97290 ZPR

[9]

HADJICONSTANTIN.E, MS912 IMP COLL

[10] APPROXIMATION SCHEMES FOR COVERING AND PACKING PROBLEMS IN IMAGE-PROCESSING AND VLSI [J].

HOCHBAUM, DS ;

MAASS, W .

JOURNAL OF THE ACM, 1985, 32 (01) :130-136

← 1 2 →