Two new parameter proposals for variable neighborhood descent algorithm to minimize Cmax in machine scheduling problem

Öz

Scheduling can be defined as the assignment of jobs to machines that will be processed under certain constraints and measurements. Different scheduling problems arise when creating schedules and assigning jobs to machines. The problem of interest in this study is the Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSPST), which is classified as NP-hard. The objective of the problem is to minimize the makespan (Cmax). In UPMSPST, machines have different processing times for jobs and there are machine-dependent setup times between jobs. Exact solution methods are not sufficient for solving the UPMSPST and many metaheuristics have been proposed by researchers to find approximate solutions. The aim of this paper is to propose two new parameters for solving the UPMSPST with the Variable Neighborhood Descent (VND) algorithm, which is a single-solution metaheuristic algorithm, in order to find better solutions. The proposed parameters are tested in four different scenarios and the results of the best parameter configuration are given. The results show that the proposed new parameters are effective in improving the existing solution.

Anahtar Kelimeler

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

Kaynakça

1. 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 (2004): 177-187. https://scholar.google.com/scholar_lookup?title=Scheduling%20to%20minimize%20makespan%20on%20unrela ted%20parallel%20machines%20with%20sequence%20dependent%20setup%20times&publication_year=2004 &author=A.%20Al-Salem
2. Anagnostopoulos, G. C., & Rabadi, G. (2002, June). A simulated annealing algorithm for the unrelated parallel machine scheduling problem. In Proceedings of the 5th Biannual world automation congress (Vol. 14, pp. 115- 120). IEEE. https://doi.org/10.1109/wac.2002.1049430
3. Arnaout, J. P. (2020). “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. https://doi.org/10.1007/s10479-019-03138-w
4. Arnaout, J. P., Musa, R., & Rabadi, G. (2014). “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. https://doi.org/10.1007/s10845-012-0672-3 Kılıç, Organ JTOM (9)1,36-46,2025 45
5. Arnaout, J. P., Rabadi, G., & Musa, R. (2010). “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. https://doi.org/10.1007/s10845-009-0246-1
6. Baker, K. R., & Trietsch, D. (2018). Principles of sequencing and scheduling. John Wiley & Sons. https://doi.org/10.1002/9781119262602
7. Berthier, A., Yalaoui, A., Chehade, H., Yalaoui, F., Amodeo, L., & Bouillot, C. (2022). “Unrelated parallel machines scheduling with dependent setup times in textile industry.” Computers & Industrial Engineering, 174, 108736. https://doi.org/10.1016/j.cie.2022.108736
8. Chang, P. C., & Chen, S. H. (2011). “Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times.” Applied Soft Computing, 11(1), 1263-1274. https://doi.org/10.1016/j.asoc.2010.03.003

