İKİ BOYUTLU KESME PROBLEMİ İÇİN YENİ KARMA TAMSAYILI DOĞRUSAL PROGRAMLAMA MODELLERİ

Year 2024, , 1130 - 1139, 22.04.2024

Büşra Tutumlu , Gülüm Tunçer , Tuğba Saraç

https://doi.org/10.31796/ogummf.1283954

Abstract

Bu çalışma, iki boyutlu kesme problemlerinin çözümü için yeni karma tamsayılı doğrusal matematiksel modeller (M1 ve M2) önermektedir. M1 modeli, literatürdeki model ile kıyaslanırken, M2 modeli parçaların 90 derece döndürülmesine izin vererek ek esneklik sunmaktadır. Bu çalışmada, önerilen modellerin performansı, literatürden alınan ve en iyi çözümleri bilinen test problemleri kullanılarak değerlendirilmektedir. Ayrıca, çalışma bir gerçek hayat uygulaması da içermektedir. Bu kapsamda lokomotif ve motor üretimi yapan bir fabrikanın vagon atölyesindeki 16 ve 25 parçalı kesme problemleri önerilen modellerle çözülmüş ve sonuçlar işletmenin mevcut çözümü ile karşılaştırılmıştır. Sonuç olarak, 16 parçalı kesme probleminde M1 ve M2 modelleri sırasıyla %1,32 ve %2,32 oranında iyileşme sağlamıştır. 25 parçalı kesme probleminde ise, M1 modeli %1,59 ve M2 modeli %8,78 oranında iyileşme elde edilmiştir. Bu sonuçlar, önerilen modellerin kesme problemlerini çözmekte etkili olduğunu ve mevcut yöntemlere göre daha iyi sonuçlar elde ettiğini göstermektedir. Bu çalışma, kesme problemlerinin çözümünde yeni ve etkili yöntemler sunarak, malzeme kullanımını optimize etmeye ve israfı azaltmaya yardımcı olabilecek potansiyel katkıları ile sürdürülebilir üretim uygulamalarına da katkı sağlamaktadır.

Keywords

İki boyutlu kesme problemi, Karma tamsayılı doğrusal programlama, Gerçek hayat uygulaması.

NEW MIXED INTEGER LINEAR PROGRAMMING MODELS FOR TWO-DIMENSIONAL CUTTING STOCK PROBLEM

Abstract

This study proposes new mixed-integer linear mathematical models (M1 and M2) for solving two-dimensional cutting stock problems. The M1 model is compared with the model in the existing literature, while the M2 model allows for additional flexibility by permitting 90-degree rotation of the pieces. In this study, the performance of these models is evaluated using test problems with known optimal solutions from the literature. Additionally, for real-world applications, cutting stock problems involving 16 and 25 pieces in a wagon workshop of a locomotive and engine manufacturing factory are solved using the proposed models, and the results are compared with the company's existing solution. As a result, in the 16-piece cutting problem, the M1 and M2 models achieved improvements of 1.32% and 2.32%, respectively. In the 25-piece cutting problem, the M1 model attained a 1.59% improvement, while the M2 model achieved an 8.78% improvement. These results demonstrate that the proposed models are effective in solving cutting problems and yield better outcomes compared to existing methods. This study presents novel and efficient approaches to solving cutting problems, which have the potential to optimize material usage and reduce waste, contributing to more sustainable manufacturing practices.

Keywords

Two-dimensional cutting stock problem, Mixed-integer linear programming model, Real-life application.

References

