A simulated annealing algorithm for the faculty-level university course timetabling problem

Yıl 2024, Cilt: 30 Sayı: 1, 17 - 34, 29.02.2024

Hatice Erdoğan Akbulut , Feriştah Özçelik , Tuğba Saraç

Öz

In this study, faculty-level university course timetabling problem with double major and minor program constraints where classrooms are shared with several faculties is taken into account. This is the first study considering all these constraints together. A goal programming model is proposed to solve the considered problem. Since it is not possible to find a feasible solution for large-size problems with the proposed model in a time limit, a simulated annealing algorithm is developed. The performance of the proposed solution methods is tested by using randomly generated test problems. In addition, a case study is performed at the engineering faculty of a private university. Computational results show the success of the proposed simulated annealing algorithm to solve large-sized problems. An 83% improvement was achieved with the proposed algorithm for the real-life problem.

Anahtar Kelimeler

Faculty-level university course timetabling, Simulated annealing, Goal programming, Double major program, Minor program

Fakülte seviyesinde üniversite ders çizelgeleme problemi için bir tavlama benzetimi algoritması

Öz

Bu çalışmada, dersliklerin fakülteler arasında paylaşıldığı, çift anadal ve yan dal kısıtlarının olduğu fakülte seviyesinde üniversite ders çizelgeleme problemi ele alınmıştır. Bu çalışma, tüm bu kısıtları bir arada ele alan ilk çalışmadır. Ele alınan problemi çözmek için bir hedef programlama modeli önerilmiştir. Önerilen model ile büyük boyutlu problemler için süre limiti içinde uygun çözüm bulmak mümkün olmadığından, bir tavlama benzetimi algoritması geliştirilmiştir. Önerilen çözüm yöntemlerinin performansı rassal türetilmiş test problemleri kullanılarak sınanmıştır. Ayrıca özel bir üniversitenin mühendislik fakültesinde vaka çalışması yapılmıştır. Deneysel sonuçlar, önerilen tavlama benzetimi algoritmasının büyük boyutlu problemleri çözmedeki başarısını ortaya koymuştur. Gerçek hayat problemi için önerilen algoritma ile %83 oranında iyileşme sağlanmıştır.

Anahtar Kelimeler

Fakülte seviyesinde üniversite ders çizelgeleme, Tavlama benzetimi, Hedef programlama, Çift anadal programı, Yandal programı

Kaynakça

• [1] Wren A. Scheduling, Timetabling and Rostering-A special Relationship?. Editors: Burke EK, Ross P. Practice and Theory of Automated Timetabling, 46-75, Heidelberg, Berlin, Springer, 1996.
• [2] Burke EK, Petrovic S, Qu R. “Case-based heuristic selection for timetabling problems”. Journal of Scheduling, 9(2), 115-132, 2006.
• [3] Petrovic S, Burke E. “University timetabling”. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, 45, 1-34, 2004.
• [4] Schaerf A. “Survey of automated timetabling”. Artificial Intelligence Review, 13(2), 87-127, 1999.
• [5] Babaei H, Karimpour J, Hadi A. “A survey of approaches for university course timetabling problem”. Computers and Industrial Engineering, 86, 43-59, 2015.
• [6] Altunay H, Eren T. “A literature review for course scheduling problem”. Pamukkale University Journal of Engineering Sciences, 23(1), 55-70, 2017.
• [7] Mirhassani SA. “A computational approach to enhancing course timetabling with integer programming”. Applied Mathematics and Computation, 175(1), 814-822, 2006.
• [8] Ismayilova NA, Saǧir M, Gasimov RN. “A multiobjective faculty-course-time slot assignment problem with preferences”. Mathematical and Computer Modelling, 46(7-8), 1017-1029, 2007.
• [9] Cura T. “Timetabling of faculty lectures using simulated annealing algorithm”. İstanbul Commerce University Journal of Science, 6(12), 1-20, 2007.
• [10] Al Tarawneh HY, Ayob M. “Using tabu search with multi-neighborhood structures to solve university course timetable UKM case study (faculty of engineering)”. 2011 3rd Conference on Data Mining and Optimization (DMO), Putrajaya, Malaysia, 28-29 June 2011.
• [11] Nguyen K, Nguyen P, Tran N. “A hybrid algorithm of harmony search and bees algorithm for a university course timetabling problem”. International Journal of Computer Science Issues, 9(1), 12-17, 2012.
• [12] Demir Y, Çelik C. “An Integer Programming Approach for Curriculum Based Timetabling Problem Solution”. Journal of the Faculty of Engineering and Architecture of Gazi University, 31(1), 145-159, 2016.
• [13] Abdelhalim EA, El Khayat GA. “A utilization-based genetic algorithm for solving the university timetabling problem (UGA)”. Alexandria Engineering Journal, 55(2), 1395-1409, 2016.
• [14] Borchani R, Elloumi A, Masmoudi M. “Variable neighborhood descent search based algorithms for course timetabling problem: Application to a Tunisian University”. Electronic Notes in Discrete Mathematics, 58, 119-126, 2017.
• [15] Ertane E. Course Timetabling with Double Major Constraints. MSc Thesis, Ataturk University, Erzurum, Turkey, 2018.
• [16] Özkan A. Solving University Course Timetabling Problems with Integer Linear Programming and Heuristic Approaches. PhD Thesis, Hacettepe University, Ankara, Turkey, 2019.
• [17] Thepphakorn T, Pongcharoen P. “Performance improvement strategies on cuckoo search algorithms for solving the university course timetabling problem”. Expert Systems with Applications, 161, 1-21, 2020.
• [18] Alnowaini G, Aljomai AA. "Genetic Algorithm for Solving University Course Timetabling Problem Using Dynamic Chromosomes". 2021 International Conference of Technology, Science and Administration, Taiz, Yemen, 22-24 March 2021.
• [19] Ariyazand A, Soleimani H, Etebari F, Mehdizadeh E. "Improved satisfaction of university faculty by utilizing the Bat metaheuristic algorithm (Case study of the faculty of humanities, Islamic Azad University, Parand Branch)". Journal of Industrial Engineering and Management Studies, 9(8), 95-108, 2022.
• [20] Long J, Wu S, Han X, Wang Y, Liu L. "Autonomous task planning method for multi-satellite system based on a hybrid genetic algorithm". Aerospace, 10(1), 1-18, 2023.