×

A tabu search algorithm for a two-dimensional non-guillotine cutting problem. (English) Zbl 1138.90430

Summary: We study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.

MSC:

90C10 Integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarez-Valdes, R.; Parreño, F.; Tamarit, J. M., A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems, Journal of Operational Research Society, 56, 414-425 (2005) · Zbl 1104.90040
[2] Amaral, A., Letchford, A., 2003. An improved upper bound for the two-dimensional non-guillotine cutting problem. Working paper available from the second author at Department of Management Science, Management School, Lancaster University, Lancaster LA1 4YW, England.; Amaral, A., Letchford, A., 2003. An improved upper bound for the two-dimensional non-guillotine cutting problem. Working paper available from the second author at Department of Management Science, Management School, Lancaster University, Lancaster LA1 4YW, England.
[3] Arenales, M.; Morabito, R., An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems, European Journal of Operational Research, 84, 599-617 (1995) · Zbl 0928.90074
[4] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 49-64 (1985) · Zbl 0569.90038
[5] Beasley, J. E., A population heuristic for constrained two-dimensional non-guillotine cutting, European Journal of Operational Research, 156, 601-627 (2004) · Zbl 1056.90011
[6] Caprara, A.; Monaci, M., On the two-dimensional knapsack problem, Operations Research Letters, 32, 5-14 (2004) · Zbl 1056.90115
[7] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 30-44 (1977) · Zbl 0369.90059
[8] Fekete, S.P., Schepers, J., 1997. On more-dimensional packing III: Exact algorithms. ZPR Technical Report 97-290. Available from: <http://www.zpr.uni-koeln.de/ paper; Fekete, S.P., Schepers, J., 1997. On more-dimensional packing III: Exact algorithms. ZPR Technical Report 97-290. Available from: <http://www.zpr.uni-koeln.de/ paper
[9] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0930.90083
[10] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 83, 39-56 (1995) · Zbl 0903.90124
[11] Healy, P.; Creavin, M.; Kuusik, A., An optimal algorithm for placement rectangle, Operations Research Letters, 24, 73-80 (1999) · Zbl 0956.90034
[12] Hopper, E.; Turton, B. C.H., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128, 34-57 (2001) · Zbl 0982.90044
[13] Jakobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 165-181 (1996) · Zbl 0913.90229
[14] Lai, K. K.; Chan, J. W.M., Developing a simulated annealing algorithm for the cutting stock problem, Computers and Industrial Engineering, 32, 115-127 (1997)
[15] Lai, K. K.; Chan, J. W.M., A evolutionary algorithm for the rectangular cutting stock problem, International Journal of Industrial Engineering, 4, 130-139 (1997)
[16] Leung, T. W.; Yung, C. H.; Troutt, M. D., Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem, Computers and Industrial Engineering, 40, 201-214 (2001)
[17] Leung, T. W.; Yung, C. H.; Troutt, M. D., Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem, European Journal of Operational Research, 145, 530-542 (2003) · Zbl 1011.90033
[18] Scheithauer, G., LP-based bounds for the container and multi-container loading problem, International Transactions in Operations Research, 6, 199-213 (1999)
[19] Scheithauer, G.; Terno, J., Modeling of packing problems, Optimization, 28, 63-84 (1993) · Zbl 0818.90083
[20] Tsai, R. D.; Malstrom, E. M.; Meeks, H. D., A two-dimensional palletizing procedure for warehouse loading operations, IIE Transactions, 20, 418-425 (1988)
[21] Wäscher, G., Haussner, H., Schumann, H., 2006. An improved typology of cutting and packing problems. European Journal of Operational Research, this issue.; Wäscher, G., Haussner, H., Schumann, H., 2006. An improved typology of cutting and packing problems. European Journal of Operational Research, this issue.
[22] Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 573-586 (1983) · Zbl 0517.90093
[23] Wu, Y. L.; Huang, W.; Lau, S. C.; Wong, C. K.; Young, G. H., An effective quasi-human based heuristic for solving rectangle packing problem, European Journal of Operational Research, 141, 341-358 (2002) · Zbl 1081.90615
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.