An Integrated Mathematical Model and a Matheuristic Algorithm for the Two-Dimensional Cutting and Scheduling Problem

Öz

The two-dimensional cutting problem is the problem of determining how to cut small-sized pieces from a large-sized plate. Since it is widely applied in industry, it is frequently addressed in the literature. In these studies, the aim is usually to minimize the use of stock materials or to minimize waste, but the scheduling dimension is neglected. In the literature, studies that consider these two essential problems together either ignore or consider only one of them, such as the 90° rotation of the order pieces or the presence of different stock material sizes, which would further increase the complexity of the problem. However, each of these features can lead to more successful solutions to the problem. Therefore, in this study, we consider a bi-objective, two-dimensional cutting, assortment, and scheduling problem where the order pieces are allowed to be rotated by 90°. The objectives of the problem are to minimize total waste and total order tardiness. An integrated mathematical model and a matheuristic algorithm are proposed to solve the problem. The performance of the proposed solution approaches is demonstrated using test problems with different sizes.

Anahtar Kelimeler

• Two-dimensional cutting problem
• Mixed-integer programming
• Due date
• Matheuristic algorithm

İki Boyutlu Kesme ve Çizelgeleme Problemi için Bütünleşik Bir Matematiksel Model ve Bir Matsezgisel Algoritma

Öz

İki boyutlu kesme problemi, büyük ebatlı bir levhadan küçük boyutlu parçaların nasıl kesileceğinin belirlenmesi problemidir. Endüstride yaygın bir uygulama alanına sahip olması nedeniyle literatürde de sıklıkla ele alınmaktadır. Bu çalışmalarda genellikle en az ana malzeme kullanımı ya da en az fire amaçlanmakta ancak çizelgeleme boyutu ihmal edilmektedir. Literatürde bu iki önemli problemi birlikte dikkate alan çalışmalarda ise sipariş parçalarının 90° döndürülmesi, ya da farklı ana malzeme ebatlarının varlığı gibi problemin karmaşıklığını daha da arttıracak durumlar göz ardı edilmekte ya da sadece birisi ele alınmaktadır. Oysa bu özelliklerin her biri problemin daha başarılı çözümlerinin elde edilebilmesine olanak yaratmaktadır. Bu nedenle bu çalışmada, parçaların 90° döndürülmesine izin verilen iki amaçlı, iki boyutlu kesme, ana malzeme seçimi ve çizelgeleme problemi ele alınmıştır. Ele alınan problemin amaçları toplam firenin ve toplam sipariş gecikmelerinin enküçüklenmesidir. Problemin çözümü için bütünleşik bir matematiksel model ve bir matsezgisel algoritma önerilmiştir. Önerilen çözüm yaklaşımlarının performansı farklı boyutlara sahip test problemleri kullanılarak gösterilmiştir.

Anahtar Kelimeler

• İki boyutlu kesme problemi
• Karma tamsayılı programlama
• Teslim zamanı
• Matsezgisel algoritma

Kaynakça

1. 1. Souza Queiroz, L.R.D. & Andretta, M. (2022). A branch‐and‐cut algorithm for the irregular strip packing problem with uncertain demands. International Transactions in Operational Research, 29(6), 3486-3513.
2. 2. Tsao, Y.C., Delicia, M. & Vu, T.L. (2022). Marker planning problem in the apparel industry: Hybrid PSO-based heuristics. Applied Soft Computing, 123, 108928.
3. 3. Yang, Y., Liu, B., Li, X., Jia, Q., Duan, W. & Wang, G. (2024). Fidelity-adaptive evolutionary optimization algorithm for 2D irregular cutting and packing problem. Journal of Intelligent Manufacturing, 1-19.
4. 4. Baldacci, R. & Boschetti, M.A. (2007). A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. European Journal of Operational Research, 183(3), 1136-1149.
5. 5. Russo, M., Boccia, M., Sforza, A. & Sterle, C. (2020). Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization. International Transactions in Operational Research, 27(2), 794-834.
6. 6. 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.
7. 7. 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.
8. 8. Chen, Q. & Chen, Y. (2024). Heuristics for the two-dimensional cutting stock problem with usable leftover. Intelligent Data Analysis, (Preprint), 1-21.

9. 9. Nascimento, D.N., Cherri, A.C., Oliveira, J.F. & Oliveira, B.B. (2023). The two-dimensional cutting stock problem with usable leftovers and uncertainty in demand. Computers & Industrial Engineering, 186, 109705.
10. 10. Arbib, C., Marinelli, F. & Pizzuti, A. (2021). Number of bins and maximum lateness minimization in two-dimensional bin packing. European Journal of Operational Research, 291(1), 101-113.
11. 11. Polyakovskiy, S. & M’Hallah, R. (2021). Just-In-Time Two-Dimensional Bin Packing. Omega, 102, 102311.
12. 12. Virk, A.K. & Singh, K. (2019). Application of nature inspired algorithms to optimize multi-objective two-dimensional rectangle packing problem. Journal of Industrial Integration and Management, 4(4), 1950010.
13. 13. Demir, Y. (2024). An iterated greedy algorithm for the planning of yarn‐dyeing boilers. International Transactions in Operational Research, 31(1), 115-139.
14. 14. Polyakovskiy, S. & M’Hallah, R. (2018). A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates. European journal of operational research, 266(3), 819-839.
15. 15. Braga, N., Alves, C., Macedo, R. & de Carvalho, J.V. (2015). A model-based heuristic for the combined cutting stock and scheduling problem. In Computational Science and Its Applications-ICCSA 2015: 15th International Conference, Banff, AB, Canada, June 22-25, 2015, Proceedings, Part II 15, 490-505.
16. 16. Bennell, J.A., Lee, L.S. & Potts, C.N. (2013). A genetic algorithm for two-dimensional bin packing with due dates. International Journal of Production Economics, 145(2), 547-560.
17. 17. Li, S. (1996). Multi-job cutting stock problem with due dates and release dates. Journal of the Operational Research Society, 47(4), 490-510.
18. 18. Beasley, J.E. (1985). An exact two-dimensional nonguillotine cutting tree search procedure. Operations Research, 33, 49-64.