KaydedilenlerDerginizi ekleyin

Dergiler / Journal of Turkish Operations Management / 2026 / Cilt: 9 Sayı: 1

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

Günay Kılıç(PAMUKKALE ÜNİVERSİTESİ, REKTÖRLÜK)0000-0003-2236-7535
Arzu Organ(PAMUKKALE ÜNİVERSİTESİ)0000-0002-2400-4343
Sayfa
36–46
Yayın Tarihi
2025-07-01
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

The results show that the proposed new parameters are effective in improving the existing solution.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:Scheduling can be defined as the assignment of jobs to machines that will be processed under certain constraints and measurements.
📊
Temel Bulgular & Veri:Different scheduling problems arise when creating schedules and assigning jobs to machines.
💡
Sonuç & Katkı:The results show that the proposed new parameters are effective in improving the existing solution.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Variable Neighborhood Descent · Metaheuristic · Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times

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.

🔖

Bu Makaleye Atıf Yap

Kılıç, G., Organ, A. (2025). Two new parameter proposals for variable neighborhood descent algorithm to minimize Cmax in machine scheduling problem. Journal of Turkish Operations Management, Cilt: 9 Sayı: 1, 36–46. https://doi.org/10.56554/jtom.1515258

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (29)

  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