Solution of the Rectangular Strip Packing Problem Considering a 3-Stage Guillotine Cutting Constraint with Finite Slitter Blades
Masao Sugi*,, Yusuke Shiomi**, Tsuyoshi Okubo**, Hidetoshi Nagai**, Kazuyoshi Inoue**, and Jun Ota***
*The University of Electro-Communications
1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585, Japan
**NS Solutions Corporations, Tokyo, Japan
***The University of Tokyo, Tokyo, Japan
In this study, we propose a new algorithm to solve the rectangular strip packing problem (RSPP), a variant of the cutting stock problem in which the mother materials have a common fixed width and infinite length. Based on the column-generation technique with three improvements, the proposed algorithm can solve large-scale problems involving tens of thousands of materials within a reasonable time, considering practical cutting constraints, i.e., the three-stage guillotine cutting constraint and the limitations of slitter blades. The proposed algorithm is evaluated in terms of its packing efficiency and calculation time.
-  H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European J. of Operational Research, Vol.44, No.2, pp. 145-149, 1990.
-  R. J. Haessler and P. E. Sweeney, “Cutting stock problems and solution procedures,” European J. of Operational Research, Vol.54, No.2, pp. 141-150, 1991.
-  G. Wäscher, H. Haubner, and H. Schumann, “An Improved Typology of Cutting and Packing Problems,” European J. of Operational Research, Vol.183, No.3, pp. 1109-1130, 2007.
-  N. Ntene and J. H. van Vuuren, “A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem,” Discrete Optimization, Vol.6, No.2, pp. 174-188, 2009.
-  Y. Hu, H. Hashimoto, S. Imahori, T. Uno, and M. Yagiura, “A partition-based heuristic algorithm for the rectilinear block packing problem,” J. of the Operations Research Society of Japan, Vol.59, No.1, pp. 110-129, 2016.
-  S. Umetani, M. Yagiura, S. Imahori, T. Imamichi, K. Nonobe, and T. Ibaraki, “Solving the irregular strip packing problem via guided local search for overlap minimization,” Int. Trans. in Operational Research, Vol.16, No.6, pp. 661-683, 2009.
-  K. Eisemann, “The Trim Problem,” Management Science, Vol.3, No.3, pp. 279-284, 1957.
-  P. C. Gilmore and R. E. Gomory, “A Linear Programming Approach to The Cutting-Stock Problem,” Operations Research, Vol.9, No.6, pp. 849-859, 1961.
-  P. C. Gilmore and R. E. Gomory, “Multistage cutting stock problems of two and more dimensions,” Operations Research, Vol.13, No.1, pp. 94-120, 1965.
-  P. E. Sweeney and E. R. Paternoster, “Cutting and Packing Problems, A Categorized, Application-Oriented Research Bibliography,” J. of the Operational Research Society, Vol.43, No.7, pp. 691-706, 1992.
-  E. Hopper and B. H. C. Turton, “A Review of The Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems,” Artificial Intelligence Review, Vol.16, No.4, pp. 257-300, 2001.
-  F. Vanderbeck, “A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem,” Management Science, Vol.47, No.6, pp. 864-879, 2001.
-  S. Martello, M. Monaci, and D. Vigo, “An Exact Approach to The Strip-Packing Problem,” INFORMS J. on Computing, Vol.15, pp. 310-319, 2003.
-  E. K. Burke, G. Kendall, and G. Whitwell, “A New Placement Heuristic for The Orthogonal Stock-Cutting Problem,” Operations Research, Vol.52, No.4, pp. 655-671, 2004.
-  F. Furini, E. Malaguti, and D. Thomopulos, “Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming,” INFORMS J. on Computing, Vol.28, No.4, pp. 603-799, doi: 10.1287/ijoc.2016.0710, 2016.
-  J. E. Beasley, “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting,” J. of Operational Research Society, Vol.36, No.4, pp. 297-306, 1985.
-  J. E. Beasley, “A Population Heuristic for Constrained Two-Dimensional Non-Guillotine Cutting,” European J. of Operational Research, Vol.156, No.3, pp. 601-627, 2004.
-  B. S. Baker, E. G. Coffman Jr., and R. L. Rivest, “Orthogonal Packings in Two Dimensions,” SIAM J. on Computing, Vol.9, No.4, pp. 846-855, 1980.
-  J. Puchinger and G. R. Raidl, “Models and Algorithms for Three-Stage Two-Dimensional Bin Packing,” European J. of Operational Research, Vol.183, pp. 1304-1327, 2007.
-  D. Fayard, M. Hifi, and V. Zissimopoulos, “An Efficient Approach for Large-Scale Two-Dimensional Guillotine Cutting Stock Problems,” J. of the Operational Research Society, Vol.49, pp. 1270-1277, 1998.
-  A. T. Rahmani and N. Ono, “An Evolutionary Approach to Two-Dimensional Guillotine Cutting Problem,” Proc. of 1995 IEEE Int. Conf. on Evolutionary Computing, Vol.1, pp. 148-151, 1995.
-  E. G. Coffman Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, “Performance bounds for level-oriented two-dimensional packing algorithms,” SIAM J. on Computing, Vol.9, No.4, pp. 808-826, 1980.
-  M. Sugi, Y. Shiomi, T. Okubo, K. Inoue, and J. Ota, “A Solution for 2D Rectangular Cutting Stock Problems with 3-Stage Guillotine-Cutting Constraint,” Int. J. Automation Technol., Vol.4, No.5, pp. 461-468, 2010.
-  S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol.220, No.4598, pp. 671-680, 1983.