Solving University Course Timetabling Problem Using a Meta-Heuristic Algorithm Based on Clustering
Keywords:
UCTP, Timetabling, Clustering, Meta-heuristic, Optimization, ConstraintsAbstract
This paper examines the University Course Timetabling Problem (UCTP), which is one of the time-consuming issues in any educational environment. In UCTP there are many parameters such as courses, classes, students and timeslots that make it an NP-Hard problem. The objective here is to produce an acceptable timetable based on satisfying a set of hard and soft constraints. Hard constraints must be observed, and adherence to soft constraints will improve the timetable, although failure to comply with soft constraints does not make the solution unacceptable. In this paper, a clustering-based genetic algorithm in the form of a meta-heuristic algorithm is used to solve this problem. Here, instances of input problems are examined from two perspectives. The first view is instances that have a small search space and the solutions in which they are produced often have no hard constraints. The second view is instances of high complexity and relatively large search space. In the first category, reducing soft constraints is challenging, while in the second category, it is very difficult to produce a solution without hard constraints. In order to reduce the complexity of the proposed algorithm and to properly orient the quantification of events, here events are clustered based on the number of students. Then, the initial population is created innovatively with the aim of minimizing hard constraints. The results on the BenPaechter database indicate the fact that the proposed algorithm offers better solutions in most instances than other similar algorithms.
References
H. Babaei, J. Karimpour, A. Hadidi, "A survey of approaches for university course timetabling problem," Computers & Industrial Engineering, Vol.86, pp.43-59, 2015.
S. Abdullah, H. Turabieh, B. McCollum, P. McMullan, "A hybrid metaheuristic approach to the university course timetabling problem," Journal of Heuristics, Vol.18, Issue.1, pp.1-23, 2012.
M. Kaur, S. Saini, "A Review of Metaheuristic Techniques for Solving University Course Timetabling Problem," Advances in Information Communication Technology and Computing, Vol.8, pp.19-25, 2021.
T. Song, S. Liu, X. Tang, X. Peng, M. Chen, "An iterated local search algorithm for the University Course Timetabling Problem," Applied Soft Computing, Vol.68, pp.597-608, 2018.
R.P. Badoni, D.K. Gupta, P. Mishra, "A new hybrid algorithm for university course timetabling problem using events based on groupings of students," Computers & industrial engineering, Vol.78, pp.12-25, 2014.
A. Gülcü, C. Akkan, "Robust university course timetabling problem subject to single and multiple disruptions," European Journal of Operational Research, Vol.283, Issue.2, pp.630-646, 2020.
T. Thepphakorn, P. Pongcharoen, "Performance improvement strategies on Cuckoo Search algorithms for solving the university course timetabling problem," Expert Systems with Applications, Vol.161, pp.113732, 2020.
T. Song, S. Liu, X. Tang, X. Peng, M. Chen, "An iterated local search algorithm for the University Course Timetabling Problem," Applied Soft Computing, Vol.68, pp.597-608, 2018.
E.A. Abdelhalim, G.A. E, "A utilization-based genetic algorithm for solving the university timetabling problem (UGA)," Alexandria Engineering Journal, Vol.55, Issue.2, pp.1395-1409, 2016.
C. Akkan, A. Gülcü, "A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem," Computers & Operations Research, Vol.8, pp.22-32, 2018.
S. Abdullah, E.K. Burke, B. McCollum, “A hybrid evolutionary approach to the university course timetabling problem,” In 2007 IEEE congress on evolutionary computation, pp.1764-1768, 2007.
S.N. Jat, S. Yang, “A memetic algorithm for the university course timetabling problem,” In 2008 20th IEEE International Conference on Tools with Artificial Intelligence, Vol.1, pp.427-433, 2008.
D. Lohpetch, S. Jaengchuea, “A hybrid multi-objective genetic algorithm with a new local search approach for solving the post enrolment-based course timetabling problem,” In Recent Advances in Information and Communication Technology, pp.195-206, 2016.
G.H. Fonseca, H.G. Santos, "Variable neighborhood search-based algorithms for high school timetabling," Computers & Operations Research, Vol.52, pp.203-208, 2014.
S. Yang, S.N. Jat, “Genetic algorithms with guided and local search strategies for university course timetabling,” IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol.41, Issue.1, pp.93-106, 2010.
M.S. Kohshori, M.S. Abadeh, H. Sajedi, "A fuzzy genetic algorithm with local search for university course timetabling,” In The 3rd International Conference on Data Mining and Intelligent Information Technology Applications, pp.250-254, 2011.
E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu, "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, Vol.176, Issue.1, pp.177-192, 2007.
A. Rezaeipanah, S.S. Matoori, G. Ahmadi, "A hybrid algorithm for the university course timetabling problem using the improved parallel genetic algorithm and local search," Applied Intelligence, Vol.51, Issue.1, pp.467-492, 2021.
A. Rezaeipanah, Z. Abshirini, M.B. Zade, "Solving University course timetabling problem using parallel genetic algorithm," International Journal of Scientific Research in Computer Science and Engineering, Vol.7, Issue.5, pp.5-13, 2019.
A.A. Gozali, B. Kurniawan, W. Weng, S. Fujimura, "Solving university course timetabling problem using localized island model genetic algorithm with dual dynamic migration policy," IEEJ Transactions on Electrical and Electronic Engineering, Vol.15, Issue.3, pp.389-400, 2020.
R.M. Chen, H.F. Shih, "Solving university course timetabling problems using constriction particle swarm optimization with local search," Algorithms, Vol.6, Issue.2, pp.227-244, 2013.
J.H. Obit, K.Y. Junn, R. Alfred, "Performance comparison of linear and non-linear great deluge algorithms in solving university course timetabling problems," Advanced Science Letters, Vol.23, Issue.11, pp.11027-11030, 2017.
K.Y. Junn, J.H. Obit, R. Alfred, "The study of genetic algorithm approach to solving university course timetabling problem,” In International Conference on Computational Science and Technology, pp.454-463, 2017.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
