A New Greedy Algorithm for the Curriculum-based Course Timetabling Problem

Year 2023, , 1121 - 1136, 30.04.2023

Batuhan Mustafa Coşar , Bilge Say , Tansel Dökeroğlu

https://doi.org/10.29130/dubited.1113519

Abstract

This study describes a novel greedy algorithm for optimizing the well-known Curriculum-Based Course Timetabling (CB-CTT) problem. Greedy algorithms are a good alternative to brute-force and evolutionary algorithms, which take a long time to execute in order to find the best solution. Rather than employing a single heuristic, as many greedy algorithms do, we define and apply 120 new heuristics to the same problem instance. To assign courses to available rooms, our proposed greedy algorithm employs the Largest-First, Smallest-First, Best-Fit, Average-weight first, and Highest Unavailable course-first heuristics. Extensive experiments are carried out on 21 problem instances from the benchmark set of the Second International Timetabling Competition (ITC-2007). For 18 problems with significantly reduced soft-constraint values, the proposed greedy algorithm can report zero hard constraint violations (feasible solutions). The proposed algorithm outperforms state-of-the-art greedy heuristics in terms of performance.

Keywords

Course-timetabling, Greedy algorithms, heuristics, optimization

Müfredat Tabanlı Ders Çizelgeleme Problemi için Yeni Bir Açgözlü Algoritma

Abstract

Bu çalışma, iyi bilinen Müfredat Tabanlı Ders Çizelgeleme Problemini optimize etmek için yeni bir açgözlü algoritmayı açıklamaktadır. Açgözlü algoritmalar, en iyi çözümü bulmak için yürütülmesi uzun zaman alan kaba kuvvet ve evrimsel algoritmalara iyi bir alternatiftir. Birçok açgözlü algoritmanın yaptığı gibi tek bir buluşsal yöntem kullanmak yerine, aynı problem örneğine 120 yeni buluşsal yöntem tanımlıyor ve uyguluyoruz. Dersleri müsait odalara atamak için, önerilen açgözlü algoritmamız En Büyük-İlk, En Küçük-İlk, En Uygun, Önce Ortalama Ağırlık ve En Yüksek Kullanılamaz ders-ilk buluşsal yöntemlerini kullanır. İkinci Uluslararası Zaman Çizelgesi Yarışması'nın (ITC-2007) kıyaslama setinden 21 problem örneği üzerinde kapsamlı deneyler gerçekleştirilir. Önemli ölçüde azaltılmış yumuşak kısıtlama değerlerine sahip 18 problem için, önerilen açgözlü algoritma sıfır sabit kısıtlama ihlali (uygulanabilir çözümler) rapor edebilir. Önerilen algoritma, performans açısından son teknoloji ürünü açgözlü buluşsal yöntemleri geride bırakıyor.

Keywords

Ders zaman çizelgesi oluşturma, Açgözlü algoritmalar, buluşsal yöntemler, eniyileme

References

