Halı Dokuma Tezgahlarının İki Boyutlu Şerit Paketleme Problemi Kısıtları Kullanılarak Çizelgelenmesi

Öz

Bu çalışmada, bir halı üretim işletmesinde kısa vadeli üretim planının çizelgelenmesi ele alınmıştır. Çalışmanın amacı, halı dokuma tezgahlarına atanan işler için farklı kısıtlamalar ve süreler dikkate alınarak hazırlık sürelerini azaltmak, kaynakları etkin bir şekilde kullanmak ve verimliliği artırmaktır. Halı üretiminde kullanılan iplik türü, halının ilmek sıklığı ve hav yüksekliği gibi özelliklerin kaliteyi belirlediği ve bu kalitelerin her tezgâhta aynı şartlarda üretilemediği vurgulanmıştır. Bu nedenle, farklı kalite gereksinimlerine sahip siparişlerin en uygun şekilde sıralanması büyük önem taşımaktadır. Çalışmada, halı üretim işletmelerinde kısa vadeli üretim planlarının çizelgelenmesi için yeni matematiksel modeller geliştirilmiştir. Bu modeller, halı dokuma tezgahlarına atanan işlerin kısıtlamalarını ve sürelerini göz önünde bulundurarak, hazırlık sürelerini minimize eden ve kaynakların doğru kullanımını sağlayan bir çizelge oluşturmayı amaçlamaktadır. Çalışmanın sonuçları, geliştirilen bu yöntemlerin halı üretim işletmelerinde kısa vadeli üretim planlarının çizelgelenmesi için etkili ve verimli bir çözüm sunduğunu göstermektedir. Ayrıca problemin çözümü için sezgisel ve meta sezgisel yöntemler önerilmiştir. Deney sonucunda sezgisel ve meta sezgisel yöntemler ile elde edilen çözümlerin daha az maliyetli olduğu belirlenmiştir.

Anahtar Kelimeler

• Çizelgeleme
• halı üretim
• üretim planlama
• iki boyutlu Atama
• iki boyutlu şerit paketleme
• paralel makine
• tekstil.

Scheduling of Carpet Weaving Looms Using Two-Dimensional Strip Packing Problem Constraints

Öz

In this study, scheduling of the short-term production plan in a carpet production enterprise is discussed. The aim of this study is to minimize preparation times, optimize resource utilization, and enhance efficiency by considering various constraints and durations for the jobs assigned to carpet weaving looms. It is emphasized that features such as the type of yarn used in carpet production, the stitch density of the carpet and the pile height determine the quality and that these qualities cannot be produced under the same conditions on every loom. Therefore, optimal sequencing of orders with different quality requirements is of great importance. In the study, new mathematical models were developed for scheduling short-term production plans in carpet production enterprises. These models aim to develop a schedule that reduces preparation times and optimizes resource utilization while considering the constraints and durations of jobs assigned to carpet looms. The results of the study show that these developed methods offer an effective and efficient solution for scheduling short-term production plans in carpet production enterprises. Furthermore, heuristic and metaheuristic methods are prosed to solve the problem. The experimental study shows that results of heuristic and metaheuristic methods are better than the proposed mathematical modelling approaches.

Anahtar Kelimeler

• Scheduling
• carpet production
• production planning
• two-dimensional Assignment
• two-dimensional strip packaging
• parallel machine
• textile.

Kaynakça

