TEK MAKİNELİ ÇİZELGELEME PROBLEMİNDE TOPLAM GECİKME SÜRESİ MİNİMİZASYONU İÇİN GENETİK ALGORİTMA VE DAL SINIR ALGORİTMASI YAKLAŞIMI: BİR ELOKSAL TESİSİNDE UYGULAMA

Year 2025, Volume: 8 Issue: 1, 277 - 288, 26.08.2025

Münevver Meltem Çalışkan , Berk Ayvaz , Muhammet Ceylan

https://doi.org/10.56809/icujtas.1512826

Abstract

Bu çalışmada, toplam gecikmeyi minimize etmek için dal-sınır algoritması ve genetik algoritma yaklaşımları önerilmektedir. Dal-sınır algoritması, kesin çözümler sunarken büyük boyutlu problemler için yüksek hesaplama süresi gerektirebilir. Genetik algoritmalar ise esnek yapısı ve hızlı çözüm tarama kabiliyeti ile dikkat çekmektedir. Önerilen yöntem, alüminyum aksesuar üretimi yapan bir fabrikanın eloksal tesisindeki tek makine çizelgeleme problemine uygulanmış ve toplam gecikmeyi minimize edecek en uygun çizelge oluşturulmuştur.

Keywords

Tek makine çizelgeleme , Dal sınır algoritması , Genetik algoritma

A Genetic Algorithm And Branch-And-Bound Approach For Minimizing Total Tardiness In The Single Machine Scheduling Problem: An Application In An Anodizing Facility

Abstract

The study proposes the use of branch-and-bound algorithm and genetic algorithm methodologies to minimize the total tardiness. Although the branch-and-bound approach is capable of providing precise solutions, it may necessitate significant computational time when dealing with issues of considerable scale. Genetic algorithms are notable for their adaptable framework and efficient ability to scan for solutions quickly. The proposed method is implemented to address the single machine scheduling problem in the anodising plant of an aluminium accessories manufacturing facility, resulting in the generation of an optimal schedule that minimizes the total delay.

Keywords

Single Machine Scheduling , Branch and Bound Algorithm , Genetic Algorithm

References

