Pattern Generation for Three Dimensional Cutting Stock Problem

Mutia Atika; Bib Paruhum Silalahi; Fahren Bukhari

doi:10.31764/jtam.v6i4.9933

Pattern Generation for Three Dimensional Cutting Stock Problem

Mutia Atika, Bib Paruhum Silalahi, Fahren Bukhari

Abstract

We consider the problem of three-dimensional cutting of a large block that is to be cut into some small block pieces, each with a specific size and request. Pattern generation is an algorithm that has been used to determine cutting patterns in one-dimensional and two-dimensional problems. The purpose of this study is to modify the pattern generation algorithm so that it can be used in three-dimensional problems, and can determine the cutting pattern with the minimum possible cutting residue. The large block will be cut based on the length, width, and height. The rest of the cuts will be cut back if possible to minimize the rest. For three-dimensional problems, we consider the variant in which orthogonal rotation is allowed. By allowing the remainder of the initial cut to be rotated, the dimensions will have six permutations. The result of the calculation using the pattern generation algorithm for three-dimensional problems is that all possible cutting patterns are obtained but there are repetitive patterns because they suggest the same number of cuts.

Keywords

Guillotine Cutting; Pattern Generation; Three Dimensional Cutting Stock Problem.

Full Text:

DOWNLOAD [PDF]

References

Alfares, H. K., & Alsawafy, O. G. (2019). A Least-Loss Algorithm for a Bi-Objective One-Dimensional Cutting-Stock Problem. International Journal of Applied Industrial Engineering, 6(2), 1–19. https://doi.org/10.4018/ijaie.2019070101

Altın, S., Aydilek, T., Şirvan, U., Yüksel, D., Öner, A., & Kutup, N. (2019). Three Dimensional Cutting Stock Problem in Mattress Production: A Case Study (pp. 949–960). https://doi.org/10.1007/978-3-319-92267-6_76

Alvarez-Valdes, R., Parajon, A., & Tamarit, J. M. (2002). A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems. OR Spectrum, 24(2), 179–192. https://doi.org/10.1007/s00291-002-0093-3

Beasley, J. E. (1985). An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure. Operations Research, 33(1), 49–64. http://www.jstor.org/stable/170866

Bortfeldt, A., & Wäscher, G. (2013). Constraints in container loading – A state-of-the-art review. European Journal of Operational Research, 229(1), 1–20. https://doi.org/https://doi.org/10.1016/j.ejor.2012.12.006

Cerqueira, G., Aguiar, S., & Marques, M. (2021). Modified Greedy Heuristic for the one-dimensional cutting stock problem. Journal of Combinatorial Optimization, 42, 1–18. https://doi.org/10.1007/s10878-021-00695-4

Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y., & Xavier, E. C. (2008). Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1), 61–85. https://doi.org/https://doi.org/10.1016/j.ejor.2007.08.007

Clautiaux, F., Sadykov, R., Vanderbeck, F., & Viaud, Q. (2019). Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers. EURO Journal on Computational Optimization, 7(3), 265–297. https://doi.org/10.1007/S13675-019-00113-9

Cui, Y., Zhong, C., & Yao, Y. (2015). Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost. European Journal of Operational Research, 243(2), 540–546. https://doi.org/10.1016/J.EJOR.2014.12.015

De Queiroz, T. A., Miyazawa, F. K., Wakabayashi, Y., & Xavier, E. C. (2012). Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing. Computers and Operations Research, 39(2). https://doi.org/10.1016/j.cor.2011.03.011

Furini, F., & Malaguti, E. (2013). Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Computers & Operations Research, 40(8), 1953–1962. https://doi.org/10.1016/J.COR.2013.02.026

Furini, F., Malaguti, E., Medina Durán, R., Persiani, A., & Toth, P. (2012). A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size. European Journal of Operational Research, 218(1), 251–260. https://doi.org/10.1016/J.EJOR.2011.10.018

