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

Year 2025, Volume: 9 Issue: 1, 36 - 46, 01.07.2025

Günay Kılıç , Arzu Organ

https://doi.org/10.56554/jtom.1515258

Abstract

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.

Keywords

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

Ethical Statement

Bu makale "Sıra bağımlı ilişkisiz paralel makine çizelgeleme problemi için yeni bir sezgisel algoritma önerisi" isimli doktora tezinden üretilmiştir.

References

• 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
• 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
• 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
• 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
• 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
• Baker, K. R., & Trietsch, D. (2018). Principles of sequencing and scheduling. John Wiley & Sons. https://doi.org/10.1002/9781119262602
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Pinedo, M. L (2018). Scheduling: theory, algorithms, and systems. Springer. https://link.springer.com/book/10.1007/978-0-387-78935-4
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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-
• 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