Iterated Local Search Algorithm for the Constrained Two-Dimensional Non-Guillotine Cutting Problem

Document Type : Research Paper

Authors

ICD-LOSI, University of Technology of Troyes, 10010 Troyes cedex, France

Abstract

An Iterated Local Search method for the constrained two-dimensional non-guillotine cutting problem is presented. This problem consists in cutting pieces from a large stock rectangle to maximize the total value of pieces cut. In this problem, we take into account restrictions on the number of pieces of each size required to be cut. It can be classified as 2D-SLOPP (two dimensional single large objects placement problem) and has many industrial applications like in wood and steel industries. The proposed Iterated Local Search algorithm in which we use a constructive heuristic and a local search move based on reducing pieces. The algorithm is tested on well known instances from the literature. Our computational results are very competitive compared to the best known solutions of literature and improve a part of them.

Keywords

Main Subjects


[1] Alvarez-Valdes R., Parreno F., Tamarit J.M. (2005), A Grasp algorithm for constrained twodimensional
non guillotine cutting problems; Journal of Operational Research Society 56(4); 414-425.
[2] Alvarez-Valdes R., Parreno F., Tamarit J.M. (2007), A Tabu search algorithm for two-dimensional non
guillotine cutting problems; Journal of Operationan Research 183; 1167-1182.
[3] Beasley J.E. (1985), A two dimensional non guillotine cutting tree search procedure; Operations
Research 33(1); 49-64.
[4] Beasley J.E. (2004), A population heuristic for constrained two-dimensional non-guillotine cutting
problems; European Journal of Operational Research 156(3); 601-627.
[5] Biro M., Boros E. (1984), Network flows and non-guillotine cutting pattern; European Journal of
Operational Research 16; 215-221.
[6] Caprara A., Monaci M. (2004), On the two-dimensional Knapsack problem; Operations Research
Letters 32; 5-14.
[7] Christofides N., Whitlock C. (1977), An algorithm for two dimensional cutting problems; Operations
Research 25; 30-44.
[8] Farley A.A. (1999), Selection of stock plate characteristics and cutting style for two dimensional
cutting stock situations; European Journal of Operational Research 44; 239-246.
[9] Fekete S.P., Schepers J. (1997), On more-dimensional packing III: Exact Algorithms, Report
No.97.290; Technical University Berlin.
[10] Garey M.R., Johnson D.S. (1979), Computer and intractability: A guide to the theory of NPcompleteness;
Freeman and Company; San Francisco.
[11] Glover F., Kochenberger G. (2002), Editors, Handbook of metaheuristics; International series in
operations research and management science vol. 57; Kluwer Academic Publishers, Norwell, MA,
321-353.
[12] Hadjiconstantinou E., Boschetti M.A., Mingozzi A. (2002), New upper bounds for the twodimensional
orthogonal non-guillotine cutting stock problem; IMA Journal of Management
Mathematics 13; 95-119.
[13] Hadjiconstantinou E., Christofides N. (1995), An exact algorithm for general orthogonal twodimensional
knapsack problems; European Journal of Operational Research 83; 39-56.
[14] Healy P., Creavin M., Kuusik A. (1999), An optimal algorithm for placement rectangle; Operations
Research Letters 24; 73-80.
[15] Hopper E., Turton B.C.H. (2001), An empirical investigation of meta-heuristic and heuristic
algorithms for a 2D packing problem; European Journal of Operational Research 128; 34-57.
[16] Jakobs S. (1996), On genetic algorithms for the packing of polygons; European Journal of
Operational Research 88; 165-181.
[17] Lai K.K., Chan J.W.M. (1997), Developing a simulated annealing algorithm for the cutting stock
problem; Computers and Industrial Engineering 32; 115-127.
[18] Leung T.W., Yung C.H., Troutt M.D. (2001), Applications of genetic search and simulated annealing
to the two-dimensional orthogonal packing problem; Computers and Industrial Engineering 40; 201-
214.
[19] Leung T.W., Yung C.H., Troutt M.D. (2003), Application of a mixed simulated annealing-genetic
algorithm heuristic for the two-dimensional orthogonal packing problem; European Journal of
Operational Research 145; 530-542.
[20] Scheithauer G., Terno J. (1993), Modeling of packing problems; Optimization 28; 63-84.
[21] Tsai R.D., Malstrom E.M., Meeks H.D. (1988), A two-dimensional palletizing procedure for
warehouse loading operations; IIE Transactions 20; 418-425.
[22] Wächer G., Haussner H., Schumann H. (2007), An improved typology of cutting and packing
problems; European Journal of Operational Research 183; 1109-1130.
[23] Wang P.Y. (2003), Two algorithms for constrained two-dimensional cutting stock problems;
Operations Research 31; 573-586.
[24] Wu Y.L., Huang W., Wong S.C., Young G.H. (2002), An effective quasi-human based heuristic for
solving rectangle packing; European Journal of Operational Research 141; 341-358