Gilmore, P. C., & Gomory, R. (1963). A Linear Programming Approach to the Cutting Stock Problem—Part II. Operations Research, 11. https://doi.org/10.1287/opre.11.6.863

Gilmore, P. C., & Gomory, R. E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research, 13(1), 94–120. https://doi.org/10.1287/opre.13.1.94

Hifi, M. (2004). Exact algorithms for unconstrained three-dimensional cutting problems: a comparative study. Computers & Operations Research, 31(5), 657–674. https://doi.org/https://doi.org/10.1016/S0305-0548(03)00019-4

Karelahti, J. (2002). Solving the cutting stock problem in the steel industry. Helsinki University Of Technology, Helsinki, Finlandia.

Kwon, S. J., Joung, S., & Lee, K. (2019). Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem. Computers & Operations Research, 109, 159–169. https://doi.org/10.1016/J.COR.2019.05.005

Macedo, R., Alves, C., & Valério de Carvalho, J. M. (2008). Exact Algorithms for the Two Dimensional Cutting Stock Problem. Algoritma Research Center, June.

Macedo, R., Alves, C., & Valério de Carvalho, J. M. (2010). Arc-flow model for the two-dimensional guillotine cutting stock problem. Computers and Operations Research, 37(6), 991–1001. https://doi.org/10.1016/j.cor.2009.08.005

Martin, M., Morabito, R., & Munari, P. (2020). A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem. Computers & Operations Research, 115, 104851. https://doi.org/https://doi.org/10.1016/j.cor.2019.104851

Martin, M., Oliveira, J. F., Silva, E., Morabito, R., & Munari, P. (2021). Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm. Expert Systems with Applications, 168. https://doi.org/10.1016/j.eswa.2020.114257

Martinovic, J., Scheithauer, G., & Valério de Carvalho, J. M. (2018). A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems. European Journal of Operational Research, 266(2), 458–471. https://doi.org/10.1016/J.EJOR.2017.10.008

Muter, İ., & Sezer, Z. (2018). Algorithms for the one-dimensional two-stage cutting stock problem. European Journal of Operational Research, 271(1), 20–32. https://doi.org/10.1016/J.EJOR.2018.04.042

Ravelo, S. V., Meneses, C. N., & Santos, M. O. (2020). Meta-heuristics for the one-dimensional cutting stock problem with usable leftover. Journal of Heuristics, 26(4), 585–618. https://doi.org/10.1007/s10732-020-09443-z

Rodrigo, N. (2012). Pattern Generation for Two Dimensional Cutting Stock Problem. International Journal of Mathematics Trends and Technology, 3(2).

Rodrigo, N., Daundasekera, W., & Perera, A. (2015). Modified Method for One-Dimensional Cutting Stock Problem. Software Engineering, 3(3). https://doi.org/10.11648/j.se.20150303.11

Rodrigo, W., Daundasekera, W. ., & Perera, a. a. . (2012). Pattern Generation for Two-Dimensional Cutting Stock Problem with Location. Indian Journal of …, 3(2).

Russo, M., Sforza, A., & Sterle, C. (2013). An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem. International Journal of Production Economics, 145(2), 451–462. https://doi.org/10.1016/J.IJPE.2013.04.031

Suliman, S. M. A. (2001). Pattern generating procedure for the cutting stock problem. International Journal of Production Economics, 74(1–3). https://doi.org/10.1016/S0925-5273(01)00134-7

Valério de Carvalho, J. M. (2002). LP models for bin packing and cutting stock problems. European Journal of Operational Research, 141(2), 253–273. https://doi.org/https://doi.org/10.1016/S0377-2217(02)00124-8

Vishwakarma, R., & Powar, P. L. (2021). An efficient mathematical model for solving one-dimensional cutting stock problem using sustainable trim. Advances in Industrial and Manufacturing Engineering, 3, 100046. https://doi.org/10.1016/J.AIME.2021.100046

DOI: https://doi.org/10.31764/jtam.v6i4.9933