Review and analysis of existing methods of scheduling classes
151 182
Keywords:
UCTP, table creation methods, meta-heuristics, hyperheuristics, combinatorial optimization.Abstract
One of the most important steps in organizing the quality of the educational process in educational institutions and the effectiveness of the use of scientific and pedagogical potential is the task of forming a high-quality lesson schedule. A qualitatively designed lesson schedule should ensure the uniform loading of student groups and teaching staff.
The problem of university course planning (UCTP) is a specific problem of course planning at a university, with simultaneous use of resources such as students, faculty, and classrooms. These problems are considered non-polynomial time (NP) and Combinatorial Optimization (COP) problems, which means that they can be solved by optimization algorithms to obtain the desired table. Several methods have been used in universities to solve table problems, and most of them use optimization methods.
This article discusses six methods for solving problems with the schedule of classes in universities: Sequential methods, сluster methods, сonstraint-based methods, meta-heuristic methods, generalized search, hybrid evolutionary algorithms, multi-criteria approaches, case-based reasoning techniques, hyper-heuristics, adaptive approaches. The purpose of this article is a comprehensive review of optimization approaches to solving the problems of scheduling in universities. In addition, when solving such problems, the accepted algorithms for Meta-heuristic optimization are shown. In addition, methods have been developed to analyze and measure the performance of a solution by specifying frequently used control data sets.
References
REFERENCES
A. Bashab, A.O. Ibrahim, E.E. Abedelgabar, M.A. Ismail, A. Elsafi, etc., «A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms», Neural Computing and Applications, vol.32, no.23, P. 17397–17432. – 2020.
J.S. Tan, S.L. Goh, G. Kendall and N.R. Sabar, «A survey of the state-of-the-art of optimization methodologies in school timetabling problems», Expert Systems with Applications, vol.165, Article no. 113943, – 2021.
M.C. Chen, S.L. Goh, N.R. Sabar and G. Kendall «A survey of university course timetabling problem: perspectives, trends, and opportunities», IEEE Access, vol. 9, P. 106515–106529. – 2021.
S. Mir Hassani and F. Habibi «Solution approaches to the course timetabling problem» Artificial Intelligence Review, vol. 39, no.2, P. 133–149. – 2013.
T. Arbaoui, «Modeling and solving university timetabling», PhD. Dissertation, the University of Technology Compienge. – 2014.
B.A. Aldeeb, N.M. Norwawi, M.A. Al-Betar and M.Z.B. Jali, «Solving university examination timetabling problem using intelligent water drops algorithm», in Int. Conf. on Swarm, Evolutionary, and Memetic Computing, Cham, Springer, P. 187–200. – 2014.
C.W. Fong, H. Asmuni, B. McCollum, P. McMullan and S. Omatu «A new hybrid imperialist swarm-based optimization algorithm for university timetabling problems» Information Sciences, vol. 283, P. 1–21. – 2014.
S. Kristiansen and T.R. Stidsen «A comprehensive study of educational timetabling-A survey», Department of Management Engineering, Technical University of Denmark, DTU Management Engineering Report, no.8, – 2013.
T. Muller «Real-life examination timetabling» Journal of Scheduling, vol. 19, no.3, P. 257–270. – 2016.
K. Kalita, R.K. Ghadai and S. Chakraborty «A comparative study on the metaheuristic-based optimization of skew composite laminates», Engineering with Computers, vol.38, P. 3549–3566. – 2022.
J. Henry Obit, «Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems», PhD Dissertation, University of Nottingham, Nottingham NG8 1BB, UK. – 2010.
E.A. Abdelhalim and G.A. El Khayat «A utilization-based genetic algorithm for solving the university timetabling problem» Alexandria Engineering Journal, vol. 55, no.2, P. 1395–1409. – 2016.
X.S. Yang «Swarm intelligence based algorithms: A critical analysis», Evolutionary Intelligence, vol.7, no. 1, P. 17–28. – 2014.
S.N. Tung, J.B. Jaafar, I.A. Aziz, H.G. Nguyen and A.N. Bui «Genetic algorithm for solving multi-objective optimization in examination timetabling problem», International Journal of Emerging Technologies in Learning, vol.16, no.11, P. 4–24. – 2021.
