SOLVING CUTTING STOCK PROBLEM USING PATTERN GENERATION METHOD ON 2-DIMENSIONAL STOCK
Abstract
This article discusses the solution of the 2-dimensional stock cutting problem using the Branch and Bound modified pattern generation method. The pattern generation method will produce a feasible cutting pattern matrix which is then converted into a mathematical model with a linear program equation with an objective function to minimize the use of initial stock materials. The research is a case study located at the Handal Karya Buana Store which is engaged in cutting glass of different sizes, thicknesses and types of glass. In this case, 3 types of initial stock will be used with the same thickness, and type but have different area sizes, and one of the consumer demand data will be used, namely 3 types of requests with different sizes and many requests. By using the pattern generator method, 10 cutting patterns are generated with each different cutting residue. By using the simplex method, the optimal solution is obtained for the amount of initial stock needed, the pattern used and the remaining cuts produced. So using the pattern generator method can produce a feasible cutting pattern, and can be used as an alternative to solve the stock cutting problem.
Downloads
References
P. C. Gilmore and R. E. Gomory, A linear programming approach to the cutting-stock problem, vol. 9. 1961.
R. W. Haessler and P. E. Sweeney, “Cutting stock problems and solution procedures,” Eur. J. Oper. Res., vol. 54, no. 2, pp. 141–150, 1991, doi: 10.1016/0377-2217(91)90293-5.
S. Octarina, M. Radiana, and P. B. J. Bangun, “Implementation of pattern generation algorithm in forming Gilmore and Gomory model for two dimensional cutting stock problem,” IOP Conf. Ser. Mater. Sci. Eng., vol. 300, no. 1, 2018, doi: 10.1088/1757-899X/300/1/012021.
S. Boualem and M. Abbas, “Contribution to Solving A Two-Dimensional Cutting Stock Problem with Two Objectives,” Econ. Comput. Econ. Cybern. Stud. Res., vol. 56, no. 2, pp. 179–194, 2022, doi: 10.24818/18423264/56.2.22.12.
B. I. Erdem and R. Kasimbeyli, “a Two-Step Math Heuristic Solution Approach for the Two-Dimensional Cutting Stock Problem,” J. Nonlinear Convex Anal., vol. 24, no. 4, pp. 681–699, 2023.
P. B. J. Bangun, S. Octarina, and A. P. Pertama, “Implementation of branch and cut method on n-sheet model in solving two dimensional cutting stock problem,” J. Phys. Conf. Ser., vol. 1282, no. 1, 2019, doi: 10.1088/1742-6596/1282/1/012012.
M. Dodge, S. A. MirHassani, and F. Hooshmand, “Solving two-dimensional cutting stock problem via a DNA computing algorithm,” Nat. Comput., vol. 20, no. 1, pp. 145–159, 2021, doi: 10.1007/s11047-020-09786-3.
M. Atika, B. P. Silalahi, and F. Bukhari, “Pattern Generation for Three Dimensional Cutting Stock Problem,” JTAM (Jurnal Teor. dan Apl. Mat., vol. 6, no. 4, p. 991, 2022, doi: 10.31764/jtam.v6i4.9933.
P. Caricato and A. Grieco, “An Application of Industry 4.0 to the Production of Packaging Films,” Procedia Manuf., vol. 11, no. June, pp. 949–956, 2017, doi: 10.1016/j.promfg.2017.07.199.
A. Rahman, I. Hasbiyati, and M. D. H. Gamal, “Approximation Method for Solving TwoDimensional Cutting-Stock Problems Abstract :,” vol. 19, no. 1, pp. 29–34, 2023, doi: 10.9790/5728-1901022934.
N. P. Rodrigo, W. B. Daundasekera, and A. I. Perera, “One-Dimensional Bin-Packing Problems with Branch and Bound Algorithm,” Int. J. Discret. Math., vol. 3, no. 2, pp. 36–40, 2018, doi: 10.11648/j.dmath.20180302.12.
S. Lomate, B. Rajiv, P. D. Pantawane, and B. B. Ahuja, “Greedy Algorithm to generate cutting patterns for Cutting Stock Problem (1D and 2D),” Ind. Eng. J., vol. 13, no. 4, 2020, doi: 10.26488/iej.13.4.1223.
S. Altin, T. Aydilek, U. Sirvan, D. Kesikburun, A. Oner, and N. Kutup, “Three Dimensional Cutting Stock Problem in Mattress Production: A Case Study,” Proc. Int. Symp. Prod. Res. 2018, pp. 949–960, 2019, doi: 10.1007/978-3-319-92267-6.
F. S. Hillier, G. J. Lieberman, and F. S. Hillier, Introduction to Operation Research., 9th ed. New Jersey: McGraw-Hill Education, 2010.
W. L. Winston, Operations Research: Applications and Algorithms, 4th ed. Belmont: Thomson Brooks/ Cole, 2004.
M. D. H. Gamal, “Program Linear dan Integer,” 2024. https://repository.unri.ac.id/handle/123456789/11313
M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, “Linear Programming and Network Flows,” J. Oper. Res. Soc., vol. 29, no. 5, p. 510, 1978, doi: 10.2307/3009778.
E. K. P. Chong and S. H. Zak, An Introduction to Optimization. New Jersey: John Wiley & Sons, 2013.
Copyright (c) 2025 Ihda Hasbiyati, Indri Latifa, Abdul Rahman, Ahriyati Ahriyati, Moh Danil Hendry Gamal
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
