Simple heuristic for the constrained two-dimensional cutting problem

被引：8

作者：

Cui, Y. ^{[1
]}

Chen, Q. ^{[1
]}

机构：

[1] Guangxi Univ, Sch Comp Elect & Informat, Nanning 530004, Peoples R China

来源：

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE | 2012年 / 226卷 / B3期

关键词：

cutting stock; constrained two-dimensional cutting; guillotine cuts; ALGORITHM; OPTIMIZATION;

D O I：

10.1177/0954405411421996

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper presents a heuristic for the constrained two-dimensional cutting problem in which a guillotine divides a plate into rectangular pieces. The objective of the proposed heuristic is to maximize the pattern value (that is, the total value of the pieces produced from the plate) while observing the constraint that the number produced of a piece can not exceed the demand for that piece. The algorithm uses a simple recursion approach to consider a set of cutting patterns with specified geometric features, and uses a bound technique to discard unpromising branches. It can give solutions competitive with those of other heuristic algorithms. Its solutions to some benchmark instances are better than those currently reported in the literature.

引用

页码：565 / 572

页数：8

共 17 条

[1] A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems [J].

Alvarez-Valdés, R ;

Parajón, A ;

Tamarit, JM .

COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (07) :925-947

[2]

Amaral A. R. S., 2001, International Transactions in Operational Research, V8, P3, DOI 10.1111/1475-3995.00002

[3]

Araya I., 2008, Adaptive and Multilevel Metaheuristics, volume 136 of Studies in Computational Intelligence, chapter An Efficient Hyperheuristic for Strip-Packing Problems, P61, DOI DOI 10.1007/978-3-540-79438-7_3

[4] A recursive algorithm for constrained two-dimensional cutting problems [J].

Chen, Yuanyan .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2008, 41 (03) :337-348

[5] An algorithm for the two-dimensional cutting problem of punched strips with blade length constraint [J].

Cui, Y. ;

Zhang, X. ;

Wang, Q. .

PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2008, 222 (11) :1443-1451

[6] Simple block patterns for the two-dimensional cutting problem [J].

Cui, Yaodong .

MATHEMATICAL AND COMPUTER MODELLING, 2007, 45 (7-8) :943-953

[7]

Cung V.-D., 2000, OPER RES, V7, P185

[8]

Fayard D, 1998, J OPER RES SOC, V49, P1270, DOI 10.2307/3010152

[9] Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems [J].

Hifi, M .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (01) :65-84

[10] A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem [J].

Morabito, Reinaldo ;

Pureza, Vitoria .

ANNALS OF OPERATIONS RESEARCH, 2010, 179 (01) :297-315

← 1 2 →