×

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. (English) Zbl 1146.90499

Summary: We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms.

MSC:

90C27 Combinatorial optimization

Software:

COIN-OR; OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, Ilan; Megiddo, Nimrod; Todd, Michael J., New results on the average behavior of simplex algorithms, Bulletin of the American Mathematical Society (NS), 11, 2, 378-382 (1984) · Zbl 0545.90066
[2] Alvarez-Valdes, Ramon; Parajon, Antonio; Tamarit, Jose M., A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems, OR Spektrum, 24, 2, 179-192 (2002) · Zbl 1012.90032
[3] Arenales, M.; Morábito, 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] Baker, B. S.; Brown, D. J.; Katseff, H. P., A \(\frac{5}{4}\) algorithm for two-dimensional packing, Journal of Algorithms, 2, 348-368 (1981) · Zbl 0472.68032
[5] Beasley, J. E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the Operational Research Society, 36, 4, 297-306 (1985) · Zbl 0589.90040
[6] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 1, 49-64 (1985) · Zbl 0569.90038
[7] Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990)
[8] G. Belov, G. Scheithauer, Models with Variable Strip Widths for Two-dimensional Two-stage cutting, www.math.tu-dresden.de/ capad/PAPERS/03-varwidth.pdf; G. Belov, G. Scheithauer, Models with Variable Strip Widths for Two-dimensional Two-stage cutting, www.math.tu-dresden.de/ capad/PAPERS/03-varwidth.pdf
[9] Karl-Heinz Borgwardt, Probabilistic analysis of the simplex method, in: Brunswick, 1988 (Ed.), Mathematical Developments arising from Linear Programming, Contemp. Math., vol. 114, pp. 21-34, American Mathematical Society, Providence, RI, 1990.; Karl-Heinz Borgwardt, Probabilistic analysis of the simplex method, in: Brunswick, 1988 (Ed.), Mathematical Developments arising from Linear Programming, Contemp. Math., vol. 114, pp. 21-34, American Mathematical Society, Providence, RI, 1990.
[10] Bortfeldt, Andreas, A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces, European Journal of Operational Research, 172, 814-837 (2006) · Zbl 1111.90094
[11] A. Caprara, Packing 2-dimensional bins in harmony, in: Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, pp. 490-499.; A. Caprara, Packing 2-dimensional bins in harmony, in: Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, pp. 490-499.
[12] Caprara, A.; Lodi, A.; Monaci, M., An approximation scheme for the two-stage, two-dimensional bin packing problem, (Schulz, A. S.; Cook, W. J., Proceedings of the Ninth Conference on Integer Programming and Combinatorial Optimization (IPCO’02) (2002), Springer-Verlag), 320-334
[13] Caprara, A.; Lodi, A.; Monaci, M., Fast approximation schemes for two-stage, two-dimensional bin packing, Mathematics of Operations Research, 30, 1, 150-172 (2005) · Zbl 1082.90141
[14] Caprara, A.; Monaci, M., On the two-dimensional knapsack problem, Operations Research Letters, 32, 5-14 (2004) · Zbl 1056.90115
[15] Christofides, N.; Whitlock, C., An algorithm for two dimensional cutting problems, Operations Research, 25, 30-44 (1977) · Zbl 0369.90059
[16] Chung, F. R.K.; Garey, M. R.; Johnson, D. S., On packing two-dimensional bins, SIAM Journal of Algebraic and Discrete Methods, 3, 66-76 (1982) · Zbl 0495.05016
[17] G.F. Cintra, Algoritmos hı´bridos para o problema de corte unidimensional, in: XXV Conferência Latinoamericana de Informática, AssunçÃo, 1999.; G.F. Cintra, Algoritmos hı´bridos para o problema de corte unidimensional, in: XXV Conferência Latinoamericana de Informática, AssunçÃo, 1999.
[18] G.F. Cintra, Algoritmos para problemas de corte de guilhotina bidimensional, PhD thesis, Instituto de Matemática e Estatı´stica, São Paulo, 2004.; G.F. Cintra, Algoritmos para problemas de corte de guilhotina bidimensional, PhD thesis, Instituto de Matemática e Estatı´stica, São Paulo, 2004.
[19] Cintra, G. F.; Miyazawa, F. K.; Wakabayashi, Y.; Xavier, E. C., A note on the approximability of cutting stock problems, European Journal on Operations Research, 183, 3, 1328-1332 (2007) · Zbl 1135.90026
[20] G.F. Cintra, Y. Wakabayashi, Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems, in: Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, Lecture Notes in Computer Science, vol. 3059, 2004, pp. 175-190.; G.F. Cintra, Y. Wakabayashi, Dynamic programming and column generation based approaches for two-dimensional guillotine cutting problems, in: Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, Lecture Notes in Computer Science, vol. 3059, 2004, pp. 175-190.
[21] Coffman, E. G.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E., Performance bounds for level oriented two-dimensional packing algorithms, SIAM Journal on Computing, 9, 808-826 (1980) · Zbl 0447.68079
[22] COIN-OR Linear Program Solver, An Open Source code for Solving Linear Programming Problems, http://www.coin-or.org/Clp/index.html; COIN-OR Linear Program Solver, An Open Source code for Solving Linear Programming Problems, http://www.coin-or.org/Clp/index.html
[23] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA · Zbl 1047.68161
[24] Cung, Van-Dat; Hifi, Mhand; Cun, Bertrand Le, Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm, Int. Trans. Oper. Res., 7, 3, 185-210 (2000)
[25] Epstein, L., Two dimensional packing: The power of rotation, (Proceedings of the 28th International Symposium of Mathematical Foundations of Computer Science. Proceedings of the 28th International Symposium of Mathematical Foundations of Computer Science, Lecture Notes on Computer Science - LNCS, vol. 2747 (2003), Springer-Verlag), 398-407 · Zbl 1124.68431
[26] Fekete, S. P.; Schepers, J.; van der Veen, J. C., An exact algorithm for higher-dimensional orthogonal packing, Operations Research, 55, 3, 569-587 (2007) · Zbl 1167.90483
[27] Gilmore, P.; Gomory, R., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[28] Gilmore, P.; Gomory, R., A linear programming approach to the cutting stock problem - Part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[29] Gilmore, P.; Gomory, R., Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120 (1965) · Zbl 0128.39601
[30] Hifi, M., Exact algorithms for the guillotine strip cutting/packing problem, Computers & Operations Research, 25, 11, 925-940 (1998) · Zbl 1040.90568
[31] Herz, J. C., A recursive computational procedure for two-dimensional stock-cutting, IBM Journal of Research and Development, 462-469 (1972) · Zbl 0265.90057
[32] K. Jansen, R. van Stee, On strip packing with rotations, in: Proceedings of the ACM Symposium on Theory of Computing, 2005, pp. 755-761.; K. Jansen, R. van Stee, On strip packing with rotations, in: Proceedings of the ACM Symposium on Theory of Computing, 2005, pp. 755-761. · Zbl 1192.68908
[33] K. Jansen, G. Zhang, On rectangle packing: maximizing benefits, in: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 204-213.; K. Jansen, G. Zhang, On rectangle packing: maximizing benefits, in: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 204-213. · Zbl 1317.68280
[34] Kenyon, C.; Rémila, E., A near-optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research, 25, 645-656 (2000) · Zbl 0977.90043
[35] Lodi, A.; Martello, S.; Vigo, D., Models and bounds for two-dimensional level packing problems, Journal of Combinatorial Optimization, 8, 363-379 (2004) · Zbl 1084.90031
[36] Lodi, A.; Monaci, M., Integer linear programming models for 2-staged two-dimensional knapsack problem, Mathematical Programming, 94, 257-278 (2003) · Zbl 1030.90064
[37] Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS Journal on Computing, 15, 3, 310-319 (2003) · Zbl 1238.90116
[38] Miyazawa, F. K.; Wakabayashi, Y., Packing problems with orthogonal rotations, (Proceedings of Latin American Theoretical INformatics. Proceedings of Latin American Theoretical INformatics, Lecture Notes in Computer Science, vol. 2976 (2004), Springer-Verlag: Springer-Verlag Buenos Aires, Argentina), 359-368 · Zbl 1196.90105
[39] Morábito, R.; Arenales, M.; Arcaro, V. F., An and-or-graph approach for two-dimensional cutting problems, European Journal of Operational Research, 58, 263-271 (1992) · Zbl 0757.90071
[40] Mukhacheva, E. A.; Mukhacheva, A. S., The rectangular packing problem: Local optimum search methods based on block structures, Automation and Remote Control, 65, 2, 101-112 (2004) · Zbl 1066.90110
[41] Oliveira, J. F.; Ferreira, J. S., An improved version of Wang’s algorithm for two-dimensional cutting problems, European Journal of Operational Research, 44, 256-266 (1990) · Zbl 0684.90073
[42] Puchinger, J.; Raidl, G. R., An evolutionary algorithm for column generation in integer programming: an effective approach for 2d bin packing, (Proceedings of Parallel Problem Solving from Nature - PPSN VIII. Proceedings of Parallel Problem Solving from Nature - PPSN VIII, LNCS, vol. 3242 (2004), Springer-Verlag), 642-651
[43] Puchinger, J.; Raidl, G. R., Models and algorithms for three-stage two-dimensional bin packing, European Journal of Operational Research, 183, 3, 1304-1327 (2007) · Zbl 1135.90029
[44] Riehme, J. R.; Scheithauer, G.; Terno, J., The solution of two-stage guillotine cutting stock problems having extremely varying order demands, European Journal of Operational Research, 91, 543-552 (1996) · Zbl 0918.90122
[45] Seiden, S. S.; Woeginger, G. J., The two-dimensional cutting stock problem revisited, Mathematical Programming, 102, 3, 519-530 (2005) · Zbl 1078.90044
[46] Vanderbeck, F., A nested decomposition approach to a 3-stage 2-dimensional cutting stock problem, Management Science, 47, 864-879 (2001) · Zbl 1232.90326
[47] Wäscher, G.; Gau, T., Heuristics for the integer one-dimensional cutting stock problem: A computational study, OR Spektrum, 18, 131-144 (1996) · Zbl 0853.90099
[48] Wäscher, G.; Haussner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347
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.