1. [1] I. Mourtos, S. Vatikiotis, and G. Zois, “Scheduling Jobs on Unrelated Machines with Job Splitting and Setup Resource Constraints for Weaving in Textile Manufacturing,” , IFIP Advances in Information and Communication Technology, vol 630, 2021, pp. 424–434. doi: 10.1007/978-3-030-85874-2_45.
2. [2] M. Tucci and R. Rinaldi, “From theory to application: Tabu search in textile production scheduling,” Production Planning & Control, vol. 10, no. 4, pp. 365–374, Jan. 1999, doi: 10.1080/095372899233118.
3. [3] D. Yilmaz Eroglu and H. C. Ozmutlu, “Solution method for a large-scale loom scheduling problem with machine eligibility and splitting property,” The Journal of The Textile Institute, vol. 108, no. 12, pp. 2154–2165, Dec. 2017, doi: 10.1080/00405000.2017.1316177.
4. [4] R. UZSOY, “Scheduling a single batch processing machine with non-identical job sizes,” Int J Prod Res, vol. 32, no. 7, pp. 1615–1635, Jul. 1994, doi: 10.1080/00207549408957026.
5. [5] F. Jolai Ghazvini and L. Dupont, “Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes,” Int J Prod Econ, vol. 55, no. 3, pp. 273–280, Aug. 1998, doi: 10.1016/S0925-5273(98)00067-X.
6. [6] R. S. Trindade, O. C. B. de Araújo, and M. Fampa, “Arc-flow approach for single batch-processing machine scheduling,”Comput Oper Res, vol. 134, p. 105394, Oct. 2021, doi: 10.1016/j.cor.2021.105394.
7. [7] Y. H. Lee and Y. H. Lee, “Minimising makespan heuristics for scheduling a single batch machine processing machine with non-identical job sizes,” Int J Prod Res, vol. 51, no. 12, pp. 3488–3500, Jun. 2013, doi: 10.1080/00207543.2012.748226.
8. [8] P. Y. Chang, P. Damodaran, and S. Melouk, “Minimizing makespan on parallel batch processing machines,” Int J Prod Res, vol. 42, no. 19, pp. 4211–4220, Oct. 2004, doi: 10.1080/00207540410001711863.

