Solution Approach to Cutting Stock Problems Using Iterative Trim Loss Algorithm and Monte-Carlo Simulation

Abstract

Cutting Stock Problems are the most studied NP-Hard combinatorial problems among optimization problems. An One-dimensional Cutting Stock Problem (1-CSP), which aims to create cutting patterns to minimize trim loss, is one of the best known optimization problems. The difficulty of the solution stages and the lack of a definite solution method that can be applied to all problems have caused these problems to attract a lot of attention by researchers. This study includes a hybrid solution algorithm combined with iterative trim loss algorithm and Monte Carlo simulations, and a comparative study of the method with the solution methods in the literature, for the solution of orders to be obtained with minimum cutting loss from the same type of stocks.

Keywords

• Combinatorial Optimization
• NP-Hard
• Cutting Stock Problems

References

1. 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 (IJAIE), 6(2):1–19.
2. Bayır, F. (2012). “Kesme Problemine Sezgisel Bir Yaklaşım”, Doktora Tezi, İstanbul Üniversitesi
3. Dikili, A. C., Barlas, B. (2011). A generalized approach to the solutionof one-dimensional stock-cutting problem for small shipyards.Journal ofmarine science and technology, 19(4):368–376
4. Dyckhoff, H. (1990) “A typology of cutting and packing problems”, Eur. J. Opi Res. 44, 145-159.
5. Evtimov, G. and Fidanova, S. (2018). Ant Colony Optimization Algorithm for1D Cutting Stock Problem, pages 25–31. Springer International Publishing,Cham
6. Falkenauer, E., Delchambre, A. (1992). "A genetic algorithm for bin packing and line balancing ", ICRA, pp. 1186-1192.
7. Gilmore, P. C.; Gomory, R. E. (1961). “A Linear Programming Approach to the Cutting Stock Problem”, Operations Research, v9, s.849-859.
8. Gilmore, P. C.; Gomory, R. E. (1963) “A Linear Programming Approach to the Cutting Stock Problem-Part II”, Operations Research, v11, s.863-888.

9. Gilmore, P. C.; Gomory, R. E. (1965) Multistage cutting stock problems of two and more dimensions. Opns Res. 13, 94-120.
10. Gilmore, P. C.; Gomory, R. E. (1966) The theory and computation of knapsack functions. Opns Res. 14, 1045-1074.
11. Hinterding, R. and Khan, L. (1993). Genetic algorithms for cutting stock pro-blems: with and without contiguity. In Progress in evolutionary computation, pages 166–186. Springe
12. Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4):366–422.
13. Levine, J. and Ducatelle, F. (2004). Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the Operational Research Society, 55(7):705–716
14. Liang, K.H., Yao, X., Newton, Y., Hoffman, D. 2002. A new evolutionary approach to cutting stock problems with and without contiguity. Comput. Oper. Res., 29(12):1641–59.
15. Machado, A. A., Zayatz, J. C., da Silva, M. M., Melluzzi Neto, G., Leal, G.C. L., and Palma Lima, R. H. (2020). Aluminum bar cutting optimizationfor door and window manufacturing. DYNA, 87(212): 155–162
16. Ogunranti, G. A. and Oluleye, A. E. (2016). Minimizing waste (off-cuts) usingcutting stock model: The case of one-dimensional cutting stock problem inwood working industry.Journal of Industrial Engineering and Management, 9(3):834–859
17. Peng, J. and Chu, Z. S. (2010a). A hybrid ant colony algorithm for the cuttingstock problem. In 2010 International Conference on Future InformationTechnology and Management Engineering, volume 2, pages 32–35
18. Peng, J. and Chu, Z. S. (2010b). A Hybrid Multi-Chromosome Genetic Algorithm for the Cutting Stock Problem. In2010 3rd International Conferenceon Information Management, Innovation Management and Industrial Engi-neering, volume 1, pages 508–511
19. Ravelo, S. V., Meneses, C. N., and Santos, M. O. (2020). Meta-heuristics for the one-dimensional cutting stock problem with usable leftover. Journal of Heuristics, 26(4):585–618
20. Tanır, D. , Uğurlu, O., Nuriyev, U., Kapar, M. (2018). Birleşik Stok Kesme ve Patern Sıralama Problemi için Bir Sezgisel Algoritma . Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi , 22 (1) , 300-305
21. Zanarini, A. (2017). Optimal stock sizing in a cutting stock problem with sto-chastic demands. In Salvagnin, D. and Lombardi, M., editors,Integration of AI and OR Techniques in Constraint Programming, pages 293–301, Cham.Springer International Publishing