Document Type : Original Article


1 Department of Applied Mathematics, Faculty of Basic Sciences, Islamic Azad University of Arsanjan Branch, Arsanjan, Iran.

2 Department of Optimization, Faculty of Mathematical Sciences, Shiraz University of Technology, Shiraz, Iran.

3 Department of Optimization, Faculty of Mathematical Sciences, Shiraz University of Technology, Shiraz, Iran


Purpose: This paper presents a new two-phase method for solving the curriculum-based university course timetabling problem. A new metaheuristic approach is used in both phases of the new present method.
Methodology: A feasible, high-quality solution is computed in the first phase of the new method. To this end, the hard constraints relating to the periods are considered, and a solution is computed that satisfies these hard constraints. In the next step, a new method is introduced for assigning rooms to courses, after which a feasible solution is calculated based on the solution that satisfies the period's hard constraints. In the second phase, several new neighbourhood functions are used to improve the quality of computed feasible solutions. While the fitness function of the first phase is based on the violation of hard constraints, the fitness function of the second phase is based on the penalty of the feasible solution.
Findings: The numerical results indicate that the required computing time increases with the size of instances, and the algorithm tends to converge towards the optimal solution after a few minutes.
Originality/Value: The presented algorithm enables us to deal with extensive university course timetabling problems in practice. Moreover, it provides us with an efficient way to obtain feasible solutions to such real-world instances and try to improve their quality.


Avella, P., & Vasil'Ev, I. (2005). A computational study of a cutting plane algorithm for university course timetabling. Journal of Scheduling, 8(6), 497-514.
Ceschia, S., Di Gaspero, L., & Schaerf, A. (2022). Educational timetabling: problems, benchmarks, and state-of-the-art results. European journal of operational research.‏ 0377-2217.
Chen, R. M., & Shih, H. F. (2013). Solving university course timetabling problems using constriction particle swarm optimization with local search. Algorithms, 6(2), 227-244.
Daskalaki, S., & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European journal of operational research, 160(1), 106-120.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European journal of operational research, 153(1), 117-135.
Gaspero, L. D., & Schaerf, A. (2002). Multi-neighbourhood local search with application to course timetabling. International conference on the practice and theory of automated timetabling. (pp. 262-275). Springer, Berlin.
Lemos, A., Monteiro, P. T., & Lynce, I. (2021). Disruptions in timetables: a case study at universidade de Lisboa. Journal of scheduling, 24(1), 35-48.
Martin, C. H. (2004). Ohio university's college of business uses integer programming to schedule classes. Interfaces34(6), 460-465.‏
Nguyen, K., Nguyen, Q., Tran, H., Nguyen, P., & Tran, N. (2011). Variable neighborhood search for a real-world curriculum-based university timetabling problem. Third international conference on knowledge and systems engineering (pp. 157-162). IEEE.
Qualizza, A., & Serafini, P. (2004). A column generation scheme for faculty timetabling. International conference on the practice and theory of automated timetabling, (pp. 161-173). Springer.
Schimmelpfeng, K., & Helber, S. (2007). Application of a real-world university-course timetabling model solved by integer programming. Or Spectrum, 29(4), 783-803.
Suyanto, S. (2010, June). An informed genetic algorithm for university course and student timetabling problems. Proceedings of the 10th international conference on Artifical intelligence and soft computing: Part II (pp. 229-236).