KaydedilenlerDerginizi ekleyin

Dergiler / Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi / 2026 / Cilt: 41 Sayı: 1

Tek makine ağırlıklı erken / geç tamamlanma çizelgeleme problemi için sütun oluşturma, dal-fiyat ve ışın arama algoritmaları

Column generation, branch-price and beam search algorithms for single machine weighted earliness/tardiness scheduling problem

Oğuzhan Ahmet Arık, Nurefşan Bingöl

Sayfa
127–140
Yayın Tarihi
2026-02-19
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗

Özet

Bu çalışma, tek makinede ağırlıklı erken ve geç tamamlanma cezalarını minimize etmeye yönelik çizelgeleme problemine odaklanmakta ve bu problem için sütun oluşturma, dal-fiyat ve ışın arama algoritmalarının etkililiğini değerlendirmektedir. Araştırmada, çeşitli iş sayısı ve problem parametresiyle oluşturulan test setleri üzerinde önerilen yöntemlerin hem çözüm kalitesi hem de hesaplama süresi açısından kapsamlı karşılaştırmaları yapılmıştır. Elde edilen sonuçlar, sütun oluşturma tabanlı yaklaşımların referans yöntemlerle benzer veya optimal yakın çözüm kalitesi sunarken, özellikle dal-fiyat algoritmasının problem büyüklüğü arttıkça çözüm kalitesinde belirgin avantaj sağladığını göstermektedir. Ayrıca, ışın arama algoritması pratik çalışma süresi ve yüksek kaliteyi bir arada sunarak, büyük boyutlu problemlerde uygulanabilir bir alternatif olarak öne çıkmıştır. Analizler, Genetik Algoritma tabanlı başlangıç çözümlerine kıyasla, önerilen algoritmaların ortalamada %44'e varan iyileştirme sağladığını ortaya koymuştur. Sonuç olarak, çalışma, dinamik üretim ortamlarında tek makine çizelgeleme problemleri için gelişmiş optimizasyon tekniklerinin uygulama potansiyelini somut biçimde ortaya koymaktadır.

Abstract

This study focuses on the scheduling problem of minimizing weighted earliness and tardiness penalties on a single machine and evaluates the effectiveness of column generation, branch-price and beam search algorithms for this problem. In the study, comprehensive comparisons of the proposed methods in terms of both solution quality and computational time were made on test sets created with various job numbers and problem parameters. The obtained results show that while column generation based approaches provide similar or near-optimal solution quality to the reference methods, especially the branch-price algorithm provides a significant advantage in solution quality as the problem size increases. In addition, the beam search algorithm stands out as a viable alternative in large-scale problems by offering practical running time and high quality together. The analyses revealed that the proposed algorithms provide an average improvement of up to 44% compared to the initial solutions based on Genetic Algorithm. As a result, the study concretely demonstrates the application potential of advanced optimization techniques for single machine scheduling problems in dynamic manufacturing environments.

Anahtar kelimeler
🔖

Bu Makaleye Atıf Yap

Arık, O. A., Bingöl, N. (2026). Tek makine ağırlıklı erken / geç tamamlanma çizelgeleme problemi için sütun oluşturma, dal-fiyat ve ışın arama algoritmaları. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, Cilt: 41 Sayı: 1, 127–140. https://doi.org/10.17341/gazimmfd.1717668

📄 Tam Metin PDF Okuyucu

↗Yeni Sekme

PDF belgesi yükleniyor...

