Capacity Balancing and Variation Minimization in Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: A Mathematical Model and Matheuristic Approach

Year 2025, Volume: 13 Issue: 3

Merhad Ay

https://doi.org/10.29109/gujsc.1598698

Abstract

In this study, a scheduling problem for unrelated parallel machines with sequence-dependent setup times, specifically in the context of tire production, is addressed. To solve this problem, a mathematical model and genetic algorithm-based matheuristic approaches have been developed. While the mathematical model provides accurate and effective solutions for small and medium scale problems, it exhibits limitations in time-constrained applications due to increased solution times for large-scale problems. In the study, two alternative matheuristic algorithms employing different crossover operators are proposed, and their ability to achieve near-optimal solutions for large-scale problems in short periods has been tested. Additionally, the classical random mutation operator was modified into a constrained random mutation operator tailored to the problem. Experimental results demonstrate that the proposed matheuristic algorithms significantly reduce solution times compared to the mathematical model, with the MA1 algorithm showing superior performance in terms of solution quality. This study offers substantial advantages in solving real-world problems by improving both solution time and quality. In the proposed matheuristic algorithm, the problem-specific chromosome structure, the initialization method for the initial population, and the constrained random mutation operator provide significant contributions to the literature for solving similar problems.

Keywords

Parallel Machine Scheduling, Matheuristic, Optimization, Capacity Balancing

Sıra Bağımlı Hazırlık Süreli İlişkisiz Paralel Makine Çizelgelemede Kapasite Dengeleme ve Varyasyon Minimizasyonu: Matematiksel Model ve Matsezgisel Yaklaşım

Abstract

Bu çalışmada, sıra bağımlı hazırlık sürelerine sahip özdeş olmayan paralel makineler için lastik üretimi özelinde bir çizelgeleme problemi ele alınmış ve bu probleme yönelik bir matematiksel model ile genetik algoritma tabanlı matsezgisel yöntemler geliştirilmiştir. Matematiksel model, küçük ve orta ölçekli problemlerde etkin ve doğru çözümler sunarken, büyük ölçekli problemlerde çözüm süresinin artması nedeniyle zaman kısıtlı uygulamalarda sınırlamalar göstermektedir. Çalışmada iki farklı çaprazlama operatörünün kullanıldığı iki alternatif matsezgisel algoritma önerilmektedir ve bu algoritmaların büyük problemlerde kısa sürelerde optimuma yakın sonuçlar elde edebileceği test edilmiştir. Ayrıca, mutasyon aşamasında klasik rastgele mutasyon operatörü, probleme özgü olarak modifiye edilerek sınırlandırılmış rastgele mutasyon operatörü olarak kullanılmıştır. Deneysel sonuçlar, önerilen matsezgisel algoritmaların matematiksel modele kıyasla çok daha kısa sürelerde çözüm sağladığını ve MA1 algoritmasının çözüm kalitesi açısından iyi performans sergilediğini göstermektedir. Çalışma, çözüm süresini ve kalitesi açısından gerçek hayat problemlerinin çözümünde önemli avantajlar sunmaktadır. Önerilen matsezgisel algoritmada, probleme özgü olarak tasarlanan kromozom yapısı, başlangıç popülasyonu oluşturma yöntemi ve sınırlandırılmış rastgele mutasyon operatörü, benzer problemlerin çözümüne yönelik literatüre önemli katkılar sunmaktadır.

Keywords

Paralel Makine Çizelgeleme, Matsezgisel, Optimizasyon, Kapasite Dengeleme

References

