Solving University Course Timetabling Problem Using a Meta-Heuristic Algorithm Based on Clustering

Tooba Bardestani¹ , Musa Mojarad² , Hassan Arfaeinia³

Section:Research Paper, Product Type: Journal-Paper
Vol.9 , Issue.6 , pp.1-8, Dec-2021

Online published on Dec 31, 2021

Copyright © Tooba Bardestani, Musa Mojarad, Hassan Arfaeinia . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
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.

Key-Words / Index Term :
UCTP, Timetabling, Clustering, Meta-heuristic, Optimization, Constraints

References :
[1] H. Babaei, J. Karimpour, A. Hadidi, "A survey of approaches for university course timetabling problem," Computers & Industrial Engineering, Vol.86, pp.43-59, 2015.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] G.H. Fonseca, H.G. Santos, "Variable neighborhood search-based algorithms for high school timetabling," Computers & Operations Research, Vol.52, pp.203-208, 2014.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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.