SavedAdd your journal

Journals / Endüstri Mühendisliği / 2026 / Cilt: 37 Sayı: 2

A GENIUS-CP-BASED HEURISTIC FOR TOTAL WEIGHTED TARDINESS MINIMIZATION IN THE SINGLE-MACHINE SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES

SIRAYA BAĞLI HAZIRLIK SÜRELİ TEK MAKİNE ÇİZELGELEME PROBLEMİNDE TOPLAM AĞIRLIKLI GECİKMENİN MİNİMİZASYONU İÇİN GENIUS-CP TABANLI BİR SEZGİSEL

Erdener Özçetin(HİTİT ÜNİVERSİTESİ)0000-0002-6079-3159
Pages
566–597
Publication Date
2026-08-28
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Experimental results show that SA (0.6% deviation) and TS (3.0% deviation) outperform GENIUS-CP (6.3% deviation) in terms of solution quality.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Scheduling jobs on a single machine with sequence-dependent setup times to minimize the total weighted tardiness (1 | sᵢⱼ | Σ wⱼTⱼ) is an NP-hard problem frequently encountered in real production systems.
📊
Key Findings & Data:In the proposed method, the generalized insertion move is combined with a constraint programming-based domain reduction structure; a multi-start strategy is integrated into the algorithm to establish a parallel computing framework.
💡
Conclusion & Impact:Experimental results show that SA (0.6% deviation) and TS (3.0% deviation) outperform GENIUS-CP (6.3% deviation) in terms of solution quality.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Tek makine çizelgeleme · sıraya bağlı hazırlık süresi · ağırlıklı gecikme

Abstract

Scheduling jobs on a single machine with sequence-dependent setup times to minimize the total weighted tardiness (1 | sᵢⱼ | Σ wⱼTⱼ) is an NP-hard problem frequently encountered in real production systems. In this study, the GENIUS-CP algorithm, originally developed in the literature primarily for vehicle routing problems, is adapted to the scheduling problem in question. In the proposed method, the generalized insertion move is combined with a constraint programming-based domain reduction structure; a multi-start strategy is integrated into the algorithm to establish a parallel computing framework. The method is compared with EDD, ATCS, Simulated Annealing (SA), Tabu Search (TS), and Genetic Algorithm (GA) on 24 instances generated according to the Cicirello benchmark parameters. Experimental results show that SA (0.6% deviation) and TS (3.0% deviation) outperform GENIUS-CP (6.3% deviation) in terms of solution quality. However, the single-start GENIUS-CP variant achieves this solution quality in under one second (0.42 s), demonstrating a significantly shorter actual computation time compared to the local search-based methods. The parallel multi-start variant, on the other hand, prolonged the computation time due to parallelization overhead without providing a notable improvement in quality for the current instance sizes. The findings reveal that it would be advantageous to position GENIUS-CP not as a standalone metaheuristic, but as a powerful constructive heuristic that generates extremely fast and high-quality initial solutions for hybrid algorithms.

Özet

Sıraya bağlı hazırlık sürelerine sahip işlerin tek bir makine üzerinde çizelgelenerek toplam ağırlıklı gecikmenin en küçüklenmesi (1 | sᵢⱼ | Σ wⱼTⱼ) NP-zor yapıda bir problemdir ve gerçek üretim sistemlerinde sıklıkla karşılaşılır [source: 1]. Bu çalışmada, literatürde öncelikli olarak araç rotalama problemleri için geliştirilen GENIUS-CP algoritması söz konusu çizelgeleme problemine uyarlanmıştır. Önerilen yöntemde, genelleştirilmiş yerleştirme hareketi kısıt programlama tabanlı bir alan daraltma yapısıyla birleştirilmiş; algoritmaya çoklu başlangıç stratejisi entegre edilerek paralel hesaplama altyapısı kurulmuştur. Yöntem, Cicirello benchmark üretim parametrelerine uygun 24 örnek üzerinde EDD, ATCS, Tavlama Benzetimi (SA), Tabu Arama (TS) ve Genetik Algoritma (GA) ile karşılaştırılmıştır. Deneysel sonuçlar, çözüm kalitesi açısından SA (%0,6 sapma) ve TS'nin (%3,0 sapma) GENIUS-CP'den (%6,3 sapma) daha üstün olduğunu göstermektedir. Ancak, tek başlangıçlı GENIUS-CP varyantı, söz konusu çözüm kalitesine bir saniyenin altında (0,42 s) ulaşarak yerel arama tabanlı yöntemlerden önemli ölçüde daha kısa gerçek çalışma süresi sergilemiştir. Çoklu başlangıçlı paralel varyant ise mevcut örnek boyutlarında kalitede belirgin bir artış sağlamadan paralel hesaplama maliyeti nedeniyle süreyi uzatmıştır. Elde edilen bulgular, GENIUS-CP'nin tek başına bir metasezgisel olarak değil, hibrit algoritmalar için son derece hızlı ve yüksek kaliteli başlangıç çözümü üreten güçlü bir inşa sezgiseli olarak konumlandırılmasının avantaj sağlayacağını ortaya koymaktadır.

🔖

Cite This Article

Özçetin, E. (2026). A GENIUS-CP-BASED HEURISTIC FOR TOTAL WEIGHTED TARDINESS MINIMIZATION IN THE SINGLE-MACHINE SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIMES. Endüstri Mühendisliği, Cilt: 37 Sayı: 2, 566–597. https://doi.org/10.46465/endustrimuhendisligi.1945267

📄 Full Text PDF Viewer

📄

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

