Simple heuristic for the constrained two-dimensional cutting problem

Abstract

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.

Keywords

cutting stock constrained two-dimensional cutting guillotine cuts

References

Razfar

M. R.

Asadnia

Haghshenas

Farahnakian

Optimum surface roughness prediction in face milling X20Cr13 using particle swarm optimization algorithm. Proc. IMechE, Part B: J. Engng Mf., 2010, 224, 1645–1653.

Sedighi

Hadi

Preform optimization for reduction of forging force using a combination of neural network and genetic algorithm. Proc. IMechE, Part B: J. Engng Mf., 2010, 224, 1717–1724.

Cui

Zhang

Wang

An algorithm for the two-dimensional cutting problem of punched strips with blade length constraint. Proc. IMechE, Part B: J. Engng Mf., 2008, 222, 1443–1451.

Wang

P. Y.

Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res., 1983, 32, 573–586.

Viswanathan

K. V.

Bagehi

Best-first search methods for constrained two-dimensional cutting stock problems. Oper. Res., 1993, 41, 768–776.

Cung

V.-D.

Hifi

Cun

B. L.

Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm. Int. Trans. Oper. Res., 2000, 7, 185–210.

Amaral

A. R. S.

Wright

Efficient algorithm for the constrained two-dimensional cutting stock problem. Int. Trans. Oper. Res., 2001, 8, 3–13.

Vasko

F. J.

Bartkowski

C. L.

Using Wang’s two-dimensional cutting stock algorithm to optimally solve difficult problems. Int. Trans. Oper. Res., 2009, 16, 829–838.

Fayard

Hifi

Zissimopoulos

An efficient approach for large-scale two-dimensional guillotine cutting stock problem. J. Oper. Res. Soc., 1998, 49, 1270–1277.

10.

Alvarez-Valdés

Parajón

Tamarit

J. M.

A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput. Oper. Res., 2002, 29, 925–947.

11.

Hifi

Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems. J. Comb. Optim., 2004, 8, 65–84.

12.

Chen

A recursive algorithm for constrained two-dimensional cutting problems. Comput. Optim. Appl., 2008, 41, 337–348.

13.

Morabito

Vitória Pureza

A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem. Ann. Oper. Res., 2010, 179, 297–315.

14.

Araya

Neveu

Riff

M. C.

An efficient hyperheuristic for strip-packing problems. In Adaptive and Multilevel Metaheuristics (Eds Cotta

Sevaux

Sorrenson

) 2008, pp. 61–76 (Springer Verlag, Germany).

15.

Riff

M. C.

Bonnaire

Neveu

A revision of recent approaches for two dimensional strip-packing problems. Engng Appl. Artif. Intell., 2009, 22, 823–827.

16.

Cui

Simple block patterns for the two-dimensional cutting problem. Math. Comput. Model., 2007, 45, 943–953.

17.

Suliman

S. M. A.

A sequential heuristic procedure for the two-dimensional cutting-stock problem. Int. J. Prod. Econ., 2006, 99, 177–185.

18.

Library of Instances, available from http://www.laria.u-picardie.fr/hifi/OR-Benchmark/ (access date May 10, 2011).

19.

ESICUP, available from http://paginas.fe.up.pt/~esicup/tiki-index.php (access date May 10, 2011).