A new neighborhood-based VNS algorithm for unrelated parallel machine scheduling problem with sequence-dependent setup times

Öz

Scheduling involves the allocation of tasks to machines under specific constraints and criteria. As schedules are constructed and jobs are assigned to machines, various scheduling challenges arise. This study focuses on the NP-hard Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSPSDT), where jobs have varying processing times across machines, and setup times between jobs depend on the machine. The objective is to minimize the makespan (Cmax) of the final schedule. Due to its computational complexity, exact methods are ineffective in solving UPMSPSDT efficiently, leading researchers to explore metaheuristic approaches for near-optimal solutions. This study aims to enhance solution quality for UPMSPSDT using the Variable Neighborhood Search (VNS) algorithm, a single-solution metaheuristic. To this end, a novel neighborhood structure is introduced, inspired by the shell-changing behavior of crabs, complementing existing structures in literature. Additionally, three different local search strategies are evaluated based on the makespan values obtained through neighborhood transitions and are applied iteratively using a local search selection strategy. Furthermore, an improved version of a greedy initial solution from the literature is proposed to generate higher-quality starting solutions. The proposed Crab-inspired Neighborhood-based VNS (CNVNS) is tested on a widely used benchmark dataset, and the results are analyzed. Findings indicate that the proposed algorithm outperforms benchmarked approaches in achieving lower Cmax values, demonstrating its effectiveness in solving UPMSPSDT.

Anahtar Kelimeler

• Variable Neighborhood Search
• Metaheuristic
• Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times

Sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir komşuluk tabanlı DKA algoritması

Öz

Çizelgeleme, belirli kısıtlar ve kriterler doğrultusunda görevlerin makinelere tahsis edilmesi sürecidir. Çizelgeler oluşturulup işler makinelere atandıkça çeşitli çizelgeleme problemleri ortaya çıkmaktadır. Bu çalışma, işler farklı makinelere göre değişen işlem sürelerine sahipken ve işler arasındaki hazırlık süreleri makineye bağlı olarak değişirken, nihai tamamlanma süresinin (Cmax) en aza indirilmesini amaçlayan Sıra Bağımlı Hazırlık Süreli İlişkili Olmayan Paralel Makine Çizelgeleme Problemi (UPMSPSDT) üzerine odaklanmaktadır. Hesaplama açısından NP-zor bir problem olması nedeniyle, kesin yöntemler UPMSPSDT’yi etkin bir şekilde çözmede yetersiz kalmakta ve bu nedenle araştırmacılar yaklaşık çözümler elde etmek için metasezgisel yaklaşımlara yönelmektedir. Bu çalışmada, Değişken Komşuluk Arama (DKA) algoritması kullanılarak UPMSPSDT için daha kaliteli çözümler elde edilmesi amaçlanmaktadır. Bu doğrultuda, yengeçlerin kabuk değiştirme davranışından esinlenen ve literatürde mevcut komşuluk yapılarını tamamlayıcı nitelikte yeni bir komşuluk yapısı önerilmektedir. Ayrıca, üç farklı yerel arama yöntemi, komşuluk değişimlerinden elde edilen tamamlanma süresi (Cmax) değerlerine göre değerlendirilmiş ve yerel arama seçim stratejisi kullanılarak iteratif olarak uygulanmıştır. Bunun yanı sıra, literatürdeki açgözlü (greedy) başlangıç çözümüne yönelik bir iyileştirme önerilerek, daha yüksek kaliteli başlangıç çözümlerinin elde edilmesi hedeflenmiştir. Önerilen Yengeç İlhamlı Komşuluk Tabanlı DKA (CNVNS) algoritması, yaygın olarak kullanılan bir test veri seti üzerinde değerlendirilmiş ve sonuçlar analiz edilmiştir. Elde edilen bulgular, önerilen algoritmanın karşılaştırıldığı diğer yaklaşımlara kıyasla daha düşük Cmax değerleri ürettiğini ve UPMSPSDT çözümünde etkinliğini ortaya koyduğunu göstermektedir.

Anahtar Kelimeler

• Değişken Komşuluk Arama
• Metasezgisel
• Sıra Bağımlı Hazırlık Süreli İlişkisiz Paralel Makine Çizelgeleme

Kaynakça