9. [9] S. H. Chung, Y. T. Tai, and W. L. Pearn, “Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes,” Int J Prod Res, vol. 47, no. 18, pp. 5109–5128, Sep. 2009, doi: 10.1080/00207540802010807.
10. [10] B. Cheng, S. Yang, X. Hu, and B. Chen, “Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes,” Appl Math Model, vol. 36, no. 7, pp. 3161–3167, Jul. 2012, doi: 10.1016/j.apm.2011.09.061.
11. [11] L. Mönch, H. Balasubramanian, J. W. Fowler, and M. E. Pfund, “Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times,” Comput Oper Res, vol. 32, no. 11, pp. 2731–2750, Nov. 2005, doi: 10.1016/j.cor.2004.04.001.
12. [12] İ. Muter, “Exact algorithms to minimize makespan on single and parallel batch processing machines,” Eur J Oper Res, vol. 285, no. 2, pp. 470–483, Sep. 2020, doi: 10.1016/j.ejor.2020.01.065.
13. [13] C.-Y. Lee, “Minimizing makespan on a single batch processing machine with dynamic job arrivals,” Int J Prod Res, vol. 37, no. 1, pp. 219–236, Jan. 1999, doi: 10.1080/002075499192020.
14. [14] L. Dupont and C. Dhaenens-Flipo, “Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure,” Comput Oper Res, vol. 29, no. 7, pp. 807–819, Jun. 2002, doi: 10.1016/S0305-0548(00)00078-2.
15. [15] J. E. C. Arroyo and J. Y.-T. Leung, “Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times,” Comput Oper Res, vol. 78, pp. 117–128, Feb. 2017, doi: 10.1016/j.cor.2016.08.015.
16. [16] Z. Jia, C. Wang, and J. Y.-T. Leung, “An ACO algorithm for makespan minimization in parallel batch machines with non- identical job sizes and incompatible job families,” Appl Soft Comput, vol. 38, pp. 395–404, Jan. 2016, doi: 10.1016/j.asoc.2015.09.056.
17. [17] X. Li and K. Zhang, “Single batch processing machine scheduling with two-dimensional bin packing constraints,” Int J Prod Econ, vol. 196, pp. 113–121, Feb. 2018, doi: 10.1016/j.ijpe.2017.11.015.
18. [18] J. A. Bennell, L. Soon Lee, and C. N. Potts, “A genetic algorithm for two-dimensional bin packing with due dates,” Int J Prod Econ, vol. 145, no. 2, pp. 547–560, Oct. 2013, doi: 10.1016/j.ijpe.2013.04.040.
19. [19] S. Polyakovskiy and R. M’Hallah, “A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates,” Eur J Oper Res, vol. 266, no. 3, pp. 819–839, May 2018, doi: 10.1016/j.ejor.2017.10.046.
20. [20] F. Tercinet, E. Néron, and C. Lenté, “Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem,” 4OR, vol. 4, no. 4, pp. 297–317, Nov. 2006, doi: 10.1007/s10288-006-0017-1.
21. [21] N. Xie, S. Zheng, and Q. Wu, “Two-dimensional packing algorithm for autoclave molding scheduling of aeronautical composite materials production,” Comput Ind Eng, vol. 146, p. 106599, Aug. 2020, doi: 10.1016/j.cie.2020.106599.
22. [22] A. Lodi, S. Martello, and M. Monaci, “Two-dimensional packing problems: A survey,” Eur J Oper Res, vol. 141, no. 2, pp. 241–252, Sep. 2002, doi: 10.1016/S0377-2217(02)00123-6.
23. [23] S. Zhou, Z. Jia, M. Jin, and N. Du, “Minimizing makespan on parallel batch processing machines with two-dimensional rectangular jobs,” Comput Ind Eng, vol. 169, p. 108167, Jul. 2022, doi: 10.1016/j.cie.2022.108167.
24. [24] X. Zhang, M. Shan, and J. Zeng, “Parallel Batch Processing Machine Scheduling Under Two-Dimensional Bin-Packing Constraints,” IEEE Trans Reliab, 2022, doi: 10.1109/TR.2022.3201333.
25. [25] S. Zhou, M. Jin, C. Liu, X. Zheng, and H. Chen, “Scheduling a single batch processing machine with non-identical two- dimensional job sizes,” Expert Syst Appl, vol. 201, p. 116907, Sep. 2022, doi: 10.1016/j.eswa.2022.116907.
26. [26] K. Hu, Y. Che, T. S. Ng, and J. Deng, “Unrelated parallel batch processing machine scheduling with time requirements and two-dimensional packing constraints,” Comput Oper Res, vol. 162, p. 106474, Feb. 2024, doi: 10.1016/j.cor.2023.106474.
27. [27] J. O. Berkey and P. Y. Wang, “Two-Dimensional Finite Bin-Packing Algorithms,” Journal of the Operational Research Society, vol. 38, no. 5, pp. 423–429, May 1987, doi: 10.1057/jors.1987.70.
28. [28] S. V. MEHTA and R. UZSOY, “Minimizing total tardiness on a batch processing machine with incompatible job families,” IIE Transactions, vol. 30, no. 2, pp. 165–178, Feb. 1998, doi: 10.1080/07408179808966448.
29. [29] K. Hadj Salem, E. Silva, J. F. Oliveira, and M. A. Carravilla, “Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry,” Eur J Oper Res, vol. 306, no. 2, pp. 549–566, Apr. 2023, doi: 10.1016/j.ejor.2022.08.018.
30. [30] M. Hifi, “Exact algorithms for the guillotine strip cutting/packing problem,” Comput Oper Res, vol. 25, no. 11, pp. 925–940, Nov. 1998, doi: 10.1016/S0305-0548(98)00008-2.
31. [31] A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” Eur J Oper Res, vol. 172, no. 3, pp. 814–837, Aug. 2006, doi: 10.1016/j.ejor.2004.11.016.
32. [32] S. C. H. Leung, D. Zhang, and K. M. Sim, “A two-stage intelligent search algorithm for the two-dimensional strip packing problem,” Eur J Oper Res, vol. 215, no. 1, pp. 57–69, Nov. 2011, doi: 10.1016/j.ejor.2011.06.002.
33. [33] M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura, and H. Nagamochi, “Exact algorithms for the two-dimensional strip packing problem with and without rotations,” Eur J Oper Res, vol. 198, no. 1, pp. 73–83, Oct. 2009, doi: 10.1016/j.ejor.2008.08.020.
34. [34] A. Bekrar, I. Kacem, C. Chu, and C. Sadfi, “An improved heuristic and an exact algorithm for the 2D strip and bin packing problem,” 2010.
35. [35] K. He, Y. Jin, and W. Huang, “Heuristics for two-dimensional strip packing problem with 90 rotations,” Expert Syst Appl, vol. 40, no. 14, pp. 5542–5550, 2013, doi: 10.1016/j.eswa.2013.04.005.
36. [36] P. M. Castro and I. E. Grossmann, “From time representation in scheduling to the solution of strip packing problems,” Comput Chem Eng, vol. 44, pp. 45–57, Sep. 2012, doi: 10.1016/j.compchemeng.2012.05.002.,
37. [37] T. Saraç and B. Tutumlu, “İlişkisiz paralel makine çizelgeleme probleminde eniyi makine sayısının belirlenmesi için bir doğrusal tam,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 37, no. 1, pp. 329–345, 2022, doi: 10.17341/gazimmfd.686683.
38. [38] A. Takan and T. Saraç, “Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 38, no. 2, pp. 1041–1054, 2023, doi: 10.17341/gazimmfd.815942.
39. [39] A. K. Türker and C. Sel, “Sira baǧimli hazirlik operasyonlari için tek ekipli paralel makinalarda çizelgeleme problemine karma yaklaşim,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 26, no. 4, pp. 731–740, 2011.
40. [40] T. Saraç and F. Özçelik, “Çok amaçli ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 38, no. 3, pp. 1953–1966, 2023, doi: 10.17341/gazimmfd.873295.
41. [41] G. Bektur and T. Saraç, “İki paralel enjeksiyon makinasinin kreyn kisiti altinda çizelgelenmesi,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 31, no. 4, pp. 903–911, 2016, doi: 10.17341/gazimmfd.278445.
42. [42] A. Furugi, “Makine uygunluk kısıtlaması ve sıra bağımlı kurulum süresi ile özdeş olmayan paralel makine çizelgeleme,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 36, no. 3, pp. 1539–1549, 2021, doi: 10.17341/gazimmfd.806641.
43. [43] O. A. Arık, “Paralel enjeksiyon makine çizelgeleme problemi için lagrange gevşetme temelli bir algoritma,” Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 40, no. 1, pp. 277–286, 2024, doi: 10.17341/gazimmfd.1425180.
44. [44] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Sixth Edition. 2022. doi: 10.1007/978-3-031-05921-6.
45. [45] E.G. Coffman Jr, M.R. Garey, D.S. Johnson, R.E. Tarjan.” Performance bounds for level-oriented two-dimensional packing algorithms,” SIAM Journal on Computing, vol. 9, pp. 808--826, 1980.
46. [46] O. A. Arık, M. Schutten, E. Topan. "Weighted earliness/tardiness parallel machine scheduling problem with a common due date,." Expert systems with applications vol.187: 115916, 2022.
47. [47] S., Ropke, D., Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”, Transportation science, 40(4), 455-472.
48. [48] A., Kaveh, A. Dadras, “A novel meta-heuristic optimization algorithm: Thermal exchange optimization”, Advances in Engineering Software, 110, 69–84.
49. [49] S., Aslan, Bir halı üretim işletmesinde dokuma tezgahlarının iki boyutlu şerit paketleme problemi kısıtları kullanılarak çizelgelenmesi, Yüksek Lisans Tezi, Nuh Naci Yazgan Üniversitesi, Fen Bilimleri Enstitüsü, Kayseri, 2024.