Kaynakça (31)

  1. 1. Pourali Z., Ebrahimi B., A novel mathematical model with an LCA-based solution method to minimize earliness-tardiness costs on a single machine by considering batch delivery, Big Data Comput. Vis., 5 (1), 74–93, 2025.
  2. 2. Palominos P., Mazo M., Fuertes G., Alfaro M., An improved marriage in honey-bee optimization algorithm for minimizing earliness/tardiness penalties in single-machine scheduling with a restrictive common due date, Mathematics, 13 (3), 2025.
  3. 3. Arık O.A., Fuzzy rule-based variable neighborhood search algorithm for single-machine weighted earliness/tardiness scheduling with common due date, Neural Comput. Appl., 37 (5), 3355–3371, 2024.
  4. 4. Mor B., Single machine minsum and minmax common due date assignment and scheduling problems involving general position-dependent workloads, RAIRO-Oper. Res., 59 (1), 483–498, 2025.
  5. 5. Hoffmann J., Neufeld J.S., Buscher U., Minimizing the earliness–tardiness for the customer order scheduling problem in a dedicated machine environment, J. Scheduling, 27 (6), 525–543, 2024.
  6. 6. Atsmony M., Mosheiov G., Single machine scheduling to minimize maximum earliness/tardiness cost with job rejection, Optim. Lett., 18 (3), 751–766, 2024.
  7. 7. Bari P., Karande P., Bag V., Hybrid genetic algorithm to minimize scheduling cost with unequal and job dependent earliness tardiness cost, Int. J. Prod. Manag. Eng., 12 (1), 19–30, 2024.
  8. 8. Arık O.A., A heuristic for single machine common due date assignment problem with different earliness/tardiness weights, OPSEARCH, 60 (3), 1561–1574, 2023.
  9. 9. Wang W., Single-machine due-date assignment scheduling with generalized earliness-tardiness penalties including proportional setup times, J. Appl. Math. Comput., 68 (2), 1013–1031, 2022.
  10. 10. Arık O.A., Single machine earliness/tardiness scheduling problem with grey processing times and the grey common due date, Grey Syst., 11 (1), 95–109, 2021.
  11. 11. Li S.S., Chen R.X., Scheduling with common due date assignment to minimize generalized weighted earliness–tardiness penalties, Optim. Lett., 14 (7), 1681–1699, 2020.
  12. 12. Bülbül K., Kedad-Sidhoum S., Şen H., Single-machine common due date total earliness/tardiness scheduling with machine unavailability, J. Scheduling, 22 (5), 543–565, 2019.
  13. 13. Fakhrzad M.B., Shamsadini S., Jafari-Nodoushan A., The parallel machine scheduling with considering the due date assignment, earliness, weighted number of tardy jobs and batch delivery, J. Adv. Manuf. Syst., 20 (2), 369–388, 2021.
  14. 14. Arık O.A., Schutten M., Topan E., Weighted earliness/tardiness parallel machine scheduling problem with a common due date, Expert Syst. Appl., 187, 115916, 2022.
  15. 15. Zhang Y., Cheng Z., Zhang N., Chiong R., A weighted distribution-free model for parallel machine scheduling with uncertain job processing times, Eur. J. Oper. Res., 324 (3), 814–824, 2025.
  16. 16. Chen Y., Zhao X., Mumtaz J., Guangyuan C., Wang C., Batch processing machine scheduling problems using a self-adaptive approach based on dynamic programming, Comput. Oper. Res., 176, 106933, 2025.
  17. 17. Arık O.A., Comparisons of metaheuristic algorithms for unrelated parallel machine weighted earliness/tardiness scheduling problems, Evol. Intell., 13, 415–425, 2020.
  18. 18. Chen Y., Xu Y., Zhang G., Cheng Y., A single machine group scheduling problem with due date assignment and position-dependent costs, Asia-Pac. J. Oper. Res., 40 (4), 2023.
  19. 19. Schaller J., Valente J.M.S., Scheduling in a no-wait flow shop to minimise total earliness and tardiness with additional idle time allowed, Int. J. Prod. Res., 60 (18), 5488–5504, 2022.
  20. 20. Arık O.A., Optimal policies for minimizing total job completion times and deviations from common due dates in unrelated parallel machine scheduling, OPSEARCH, 1–27, 2024.
  21. 21. Saraç T., Tutumlu B., A mix integer programming model and solution approach to determine the optimum machine number in the unrelated parallel machine scheduling problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (1), 329–345, 2022.
  22. 22. Takan A., Saraç T., New representation schemes for identical parallel machine scheduling problems with sequence dependent setup times, Journal of the Faculty of Engineering and Architecture of Gazi University, 38 (2), 1041–1054, 2023.
  23. 23. Saraç T., Özçelik 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.
  24. 24. Bektur G., Saraç T., Two parallel injection machine scheduling under crane constraint, Journal of the Faculty of Engineering and Architecture of Gazi University, 31 (4), 903–911, 2016.
  25. 25. Furugi A., A tabu search algorithm for the unrelated parallel machine scheduling problem with machine availability constraint and sequence-dependent setup time, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (3), 1539–1549, 2021.
  26. 26. Arık O.A., A lagrange relaxation based algorithm for parallel injection machine scheduling problem, Journal of the Faculty of Engineering and Architecture of Gazi University, 40 (1), 277–286, 2024.
  27. 27. Pinedo M.L., Scheduling: Theory, Algorithms, and Systems, 6th Ed., Springer, New York, USA, 2022.
  28. 28. Sabuncuoglu I., Bayiz M., Job shop scheduling with beam search, Eur. J. Oper. Res., 118 (2), 390–412, 1999.
  29. 29. Van Den Akker J.M., Hoogeveen J.A., Van Kempen J.W., Parallel machine scheduling through column generation: minimax objective functions, Lect. Notes Comput. Sci., 4168, 648–659, 2006.
  30. 30. Van den Akker J.M., Hurkens C.A.J., Savelsbergh M.W.P., Time-indexed formulations for machine scheduling problems: column generation, INFORMS J. Comput., 12 (2), 111–124, 2000.
  31. 31. Van Den Akker J.M., Van Hoesel C.P.M., Savelsbergh M.W.P., A polyhedral approach to single-machine scheduling problems, Math. Program. Ser. B, 85 (3), 541–572, 1999.