• [1] Lin, Y.-K., Pfund, M., & Fowler, J. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Computers & Operations Research, 38(6), 901-916.
• [2] Su, L. (2009). Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system. Computers & Operations Research, 36(2), 461-471.
• [3] Kongsri, P., & Buddhakulsomsiri, J. (2020). A Mixed Integer Programming Model for Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Time to Minimize Makespan and Total Tardiness. 2020 IEEE 7th International Conference on Industrial Engineering and Applications (ICIEA), 605-609.
• [4] Diana, R. O. M., Souza, S. R., & Wanner, E. (2021). A robust multi-response VNS-aiNet approach for solving scheduling problems under unrelated parallel machines environments. Expert Systems with Applications, 182, 115140.
• [5] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(11), 3224-3230.
• [6] Akyol, E., & Saraç, T. (2017). Paralel makina çizelgeleme problemi için bir karma tamsayılı programlama modeli: ortak kaynak kullanımı. Gazi University Journal of Science Part C: Design and Technology, 5(3), 109-126.
• [7] Safaei, S., Naderi, R., Sohrabi, A., & Hatami, A. (2015). Scheduling of unrelated parallel machines using two multi-objective genetic algorithms with sequence-dependent setup times. International Journal of Advanced Design and Manufacturing Technology, 8, 11-22.
• [8] Yepes-Borrero, J. C., Perea, F., Ruiz, R., & Villa, F. (2020). Bi-objective parallel machine scheduling with additional resources during setups. European Journal of Operational Research, 292(2), 443-455.
• [9] Ji, B., Zhang, S., Yu, S. S., & Zhang, D. (2023). An enhanced adaptive large neighborhood search for unrelated parallel machine scheduling with sequence dependent setup times. IEEE Access.
• [10] Ezugwu, A. (2021). Advanced discrete firefly algorithm with adaptive mutation‐based neighborhood search for scheduling unrelated parallel machines with sequence‐dependent setup times. International Journal of Intelligent Systems, 37(3), 4612-4653.
• [11] Haddad, M. N., Coelho, I. M., Souza, M., Ochi, L., Santos, H., & Martins, A. X. (2012). GARP: A new genetic algorithm for the unrelated parallel machine scheduling problem with setup times. 31st International Conference of the Chilean Computer Science Society, 152-160.
• [12] Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211(3), 612-622.
• [13] Özçelik, F., & Saraç, T. (2022). Kullanılamayan Zaman Dilimlerinin ve Sıra Bağımlı Hazırlık Sürelerinin Olduğu Paralel Makina Çizelgeleme Problemi. Gazi University Journal of Science Part C: Design and Technology, 10(3), 588-600.
• [14] Zeidi, J. R., & Mohammad Hosseini, S. (2015). Scheduling unrelated parallel machines with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 81(1-4), 1487-1496.
• [15] Kim, J., & Kim, H.-J. (2020). Parallel machine scheduling with multiple processing alternatives and sequence-dependent setup times. International Journal of Production Research, 59(18), 5438-5453.
• [16] Antunes, A., Matos, M. A., Rocha, A. M., Costa, L., & Varela, L. (2022). A statistical comparison of metaheuristics for unrelated parallel machine scheduling problems with setup times. Mathematics.
• [17] Chang, Y.-C., Chang, K.-H., & Zheng, C.-P. (2022). Application of a non-dominated sorting genetic algorithm to solve a bi-objective scheduling problem regarding printed circuit boards. Mathematics.
• [18] Bektur, G., & Saraç, T. (2019). A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Journal of Industrial and Management Optimization, 15(3), 845-864.
• [19] Bozorgirad, M. A., & Logendran, R. (2012). Sequence-dependent group scheduling problem on unrelated-parallel machines. International Journal of Production Economics, 140(2), 844-853.
• [20] Fanjul-Peyro, L., Ruiz, R., & Pérez, Á. (2019). Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times. Computers & Operations Research, 102, 199-213.
• [21] Thiruvady, D., Blum, C., & Ernst, A. T. (2020). Solution merging in matheuristics for resource constrained job scheduling. Algorithms, 13(10), 256.
• [22] Maaranen, H., Miettinen, K., & Penttinen, A. (2007). On initial populations of a genetic algorithm for continuous optimization problems. Journal of Global Optimization, 37(3), 405-436.
• [23] Cerf, R. (2015). The quasispecies regime for the simple genetic algorithm with roulette wheel selection. Advances in Applied Probability, 49(4), 903-926.
• [24] Semenkin, E., & Semenkina, M. (2012). Self-configuring genetic algorithm with modified uniform crossover operator. Lecture Notes in Computer Science, 7431, 414-421.
• [25] Zainuddin, F. A., Abd Samad, M. F., & Tunggal, D. (2020). A review of crossover methods and problem representation of genetic algorithm in recent engineering applications. International Journal of Advanced Science and Technology, 29(6s), 759-769.
• [26] Soni, N., & Kumar, T. (2014). Study of various mutation operators in genetic algorithms. International Journal of Computer Science and Information Technologies, 5(3), 4519-4521.
• [27] Rajakumar, B. R. (2013). Static and adaptive mutation techniques for genetic algorithm: a systematic comparative analysis. International Journal of Computational Science and Engineering, 8(2), 180-193.