• [1] P. Michael, and K. Hadavi, "Scheduling: theory, algorithms and systems development," Operations research proceedings, Berlin, 1992, pp. 35-42.
• [2] W. Ruegg, A history of the university in Europe: Volume 3, universities in the nineteenth and early twentieth centuries, vol. 3, Cambridge University Press, 2004, pp.1800-1945.
• [3] D. Ronald, and V.N. Temlyakov, "Some remarks on greedy algorithms," Advances in computational Mathematics, vol. 5, pp. 173-187, 1996.
• [4] A.R. Barron, A. Cohen, W. Dahmen, RA. DeVore, “Approximation and learning by greedy algorithms,” The annals of statistics, vol. 36, no. 1, pp. 64-94. 2008.
• [5] A. Bettinelli, V. Cacchiani, R. Roberti, and P. “Toth An overview of curriculum-based course timetabling,” Top, vol. 23, no. 2, pp. 313-349, 2015.
• [6] E.K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” Journal of the Operational Research Society, vol. 64, no. 12, pp. 1695-1724. 2013.
• [7] D.H. Wolpert, and W.G. Macready, “No free lunch theorems for optimization,” IEEE transactions on evolutionary computation, vol. 1, no. 1, pp. 67-82, 1997.
• [8] G. Dosa, J. Sgall, “Optimal analysis of best bin packing,” International Colloquium on Automata, Languages, and Programming, 2014, pp.429-441.
• [9] K. Fleszar, and C. Charalambous, “Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem,” European Journal of Operational Research, vol. 210, no. 2, pp. 176-184, 2011.
• [10] G.L. Di, B. McCollum, and A. Schaerf, “The second international timetabling competition (ITC-2007): Curriculum-based course timetabling (track 3),” Technical Report 1.0, Queen’s University, Belfast, United Kingdom, 2007.
• [11] P.I. Tillett, “An operations research approach to the assignment of teachers to courses,” Socio-Economic Planning Sciences, vol. 9, no. 3-4, pp. 101-104, 1975.
• [12] H. Babaei, J. Karimpour, and A. Hadidi, “A survey of approaches for university course timetabling problem,” Computers & Industrial Engineering, vol. 86, pp. 43-59, 2015.
• [13] S. Abdullah, H. Turabieh, B. McCollum, and P. McMullan, “A hybrid metaheuristic approach to the university course timetabling problem,” Journal of Heuristics, vol. 18, no. 1, pp. 1-23, 2012.
• [14] I. Boussaïd, J. Lepagnot, and P. Siarry, “A survey on optimization metaheuristics,” Information sciences, vol. 237, pp. 82-117, 2013.
• [15] T. Dokeroglu, E. Sevinc, T. Kucukyilmaz, and A. Cosar, “A survey on new generation metaheuristic algorithms,” Computers & Industrial Engineering, vol. 137, no. 106040, 2019.
• [16] S.A. MirHassani, and F. Habibi, “Solution approaches to the course timetabling problem,” Artificial Intelligence Review, vol. 39, no. 2, pp. 133-149, 2013.
• [17] A. Gary, and C. Robert, “Matching Faculty to Courses,” College and University, vol. 46, pp. 83-89, 1971.
• [18] J.S. Dyer, and J.M. Mulvey, “An integrated optimization/information system for academic departmental planning,” Management Science, vol. 22, no. 12, pp. 1332-1341, 1976.
• [19] W. Shih, and J.A. Sullivan, “Dynamic course scheduling for college faculty via zero-one programming,” Decision Sciences, vol. 8, no. 4, pp. 711-721, 1977.
• [20] N.Christian, F. Bagger, S. Kristiansen, M. Sørensen, and T.R. Stidsen, “Flow formulations for curriculum-based course timetabling,” Annals of Operations Research, vol. 280, no. 1, pp. 121-150, 2019.
• [21] A.E. Phillips, C.G. Walker, M. Ehrgott, and D.M. Ryan, “Integer programming for minimal perturbation problems in university course timetabling,” Annals of Operations Research, vol. 252, no. 2, pp. 283-304, 2017.
• [22] M.J. Geiger, “Applying the threshold accepting metaheuristic to curriculum based course timetabling,” Annals of Operations Research, vol. 194, no.1, pp. 189-202, 2012.
• [23] Z. Lu, and J.K. Hao, “Adaptive tabu search for course timetabling,” European journal of operational research, vol. 200, no. 1, pp. 235-244, 2010.
• [24] T. Dokeroglu, and E. Sevinc, “Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems,” Engineering Applications of Artificial Intelligence, vol. 102, no. 104282, 2021.
• [25] A. Gulcu, and C. Akkan, “Robust university course timetabling problem subject to single and multiple disruptions,” European Journal of Operational Research, vol. 283, no. 1, pp. 630-646., 2020.
• [26] C. Akkan and A. Gulcu, “A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem,” Computers and Operations Research, vol. 90, pp. 22-32, 2018.
• [27] T. Thepphakorn, and P. Pongcharoen, “Variants and parameters investigations of particle swarm optimisation for solving course timetabling problems,” International Conference on Swarm Intelligence, 2019, pp. 177-187.
• [28] S. LengGoh, G. Kendall, and N.R. Sabar, “Improved local search approaches to solve the post enrolment course timetabling problem,” European Journal of Operational Research, vol. 261, no. 1, pp. 17-29., 2017.
• [29] N.C.F. Bagger, M. Sorensen, and TR. Stidsen, “Benders’ decomposition for curriculum-based course timetabling,” Computers and Operations Research, vol. 91, pp. 178-189, 2018.
• [30] T. Song, S. Liu, X. Tang, X. Peng, and M. Chen, “An iterated local search algorithm for the University Course Timetabling Problem,” Applied Soft Computing, vol. 68, pp. 597-608, 2018.
• [31] A.De Coster, N.Musliu, A.Schaerf, J.Schoisswohl, and K.Smith-Miles, “Algorithm selection and instance space analysis for curriculum-based course timetabling,” Journal of Scheduling, vol. 25, no 1, pp. 35-58, 2022.
• [32] C.Akkan, A.Gülcü, and Z.Kuş, “Bi-criteria simulated annealing for the curriculum-based course timetabling problem with robustness approximation,” Journal of Scheduling, pp. 1-25, 2022.
• [33] G.Colajanni, and P.Daniele, “A new model for curriculum-based university course timetabling,” Optimization Letters, vol. 15, no 5, pp. 1601-1616., 2021.
• [34] H. Asmuni, “Fuzzy methodologies for automated university timetabling solution construction and evaluation,” Ph.D. dissertation, University of Nottingham, United Kingdom, 2008.
• [35] J.H. Obit, “Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems,” Ph.D, University of Nottingham, United Kingdom, 2010.
• [36] T.A. Redl, “A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions,” Ph.D., Rice University Houston, USA, 2004.
• [37] B.M. Cosar, “New greedy algorithms to optimize the curriculum-based course timetabling problem, “ M.S thesis, Atilim University, Ankara, Turkey, 2021.
• [38] T. Muller, “ITC2007 solver description: a hybrid approach,” Annals of Operations Research, vol. 172, no. 1, pp. 429-446, 2009.
• [39] M. Atsuta, K. Nonobe, and T. Ibaraki, “ITC-2007 Track2: an approach using general CSP solver,” Citeseer, 2008.
• [40] M. Clark, M. Henz, and B. Love, “Quikfix—a repair-based timetable solver,” The Seventh International Conference on the Practice and Theory of Automated Timetabling,” Citeseer, 2008.