• Akkocaoğlu, H. (2014). A new customer order scheduling problem on a single-machine with job setup times, Çankaya Üniversitesi, Fen Bilimleri Enstitüsü (Yüksek Lisans Tezi).
• Alan, K. Ş. (2021). Doğrusal Tamsayılı Programlama Problemlerinin Çözümü İçin Yeni. İstanbul: European Journal of Science and Technology.
• Ali Allahverdi, Harun Aydilek, Asiye Aydilek, Single machine scheduling problem with interval processing times to minimize mean weighted completion time, Computers & Operations Research,Volume 51,2014,Pages 200-207,https://doi.org/10.1016/j.cor.2014.06.003.
• Baker K. R. and Trietsch D., (2009), Principles of sequencing and scheduling, A John Wiley& Sons Inc, Hoboken, New Jersey, 2009.
• Ben-Yehoshua, Y., & Mosheiov, G. (2016). A single machine scheduling problem to minimize total early work. Computers & Operations Research, 73, 115-118
• Briskorn D., Choi B.C., Lee K., Leung J., Pinedo M.Complexity of single machine scheduling subject to nonnegative inventory constraints European Journal of Operational Research, 207 (2) (2010), pp. 605-619
• Briskorn, D., Jaehn, F., & Pesch, E. (2013). Exact algorithms for inventory constrained scheduling on a single machine. Journal of Scheduling, 16, 105–115.
• Che, A., Wu, X., Peng, J., & Yan, P. (2017). Energy-efficient bi objective single-machine scheduling with power-down mechanism. Computers & Operations Research, 85, 172-183. Computers & Industrial Engineering, Volume 37,2019,106072,https://doi.org/10.1016/j.cie.2019.106072.
• Dehua Xu, Long Wan, Aihua Liu, Dar-Li Yang, Single machine total completion time scheduling problem with workload-dependent maintenance duration, Omega,Volume 52, 2015, Pages 101-106, https://doi.org/10.1016/j.omega.2014.11.002.
• Ehsan Molaee, Ghasem Moslehi, Mohammad Reisi,Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem,Computers & Mathematics with Applications,Volume 60, Issue 11,2010,Pages 2909-2919, https://doi.org/10.1016/j.camwa.2010.09.046.
• Eren, T. (2014). Learning and Deteriorating Effects on the Single Machine SchedulingProblems. Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi
• Ermiş, G. (2014). Single Machine Scheduling with Timelag Constraints, Koç Üniversitesi, Fen Bilimleri Enstitüsü (Doktora Tezi)
• Evgeny R. Gafarov, Alexander A. Lazarev, Frank Werner, A note on a single machine scheduling problem with generalized total tardiness objective function, Information Processing Letters,Volume 112, Issue 3,2012, Pages 72-76,https://doi.org/10.1016/j.ipl.2011.10.013.
• Gupta, S. R., & Smith, J. S. (2006). Algorithms for single machine total tardiness scheduling with sequence dependent setups. European Journal of OperationalResearch, 175(2), 722-739
• Herr, O., & Goel, A. (2015). Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints. European Journal of Operational Research, 248(1), 123- 135.
• Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
• Kaya, S. (2013). A genetic algorithm for the resource constrained project scheduling problem having a single machıne with sequence dependent setup times.
• Kır, S. (2011). Sıra Bağımlı Hazırlık Zamanlı Tek Makinalı Çizelgeleme Problemleri: Gıda Sektöründe Bir Uygulama (Doctoral dissertation, Fen Bilimleri Enstitüsü).
• Lu Chen, Jinfeng Wang, Xianyang Xu, An energy-efficient single machine scheduling problem with machine reliability constraints,
• Muştu, S., & 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.
• Oliver Herr, Asvin Goel, Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints, European Journal of Operational Research, Volume 248, Issue 1,2016,Pages 123-135, https://doi.org/10.1016/j.ejor.2015.07.001.
• Oliver Herr, Asvin Goel, Comparison of Two Integer Programming Formulations for a Single Machine Family Scheduling Problem to Minimize Total Tardiness,Procedia CIRP,Volume 19, 2014,Pages 174-179, https://doi.org/10.1016/j.procir.2014.05.007.
• Özbakır S.İ. (2011). A heuristic approach for the single machine scheduling tardiness problems, Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü (Yüksek Lisans Tezi).
• Özdemir M.H. (2007). Kısıtlandırılmış teslim tarihli ve sıraya bağımlı hazırlı süreli tek makine çizelgeleme problemlerinde erkenlik ve geçlik toplamının en küçüklenmesi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü
• Özer, B., & Köksal, M. (2016). Hammadde ve Renk Tabanlı Çizelgeleme ve Bir Elektroteknik Fabrikasında Uygulaması. Istanbul Commerce University Journal of Science, 15(30), 95-106.
• Perez-Gonzalez, P., & Framinan, J. M. (2018). Single machine scheduling with periodic machine availability. Computers & Industrial Engineering.
• Pinedo, M. L. (2008). Scheduling: theory, algorithms, and systems. Springer.
• Rostami, S., Creemers,S., & Leus, R. (2019). Precedence theorems and dynamic programming for the single-machine weighted tardiness problem. European Journal of Operational Research, 272(1), 43-49.
• Souissi, O., Benmansour, R., & Artiba, A. (2016). An accelerated MIP model for the single machine scheduling with preventive maintenance. IFAC-Paper sOnLine, 49(12), 1945-1949
• Walid Hfaiedh, Chérif Sadfi, Imed Kacem, Atidel Hadj-Alouane, A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization, Applied Mathematics and Computation, Volume 252, 2015,Pages 496-502, ISSN 0096-3003,https://doi.org/10.1016/j.amc.2014.11.103.
• Xiaochuan Luo, Feng Chu,A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness,Applied Mathematics and Computation,Volume 183, Issue 1,2006,Pages 575-588.
• Yunqiang Yin, Wen-Hung Wu, Wen-Hsiang Wu, Chin-Chia Wu, A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects, Information Sciences, Volume 256,2014,Pages 91-108.
• Yu-Chung Tsao, Vo-Van Thanh, Feng-Jang Hwang,Energy-efficient single-machine scheduling problem with controllable job processing times under differential electricity pricing,Resources, Conservation and Recycling,Volume 161, 2020,104902,https://doi.org/10.1016/j.resconrec.2020.104902.
• Zhao, C., &Tang, H. (2010). Single machine scheduling with pastsequence dependent setup times and deteriorating obs. Computers & Industrial Engineering, 59(4), 663-666.