References (24)

  1. Aghelinejad, M. M., Ouazene, Y. ve Yalaoui, A. (2019). Single-machine scheduling problem with total energy consumption costs minimization. IFAC-PapersOnLine, 52(13), 409-414. Doi: https://doi.org/10.1016/j.ifacol.2019.11.087
  2. Anghinolfi, D. ve Paolucci, M. (2008). A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem. International Journal of Operations Research, 5(1), 44–60.
  3. Anghinolfi, D. ve Paolucci, M. (2009). A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 193(1), 73–85. Doi: https://doi.org/10.1016/j.ejor.2007.10.044
  4. Bożejko, W. (2010). Parallel path relinking method for the single machine total weighted tardiness problem with sequence-dependent setups. Journal of Intelligent Manufacturing, 21(6), 777–785. Doi: https://doi.org/10.1007/s10845-009-0253-2
  5. Chao, C.-W. ve Liao, C.-J. (2012). A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times. Applied Soft Computing, 12(9), 3079–3087. Doi: https://doi.org/10.1016/j.asoc.2012.05.017
  6. Cicirello, V. A. (2003). Weighted tardiness scheduling with sequence-dependent setups: A benchmark library (Teknik Rapor). Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA. Erişim adresi: https://www.cicirello.org/publications/ cicirello2003cmu.html
  7. Cicirello, V. A. (2006). Non-wrapping order crossover: An order preserving crossover operator that respects absolute position. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '06) içinde (s. 1125–1131). New York: ACM Press. Doi: https://doi.org/10.1145/1143997.1144177
  8. Cicirello, V. A. (2009). Weighted tardiness scheduling with sequence-dependent setups: A benchmark problem for soft computing. E. Avineri, M. Köppen, K. Dahal, Y. Sunitiyoso ve R. Roy (Eds.), Applications of Soft Computing içinde (s. 189–198). Berlin: Springer. Doi: https://doi.org/10.1007/978-3-540-88079-0_19
  9. Cicirello, V. A. ve Smith, S. F. (2005). Enhancing stochastic search performance by value-biased randomization of heuristics. Journal of Heuristics, 11(1), 5–34. Doi: https://doi.org/10.1007/s10732-005-6997-8
  10. Gendreau, M., Hertz, A. ve Laporte, G. (1992). New insertion and postoptimization procedures for the traveling salesman problem. Operations Research, 40(6), 1086–1094. Doi: https://doi.org/10.1287/opre.40.6.1086
  11. Gendreau, M., Hertz, A., Laporte, G. ve Stan, M. (1998). A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46(3), 330–335. Doi: https://doi.org/10.1287/opre.46.3.330
  12. Kirlik, G. ve Oğuz, C. (2012). A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine. Computers & Operations Research, 39(7), 1506–1520. Doi: https://doi.org/10.1016/j.cor.2011.08.022
  13. Lee, Y. H., Bhaskaran, K. ve Pinedo, M. (1997). A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29(1), 45–52. Doi: https://doi.org/10.1080/07408179708966311
  14. Liao, C.-J. ve Juan, H.-C. (2007). An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & Operations Research, 34(7), 1899–1909. Doi: https://doi.org/10.1016/j.cor.2005.07.020
  15. Lin, S.-W. ve Ying, K.-C. (2007). Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics. The International Journal of Advanced Manufacturing Technology, 34(11), 1183–1190. Doi: https://doi.org/10.1007/s00170-006-0693-1
  16. Muştu, S. ve Eren, T. (2015). Geliş zamanlarının farklı olduğu öğrenme etkili tek makine çizelgelemede toplam gecikmenin çözümü. Sosyal Bilimler Araştırma Dergisi, 4(3), 11–34.
  17. Özçelik, F. ve Saraç, T. (2011). Sıra bağımlı hazırlık süreli iki ölçütlü tek makine çizelgeleme problemi için sezgisel bir çözüm yöntemi. Endüstri Mühendisliği, 22(4), 48-57. Erişim adresi: https://dergipark.org.tr/tr/pub/ endustrimuhendisligi
  18. Pesant, G., Gendreau, M. ve Rousseau, J.-M. (1998). GENIUS-CP: A generic single-vehicle routing algorithm. M. Maher ve J.-F. Puget (Eds.), Principles and Practice of Constraint Programming — CP98, Lecture Notes in Computer Science, vol. 1520 içinde (s. 420–434). Berlin: Springer. Doi: https://doi.org/10.1007/BFb0017457
  19. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5. baskı). Cham: Springer. Doi: https://doi.org/10.1007/978-3-319-26580-3
  20. Subramanian, A., Battarra, M. ve Potts, C. N. (2014). An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. International Journal of Production Research, 52(9), 2729–2742. Doi: https://doi.org/10.1080/ 00207543.2014.883472
  21. Tanaka, S. ve Araki, M. (2013). An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research, 40(1), 344–352. Doi: https://doi.org/10.1016/j.cor.2012.07.004
  22. Tasgetiren, M. F., Pan, Q.-K. ve Liang, Y.-C. (2009). A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research, 36(6), 1900–1915. Doi: https://doi.org/10.1016/j.cor.2008.06.007
  23. Vepsalainen, A. P. J. ve Morton, T. E. (1987). Priority rules for job shops with weighted tardiness costs. Management Science, 33(8), 1035–1047. Doi: https://doi.org/10.1287/mnsc.33.8.1035
  24. Yu, R. ve Oron, D. (2025). Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis. European Journal of Operational Research, 324(1), 40-48. Doi: https://doi.org/10.1016/j.ejor.2025.01.007