1. [1] Pinedo ML, Scheduling: Theory, Algorithms, and Systems. 5th ed. USA, Springer, 2016.
2. [2] Baker KR, Trietsch D. Principles of Sequencing and Scheduling. 2nd ed. USA, John Wiley & Sons, 2019.
3. [3] Lin SW, Lu CC, Ying KC. “Minimization of total tardiness on unrelated parallel machines with sequence-and machine-dependent setup times under due date constraints”. The International Journal of Advanced Manufacturing Technology, 53, 353-361, 2011.
4. [4] Arnaout JP. “A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times”. Annals of Operations Research, 285(1), 273-293, 2020.
5. [5] Sel Ç, Hamzadayı A. “A simulated annealing approach-based simulation-optimisation to the dynamic job-shop scheduling problem”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 24(4), 665-674, 2018.
6. [6] Al-Salem A. "Scheduling to minimize makespan on unrelated parallel machines with sequence dependent setup times". Engineering Journal of the University of Qatar, 17(1), 177-187, 2004.
7. [7] Helal M, Rabadi G, Al-Salem A. “A tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times”. International Journal of Operations Research, 3(3), 182-192, 2006.
8. [8] Rabadi G, Moraga RJ, Al-Salem A. “Heuristics for the unrelated parallel machine scheduling problem with setup times”. Journal of Intelligent Manufacturing, 17(1), 85-97, 2006.