• Albayrak, E. (2013). İki boyutlu dikdörtgen şekilli stok kesme problemleri için sezgisel-metasezgisel algoritma ve yazılım geliştirme (Yüksek Lisans Tezi). Balıkesir Üniversitesi Fen Bilimleri Enstitüsü, Balıkesir.
• Andrade, R., Birgin, R. G., Morabito, R., & Ronconi, D. P. (2014). MIP models for two-dimensional non-guillotine cutting problems with usable leftovers. Journal of the Operational Research Society, 65, 1649-1663. doi: http://doi.org/10.1057/jors.2013.108
• Arahori, Y., Imamichi, T., & Nagamochi, H. (2012). An exact strip packing algorithm based on canonical forms. Computers & Operations Research, 39(12), 2991-3011. doi: http://doi.org/10.1016/j.cor.2012.03.003
• Bağrıyanık, O. İ. E. (2019). Levha kesme problemlerine karşılaştırmalı bir yaklaşım (Yüksek Lisans Tezi). Karadeniz Teknik Üniversitesi Fen Bilimleri Enstitüsü, Trabzon.
• Baldacci, R., Boschetti, M. A., Ganovelli, M., & Maniezzo, V. (2014). Algorithms for nesting with defects. Discrete Applied Mathematics, 163(1), 17-33. doi: https://doi.org/10.1016/j.dam.2012.03.026
• Bang-Jensen, J., & Larsen, R. (2012). Efficient algorithms for real-life instances of the variable size bin packing problem. Computers & Operations Research, 39(11), 2848-2857. doi: http://doi.org/10.1016/j.cor.2012.02.018
• Beasley, J. E. (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33, 49-64. doi: http://doi.org/10.1287/opre.33.1.49
• D'Amato, J. P., Mercado, M., Heiling, A., & Cifuentes, V. (2016). A proximal optimization method to the problem of nesting irregular pieces using parallel architectures. Revista Iberoamericana De Automatica E Informatica Industrial, 13(2), 220-227. doi: http://doi.org/10.1016/j.riai.2016.01.003
• Denli, D. H. (2013). İki boyutlu standart geometrik yapılı parçaların kesim probleminin analitik ve genetik algoritma çözümü (Yüksek Lisans Tezi). Çukurova Üniversitesi Fen Bilimleri Enstitüsü, Adana.
• Erdoğan, Y. A. (2010). İki boyutlu bir kesme problemi için sezgisel yaklaşımlı bir uygulama (Yüksek Lisans Tezi). Bahçeşehir Üniversitesi Fen Bilimleri Enstitüsü, İstanbul.
• Ergün, K. (2004). Kesme ve paketleme problemleri ve araştırmaya yönelik bir metot geliştirilmesi ve bu metodun etkinliğinin sınanması (Yüksek Lisans Tezi). Balıkesir Üniversitesi Fen Bilimleri Enstitüsü, Balıkesir.
• Fırat, H. (2018). İmalat sektöründe parça yerleştirme ve kesme probleminin optimizasyonu (Yüksek Lisans Tezi). İnönü Üniversitesi Fen Bilimleri Enstitüsü, Malatya.
• Fırat, H., Alpaslan, N. ve Hanbay, D. (2019). Dikdörtgen parçalar ile iki boyutlu kesme ve paketleme problemi için sezgisel yöntemler kullanan bir hibrit metodoloji. Politeknik Dergisi, 22(4), 979-988. doi: http://doi.org/10.2339/politeknik.487602
• Goncalves, J. F., & Wascher, G. (2020). A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects. European Journal of Operational Research, 286(3), 867-882. doi: http://doi.org/10.1016/j.ejor.2020.04.028
• Gümüş, G. (2012). Dikdörtgen şekilli malzeme kesme problemleri için genetik algoritma tabanlı çok ölçütlü bir çözüm yaklaşımı (Yüksek Lisans Tezi). Anadolu Üniversitesi Fen Bilimleri Enstitüsü, Eskişehir.
• Hoare, N. P., & Beasley, J. E. (2001). Placing boxes on shelves: A case study. Journal of the Operational Research Society, 52, 605-614. doi: http://doi.org/10.1057/palgrave.jors.2601130
• İçmen, B. (2015). İki boyutlu kesme ve ana malzeme seçimi problemleri için matematiksel modeller ve çözüm yaklaşımları (Yüksek Lisans Tezi). Anadolu Üniversitesi Fen Bilimleri Enstitüsü, Eskişehir.
• Lee, J., Kim, B. I., & Johnson, A. L. (2013). A two-dimensional bin packing problem with size changeable items for the production of wind turbine flanges in the open die forging industry. IIE Transactions, 45(12), 1332-1344. doi: http://doi.org/10.1080/0740817X.2012.725506
• Leung, S. C. H., Zhang, D., & Sim, K. M. (2011). A two-stage intelligent search algorithm for the two-dimensional strip packing problem. European Journal of Operational Research, 215(1), 57-69. doi: http://doi.org/10.1016/j.ejor.2011.06.002
• Lori, M., de Lima, V. L., Martello, S., Miyazawa, F. K., & Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2), 399-415. doi: http://doi.org/10.1016/j.ejor.2020.06.050
• Martinovic, J., Strasdat, N., de Carvalho, J. V., & Furini, F. (2021). Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups. Optimization Letters. doi: http://doi.org/10.1007/s11590-021-01825-x
• Nepomuceno, N. V., Pinheiro, P. R., & Coelho, A. L. V. (2008). A hybrid optimization framework for cutting and packing problems. Springer-Verlag, 153, 87-99. Erişim adresi: http://link.springer.com/chapter/10.1007/978-3-540-70807-0_6
• Özcan, E., Kai, Z., & Drake, J. H. (2013). Bidirectional best-fit heuristic considering compound placement for two dimensional orthogonal rectangular strip packing. Expert Systems with Applications, 40(10), 4035-4043. doi: https://doi.org/10.1016/j.eswa.2013.01.005
• Qiu, X. S., Zhang, Y. H., Wu, J. Y., & Ma, X. M. (2012). Method of grouping and cutting pattern of cutting problem of two-dimensional plate. Advanced Materials Research, 462, 194-198. doi: http://doi.org/10.4028/www.scientific.net/AMR.462.194
• Queiroz, L. R. S., & Andretta, M. (2020). Two effective methods for the irregular knapsack problem. Applied Soft Computing, 95. doi: http://doi.org/10.1016/j.asoc.2020.106485
• Söke, A. ve Bingül, Z. (2005). İki boyutlu giyotinsiz kesme problemlerinin benzetilmiş tavlama algoritmasi ile çözümlerinin i̇ncelenmesi. Politeknik Dergisi, 8(1), 25-35. Erişim adresi: http://dergipark.org.tr/tr/download/article-file/384425
• Verstichel, J., De Causmaecker, P., & Vanden Berghe, G. (2013). An improved best-fit heuristic for the orthogonal strip packing problem. International Transactions in Operational Research, 20(5), 711-730. doi: http://doi.org/10.1111/itor.12030
• Virk, A. K., & Singh, K. (2019). Application of nature ınspired algorithms to optimize multi-objective two-dimensional rectangle packing problem. Journal of Industrial Integration and Management, 4(4). doi: http://doi.org/10.1142/S2424862219500106
• Wei, L., Hu, Q., Lim, A., & Liu, Q. (2018). A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem. European Journal of Operational Research, 270(2), 448-4747. doi: http://doi.org/10.1016/j.ejor.2018.04.014
• Wei, L. J., Qin, H., Cheang, B., & Xu, X. H. (2016). An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem. International Transactions in Operational Research, 23(1-2), 65-92. doi: http://doi.org/10.1111/itor.12138
• Wu, K., Min, X., & Zhang, D. (2019). Research on two-dimensional cutting problem with defects. International Conference on Software Engineering and Service Science. Erişim adresi: http://c85689232ea394a8dc08a512c1f46793a2397178.vetisonline.com/stamp/stamp.jsp?tp=&arnumber=9040847
• Yang, S., Han, S., & Ye, W. (2013). A simple randomized algorithm for two-dimensional strip packing. Computers & Operations Research, 40(1), 1-8. doi: http://doi.org/10.1016/j.cor.2012.05.001