IJAT Vol.14 No.3 pp. 447-458
doi: 10.20965/ijat.2020.p0447


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

Corresponding author

**NS Solutions Corporations, Tokyo, Japan

***The University of Tokyo, Tokyo, Japan

March 29, 2019
January 20, 2020
May 5, 2020
rectangular strip packing problem (RSPP), cutting stock problem (CSP), cutting constraints, guillotine cutting, column generation

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.

Cite this article as:
Masao Sugi, Yusuke Shiomi, Tsuyoshi Okubo, Hidetoshi Nagai, Kazuyoshi Inoue, and Jun Ota, “Solution of the Rectangular Strip Packing Problem Considering a 3-Stage Guillotine Cutting Constraint with Finite Slitter Blades,” Int. J. Automation Technol., Vol.14, No.3, pp. 447-458, 2020.
Data files:
  1. [1] H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European J. of Operational Research, Vol.44, No.2, pp. 145-149, 1990.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.
  6. [6] 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.
  7. [7] K. Eisemann, “The Trim Problem,” Management Science, Vol.3, No.3, pp. 279-284, 1957.
  8. [8] 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.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] 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.
  14. [14] 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.
  15. [15] 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.
  16. [16] J. E. Beasley, “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting,” J. of Operational Research Society, Vol.36, No.4, pp. 297-306, 1985.
  17. [17] 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.
  18. [18] 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.
  19. [19] 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.
  20. [20] 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.
  21. [21] 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.
  22. [22] 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.
  23. [23] 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.
  24. [24] 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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 05, 2021