9. [9] Arnaout JP, Rabadi G, Musa R. “A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times”. Journal of Intelligent Manufacturing, 21(6), 693-701, 2010.
10. [10] Chang PC, Chen SH. “Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times”. Applied Soft Computing, 11(1), 1263-1274, 2011.
11. [11] Ying KC, Lin SW. “Unrelated parallel machine scheduling with sequence-and machine-dependent setup times and due date constraints”. International Journal of Innovative Computing, Information and Control, 8(5), 3279-3297, 2012.
12. [12] Fleszar K, Charalambous C, Hindi KS. “A variable neighborhood descent heuristic for the problem of makespan minimisation on unrelated parallel machines with setup times”. Journal of Intelligent Manufacturing, 23(5), 1949-1958, 2012.
13. [13] Lin SW, Ying KC. “ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times”. Computers & Operations Research, 51, 172-181, 2014.
14. [14] Arnaout JP, Musa R, Rabadi G. “A two-stage Ant Colony optimization algorithm to minimize the makespan on unrelated parallel machines-part II: enhancements and experimentations”. Journal of Intelligent Manufacturing, 25(1), 43-53, 2014.
15. [15] Yilmaz Eroğlu D, Ozmutlu HC, Ozmutlu S. “Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times”. International Journal of Production Research, 52(19), 5841-5856, 2014.
16. [16] Cota LP, Guimarães FG, de Oliveira FB, Souza MJF. “An adaptive large neighborhood search with learning automata for the unrelated parallel machine scheduling problem”. IEEE Congress on Evolutionary Computation, San Sebastián, Spain, 5-8 June 2017.
17. [17] De Abreu LR, de Athayde Prata B. “A genetic algorithm with neighborhood search procedures for unrelated parallel machine scheduling problem with sequence-dependent setup times”. Journal of Modelling in Management, 15(3), 809-828, 2020.
18. [18] Arnaout JP. “A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times”. Annals of Operations Research, 285(1), 273-293, 2020.
19. [19] Zhang L, Deng Q, Lin R, Gong G, Han W. “A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect”. Expert Systems with Applications, 175, 114843, 2021.
20. [20] Berthier A, Yalaoui A, Chehade H, Yalaoui F, Amodeo L, Bouillot C. “Unrelated parallel machines scheduling with dependent setup times in textile industry”. Computers & Industrial Engineering, 174, 108736, 2022.
21. [21] Sanati H, Moslehi G, Reisi-Nafchi M. “Unrelated parallel machine energy-efficient scheduling considering sequence-dependent setup times and time-of-use electricity tariffs”. EURO Journal on Computational Optimization, 11, 100052, 2023.
22. [22] Sarac T, Ozcelik F. “A matheuristic algorithm for multi-objective unrelated parallel machine scheduling problem”. Journal of the Faculty of Engineering and Architecture of Gazi University, 38(3), 1953-1966, 2023.
23. [23] Ramos-Figueroa, O, Quiroz-Castellanos M, Mezura-Montes E, Cruz-Ramirez N. “An experimental study of grouping mutation operators for the unrelated parallelmachine scheduling problem”. Mathematical and Computational Applications, 28(1), 6, 2023.
24. [24] Elyasi M, Selcuk YS, Özener OÖ, Coban, E. “Imperialist competitive algorithm¨ for unrelated parallel machine scheduling with sequence-and-machine-dependent setups and compatibility and workload constraints”. Computers & Industrial Engineering, 190, 110086, 2024.
25. [25] Fonseca GH, Figueiroa GB, Toffolo TA. “A fix-and-optimize heuristic for the unrelated parallel machine scheduling problem”. Computers & Operations Research, 163, 106504, 2024.
26. [26] Munoz-Diaz ML, Escudero-Santana A, Lorenzo-Espejo A. “Solving an unrelated parallel machines scheduling problem with machine-and job-dependent setups and precedence constraints considering support machines”. Computers & Operations Research, 163, 106511, 2024.
27. [27] Moser M, Musliu N, Schaerf A, Winter F. “Exact and metaheuristic approaches for unrelated parallel machine scheduling”. Journal of Scheduling, 25(5), 507-534, 2022.
28. [28] Yunusoglu P, Topaloglu Yildiz S. “Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times”. International Journal of Production Research, 60(7), 2212-2229, 2022.
29. [29] Avgerinos I, Mourtos I, Vatikiotis S, Zois G. “Weighted tardiness minimisation for unrelated machines with sequence-dependent and resource-constrained setups”. International Journal of Production Research, 62(1-2), 359-379, 2024.
30. [30] Geurtsen M, Adan J, Akçay A. “Integrated maintenance and production scheduling for unrelated parallel machines with setup times”. Flexible Services and Manufacturing Journal, 36 ,1046-1079, 2023.
31. [31] Khadivi M, Abbasi M, Charter T, Najjaran H. “A mathematical model for simultaneous personnel shift planning and unrelated parallel machine scheduling”. https://doi.org/10.48550/arXiv.2402.15670
32. [32] Antunes AR, Matos MA, Rocha AMA, Costa LA, Varela LR. “A statistical comparison of metaheuristics for unrelated parallel machine scheduling problems with setup times”. Mathematics, 10(14), 2431, 2022.
33. [33] Xie F, Li K, Chen J, Xiao W, Zhou T. “An adaptive large neighborhood search for unrelated parallel machine scheduling with setup times and delivery times”. Computers & Operations Research, 177, 106976, 2025.
34. [34] Wang L, Wang S, Zheng X. “A hybrid estimation of distribution algorithm for unrelated parallel machine scheduling with sequence-dependent setup times”. IEEE/CAA Journal of Automatica Sinica, 3(3), 235-246, 2016.
35. [35] Chase ID, Weissburg M, Dewitt TH. “The vacancy chain process: a new mechanism of resource distribution in animals with application to hermit crabs”. Animal behaviour, 36(5), 1265-1274, 1988.
36. [36] Rotjan RD, Chabot JR, Lewis SM, “Social context of shell acquisition in Coenobita clypeatus hermit crabs”. Behavioral Ecology, 21(3), 639-646, 2010.
37. [37] Murali GB, Biswal BB, Deepak BBVL, Rout A, Mohanta GB. “A New Crab Shell Search Algorithm for Optimal Assembly Sequence Generation”. 9th Annual Information Technology, Electromechanical Engineering and Microelectronics Conference, United States, 13-15 March 2019.
38. [38] Topaloğlu D, Polat O, Kalaycı CB. “Çok kompartımanlı heterojen filolu zaman pencereli araç rotalama probleminin çözümü için sezgisel algoritmalar”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 29(8), 870-884, 2023.
39. [39] Hansen P, Mladenovic N. Developments of Variable Neighborhood Search. Editors: Ribeiro CC, Hansen P. Essays and Surveys in Metaheuristics, 415–439, Boston, MA, Springer, 2002.
40. [40] SVC. “Scheduling Virtual Center”. http://schedulingresearch.com (01.09.2022).
41. [41] Jiang Z, Chen, Y, Li X, Li B. “A heuristic optimization approach for multi-vehicle and one-cargo green transportation scheduling in shipbuilding”. Advanced Engineering Informatics, 49, 101306, 2021.
42. [42] Beiranvand V, Hare W, Lucet Y. “Best practices for comparing optimization algorithms”. Optimization and Engineering, 18, 815-848, 2017.