Pattern Generation for Three Dimensional Cutting Stock Problem
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
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
Refbacks
- There are currently no refbacks.
Copyright (c) 2022 Mutia Atika, Bib Paruhum Silalahi, Fahren Bukhari
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
_______________________________________________
JTAM already indexing:
_______________________________________________
JTAM (Jurnal Teori dan Aplikasi Matematika) |
_______________________________________________
_______________________________________________
JTAM (Jurnal Teori dan Aplikasi Matematika) Editorial Office: