ATÖLYE TİPİ ÇİZELGELEME PROBLEMİ: MATEMATİKSEL MODEL VE GENETİK ALGORİTMA YAKLAŞIMI

Abstract

Çalışma, atölye tipi çizelgeleme problemini uygulama odaklı bir bakış açısıyla ele almakta ve literatürde görece sınırlı incelenen sıra-bağımlı hazırlık sürelerini dikkate alarak gerçekçi üretim kısıtlarını içeren bütünleşik bir çözüm çerçevesi sunmaktadır. Fabrikanın gerçek üretim yapısını yansıtan karma tam sayılı doğrusal programlama (MILP) modelleri geliştirilmiş ve küçük ile orta ölçekli test problemleri bu modeller aracılığıyla çözülmüştür. Büyük ölçekli problemler için ise evrimsel arama yaklaşımına dayalı, permütasyon temelli bir genetik algoritma (GA) uygulanmıştır. Çalışmanın temel amacı, makineler arasındaki işlem değişikliklerinden kaynaklanan hazırlık sürelerinin neden olduğu sipariş gecikmelerini en aza indirmektir. Elde edilen bulgular, MILP modelinin küçük ve orta ölçekli problemlerde tatmin edici ve optimale yakın çözümler sunduğunu; ancak problem boyutu arttıkça çözüm süresinin belirgin biçimde arttığını ve çözüm etkinliğinin azaldığını göstermektedir. Buna karşılık GA, tüm problem boyutlarında uygulanabilir ve kararlı çözümler üretmiş; özellikle büyük ölçekli örneklerde daha üstün performans sergilemiştir. Gelecek çalışmalarda modelin çok amaçlı yapıya dönüştürülmesi ve GA’nın diğer meta sezgisel yöntemlerle hibrit olarak geliştirilmesi önerilmektedir.

Keywords

• Atölye Tipi Çizelgeleme
• Genetik Algoritma
• Makine Hazırlık Süresi
• Matematiksel Modelleme
• Sıra Bağımlı Hazırlık Süresi

JOB SHOP SCHEDULING PROBLEM IN A MARBLE FACTORY: MATHEMATICAL MODEL AND GENETIC ALGORITHM APPROACH

Abstract

The study addresses the job shop scheduling problem through an application-oriented perspective and proposes an integrated solution framework that incorporates realistic production constraints by considering sequence-dependent setup times, which are relatively limited in the literature. Mixed Integer Linear Programming (MILP) models reflecting the actual production structure of the factory were developed, and small- and medium-sized test problems were solved using these models. For large-scale instances, a permutation-based Genetic Algorithm (GA) supported by evolutionary search was applied. The primary objective is to minimize order delays caused by setup times arising from machine changeovers. The results indicate that the MILP model provides satisfactory and near-optimal solutions for small and medium-sized problems; however, as the problem size increases, computational time rises significantly and solution efficiency decreases. In contrast, the GA generates feasible and stable solutions for all problem sizes and demonstrates superior performance, particularly in large-scale cases. Future studies may extend the model to a multi-objective structure and enhance the GA through hybridization with other metaheuristic approaches.

Keywords

• Job Shop Scheduling
• Genetic Algorithm
• Mathematical Modeling
• Machine Setup Time
• Order Based Setup Time

References

1. Asano, M., Ohta, H., 2002. A heuristic for job shop scheduling to minimize total weighted tardiness. Computers & Industrial Engineering, 42 (2-4), 137-147.
2. Bahşi, N., 2025. Siparişe dayalı atölye tipi üretim için toplam gecikmeyi enazlayan sezgisel bir çözüm önerisi. (Tez No. 952183) Yüksek Lisans Tezi. Süleyman Demirel Üniversitesi, Ulusal Tez Merkezi.
3. Biegel, J.E., Davern, J.J., 1990. Genetic algorithms and job shop scheduling. Computers & Industrial Engineering, 19 (1-4), 81-91.
4. Bowman, E.H., 1959. The schedule-sequencing problem. Operations Research, 7 (5), 621-624.
5. Cheung, W., Zhou, H., 2001. Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Annals of Operations Research, 107, 65-81.
6. Gölcük, İ., Baykasoğlu, A., Madenoğlu, F.S., 2014. Kril sürüsü algoritması ile atölye çizelgeleme. Dokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisi, 16 (48), 61-75.
7. Graves, S.C., 1981. A review of production scheduling. Operations Research, 29 (4), 646-675.
8. Halat, K., Bashirzadeh, R., 2015. Concurrent scheduling of manufacturing cells considering sequence-dependent family setup times and intercellular transportation times. The International Journal of Advanced Manufacturing Technology, 77, 1907-1915.

9. Herrmann, J.W., Lee, C.Y., Hinchman, J., 1995. Global job shop scheduling with a genetic algorithm. Production and Operations Management, 4 (1), 30-45.
10. Kaya, S., Fığlalı, N., 2018. Çok amaçlı esnek atölye tipi çizelgeleme problemlerinin çözümünde meta sezgisel yöntemlerin kullanımı. Harran Üniversitesi Mühendislik Dergisi, 3 (3), 222-233.
11. Kharbeche, M., Haouari, M., 2013. MIP models for minimizing total tardiness in a two-machine flow shop. Journal of the Operational Research Society, 64 (5), 690-707.
12. Kramer, O., 2017. Genetic algorithm essentials. Switzerland: Springer Nature.
13. Kumar, N.H., Srinivasan, G., 1996. A genetic algorithm for job shop scheduling: A case study. Computers in Industry, 31 (2), 155-160.
14. Liu, A., Luh, P.B., Yan, B., Bragin, M.A., 2023. A novel integer linear programming formulation for job-shop scheduling problems. IEEE Robotics and Automation Letters, 6 (3), 5937-5944.
15. Liu, H., Abraham, A., Wang, Z., 2009. A multi-swarm approach to multi-objective flexible job-shop scheduling problems. Fundamenta Informaticae, 95 (4), 465-489.
16. Manne, A.S., 1960. On the job-shop scheduling problem. Operations Research, 8 (2), 219-223.Maxwell, W.L., 1964. The scheduling of single machine systems: A review. The International Journal of Production Research, 3 (3), 177-199.
17. Momenikorbekandi, A., Kalganova, T., 2025. Intelligent scheduling methods for optimisation of job shop scheduling problems in the manufacturing sector: A systematic review. Electronics, 14 (8), 1663.
18. Mousakhani, M., 2013. Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. International Journal of Production Research, 51 (12), 3476-3487.
19. Mousavipour, S., Farughi, H., Ahmadizar, F., 2019. A job shop scheduling problem with sequence-dependent setup times considering position-based learning effects and availability constraints. International Journal of Industrial Engineering & Production Research, 30 (3), 329-340.
20. Naderi, B., Fatemi Ghomi, S.M.T., Aminnayeri, M., Zandieh, M., 2011. A study on open shop scheduling to minimise total tardiness. International Journal of Production Research, 49 (15), 4657-4678.
21. Naderi, B., Ruiz, R., Roshanaei, V., 2023. Mixed-integer programming vs. constraint programming for shop scheduling problems: New results and outlook. INFORMS Journal on Computing, 35 (4), 817-843.
22. Naderi, B., Zandieh, M., Fatemi Ghomi, S.M.T., 2009. Scheduling sequence-dependent setup time job shops with preventive maintenance. The International Journal of Advanced Manufacturing Technology, 43, 170-181.
23. Nakamura, T., Ohuchi, A., Kaji, I., 1987. Markov chain analysis of a single-stage transfer-type automated manufacturing system two-machine parallel system. Electronics and Communications in Japan, 70 (4), 35-44.
24. Omar, M.K., Teo, S.C., Suppiah, Y., 2007. Scheduling with setup considerations: An MIP approach. Levner, E. (Edt.), multiprocessor scheduling, içinde (s. 241-254). Vienna: I-TECH.
25. Ono, I., Yamamura, M., Kobayashi, S., 1996. A genetic algorithm for job-shop scheduling problems using job-based order crossover. Proceedings of IEEE International Conference on Evolutionary Computation, 547-552.
26. Pinedo, M.L., 2008. Scheduling theory, algorithms and systems. New York: Prentice Hall.
27. Schutten, J.M., 1998. Practical job shop scheduling. Annals of Operations Research, 83, 161-178.
28. Scrich, C.R., Armentano, V.A., Laguna, M., 2004. Tardiness minimization in a flexible job shop: A tabu search approach. Journal of Intelligent Manufacturing, 15, 103-115.
29. Servranckx, T., Verbanck, T., Song, J., Vanhoucke, M., 2025. A genetic algorithm for seafood processing with flexible flow shops and sequence-dependent setups. Flexible Services and Manufacturing Journal, 37, 1-32.
30. Thiagarajan, S., Rajendran, C., 2005. Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs. Computers & Industrial Engineering, 49 (4), 463-503.
31. Wagner, H.M., 1959. An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, 6 (2), 131-140.
32. Wang, Y., Zhu, Q., 2021. A hybrid genetic algorithm for flexible job shop scheduling problem with sequence-dependent  setup times and job lag times. IEEE Access, 9, 93483-93497.
33. Wisittipanich, W., Kachitvichyanukul, V., 2011. Differential evolution algorithm for job shop scheduling problem. Industrial  Engineering and Management Systems, 10 (3), 203-208.
34. Wittrock, R.J., 1988. An adaptable scheduling algorithm for flexible flow lines. Operations Research, 36 (3), 445-453.
35. Xu, M., Mei, Y., Zhang, F., Zhang, M., 2025. Learn to optimise for job shop scheduling: A survey with comparison between  genetic programming and reinforcement learning. Artificial Intelligence Review, 58 (6), 1-53.
36. Yazdani, M., Aleti, A., Khalili, S.M., Jolai, F., 2017. Optimizing the sum of maximum earliness and tardiness of the job shop  scheduling problem. Computers & Industrial Engineering, 107, 12-24.
37. Ying, K.C., Pourhejazy, P., Lin, Z.R., 2025. Scheduling with sequence-dependent setup times in short-term production  planning: A main path analysis-based review. Operations Research Perspectives, 13, 100348.
38. Zhao, L., Cheng, W., Meng, L., Zhang, C., Ren, Y., Zhang, B., Duan, P., 2025. MILP modeling and optimization of flexible  job shop scheduling problem with preventive maintenance. Computers & Industrial Engineering, 201, 110861.