9. Cota, L. P., Guimarães, F. G., de Oliveira, F. B., & Souza, M. J. F. (2017, June). “An adaptive large neighborhood search with learning automata for the unrelated parallel machine scheduling problem.” In 2017 IEEE Congress on Evolutionary Computation (CEC) (pp. 185-192). IEEE. https://doi.org/10.1109/cec.2017.7969312
10. Elyasi, M., Selcuk, Y. S., Özener, O. Ö., & Coban, E. (2024). “Imperialist competitive algorithm for unrelated parallel machine scheduling with sequence-and-machine-dependent setups and compatibility and workload constraints.” Computers & Industrial Engineering, 190, 110086. https://doi.org/10.1016/j.cie.2024.110086
11. Fleszar, K., Charalambous, C., & Hindi, K. S. (2012). “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. https://doi.org/10.1007/s10845-011-0522-8
12. Fonseca, G. H., Figueiroa, G. B., & Toffolo, T. A. (2024). “A fix-and-optimize heuristic for the Unrelated Parallel Machine Scheduling Problem.” Computers & Operations Research, 163, 106504. https://doi.org/10.1016/j.cor.2023.106504
13. Gao, J., Sun, L., & Gen, M. (2008). “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems.” Computers & Operations Research, 35(9), 2892-2907. https://doi.org/10.1016/j.cor.2007.01.001
14. Hansen, P., & Mladenovic, N. (2003). “A tutorial on variable neighborhood search.” Les Cahiers du GERAD ISSN, 711, 2440. https://scispace.com/pdf/a-tutorial-on-variable-neighborhood-search-lq7nrkn4zn.pdf Haupt RL, Haupt SE. Practical Genetic Algorithms. 2nd ed. New York, USA, Wiley, 2004. https://doi.org/10.1002/0471671746
15. Helal, M., Rabadi, G., & Al-Salem, A. (2006). “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. https://www.researchgate.net/publication/228621816_A_tabu_search_algorithm_to_minimize_the_makespan_fo r_the_unrelated_parallel_machines_scheduling_problem_with_setup_times
16. Lin, S. W., Lu, C. C., & Ying, K. C. (2011). “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(1-4), 353-361. https://doi.org/10.1007/s00170-010-2824-y
17. Lin, S. W., & Ying, K. C. (2014). “ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times.” Computers & Operations Research, 51, 172-181. https://doi.org/10.1016/j.cor.2014.05.013
18. Mladenović, N., & Hansen, P. (1997). “Variable neighborhood search.” Computers & operations research, 24(11), 1097-1100. https://doi.org/10.1016/s0305-0548(97)00031-2
19. Muñoz-Díaz, M. L., Escudero-Santana, A., & Lorenzo-Espejo, A. (2024). “Solving an Unrelated Parallel Machines Scheduling Problem with machine-and job-dependent setups and precedence constraints considering Support Machines.” Computers & Operations Research, 163, 106511. https://doi.org/10.1016/j.cor.2023.106511
20. Pinedo, M. L (2018). Scheduling: theory, algorithms, and systems. Springer. https://link.springer.com/book/10.1007/978-0-387-78935-4
21. Rabadi, G., Moraga, R. J., & Al-Salem, A. (2006). “Heuristics for the unrelated parallel machine scheduling problem with setup times.” Journal of Intelligent Manufacturing, 17(1), 85-97. https://doi.org/10.1007/s10845- 005-5514-0
22. Ramos-Figueroa, O., Quiroz-Castellanos, M., Mezura-Montes, E., & Cruz-Ramírez, N. (2023). “An experimental study of grouping mutation operators for the unrelated parallel-machine scheduling problem”. Mathematical and Computational Applications, 28(1), 6. https://doi.org/10.3390/mca28010006
23. Sanati, H., Moslehi, G., & Reisi-Nafchi, M. (2023). “Unrelated parallel machine energy-efficient scheduling considering sequence-dependent setup times and time-of-use electricity tariffs.” EURO Journal on Computational Optimization, 11, 100052. https://doi.org/10.1016/j.ejco.2022.100052
24. Saraç, T., & Özçelik, F. (2023). “A matheuristic algorithm for multi-objective unrelated parallel machine scheduling problem Çok amaçli ilişkisiz paralel makine çizelgeleme problemi için bir matsezgisel algoritma.” Journal of the Faculty of Engineering and Architecture of Gazi University, 38(3). https://doi.org/10.17341/gazimmfd.873295
25. SchedulingResearch. (2022), Accesed 01.09.2022 from www.schedulingresearch.com. Toragay, O., & Pouya, S. (2023). “A Monte Carlo simulation approach to the gap-time relationship in solving the job shop scheduling problem.” Journal of Turkish Operations Management (JTOM), 7(1). https://doi.org/10.56554/jtom.1286288
26. Wang, L., Wang, S., & Zheng, X. (2016). “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. https://doi.org/10.1109/jas.2016.7508797
27. Yilmaz Eroğlu, D., Ozmutlu, H. C., & Ozmutlu, S. (2014). “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. https://doi.org/10.1080/00207543.2014.920966
28. Ying, K. C., Lee, Z. J., & Lin, S. W. (2012). “Makespan minimization for scheduling unrelated parallel machines with setup times.” Journal of Intelligent Manufacturing, 23, 1795-1803. https://doi.org/10.1007/s10845-010-0483-
29. Zhang, L., Deng, Q., Lin, R., Gong, G., & Han, W. (2021). “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. https://doi.org/10.1016/j.eswa.2021.114843