Genetic Algorithm-Based University Course Timetabling: A Practical Optimization Framework with Graphical Interface

Nouhaila El machichi; Fouad Kharroubi; Hiba Massous; Salma  Ouali; Aymane EL youssfi

Authors

Nouhaila El machichi Department of Mathematics, ENS Rabat, Mohammed V University, Rabat, Morocco https://orcid.org/0009-0002-5547-3764
Fouad Kharroubi ENSIAS, Mohammed V University, Rabat, Morocco https://orcid.org/0000-0002-1112-7774
Hiba Massous Department of Mathematics, ENS of Rabat, Mohammed V University, Rabat, Morocco https://orcid.org/0009-0009-6233-0869
Salma Ouali Department of Mathematics, ENS of Rabat, Mohammed V University, Rabat, Morocco https://orcid.org/0009-0006-0763-397X
Aymane EL youssfi Department of Mathematics, ENS of Rabat, Mohammed V University, Rabat, Morocco

Keywords:

Genetic algorithms, Timetabling, Metaheuristics, Constraint satisfaction, University course scheduling

Abstract

This article investigates the university course timetabling problem, a challenging combinatorial optimization problem encountered by educational institutions when allocating courses to available time slots and classrooms while satisfying numerous institutional requirements. A mathematical formulation is proposed distinguishing between hard constraints (strictly enforced) and soft constraints (penalised to improve timetable quality). Owing to the NP-hard nature of the problem, exact optimization techniques become computationally prohibitive for large-scale instances. Consequently, a genetic algorithm is developed with constraint-aware operators and a repair mechanism to efficiently explore the search space and generate high-quality feasible timetables. The proposed approach is evaluated on two realistic datasets involving 15 and 69 courses, using 10 independent runs to ensure statistical robustness. Results show that the algorithm achieves (100%) hard constraint satisfaction, an average room occupancy of (78%), with only minimal soft constraint violations (1 capacity overbooking and 2 room-type mismatches out of 15 courses), and generates feasible timetables in 45 seconds—compared to 4 hours of manual effort. A graphical user interface equipped with performance indicators is introduced to facilitate result interpretation and support administrative decision-making. These findings demonstrate that genetic algorithms provide an effective practical solution for university timetabling, with potential for deployment in medium-sized institutions.

Downloads

Download data is not yet available.

References

L. Galli and S. Stille, “Modern challenges in timetabling,” in Handbook of Optimization in the Railway Industry, ser. International Series in Operations Research & Management Science, R. Borndorfer et al., Eds. Springer, 2018, vol. 268.

B. McCollum, A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. J. Parkes et al., “Setting the research agenda in automated timetabling: The second international timetabling competition,” INFORMS Journal on Computing, vol. 22, no. 1, pp. 120–130, 2010.

T. Müller, “ITC2007 solver description: a hybrid approach,” Annals of Operations Research, vol. 172, pp. 429–446, 2009.

R. Lewis, A Guide to Graph Colouring: Algorithms and Applications. Springer, 2021.

D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

S. S. Alves, S. A. Oliveira, and A. R. R. Neto, “A recursive genetic algorithm-based approach for educational timetabling problems,” in Designing with Computational Intelligence, ser. Studies in Computational Intelligence, N. Nedjah et al., Eds. Springer, 2017, vol. 664.

E. K. Burke, G. Kendall, and E. Soubeiga, “A tabu-search hyperheuristic for timetabling and rostering,” Journal of Heuristics, vol. 9, no. 6, pp. 451–470, 2003.

S. Broder, “Final examination scheduling,” Communications of the ACM, vol. 7, pp. 494–498, 1964.

N. Pillay, “A study into the use of hyper-heuristics to solve the school timetabling problem,” in Proc. SAICSIT ’10. ACM, 2010, pp. 258–264.

R. A. O. Vrielink, E. A. Jansen, E. W. Hans, and J. van Hillegersberg, “Practices in timetabling in higher education institutions: a systematic review,” Annals of Operations Research, vol. 275, pp. 145–160, 2019.

A. Wren, “Scheduling, timetabling and rostering—a special relationship?” in Proc. International Conference on the Practice and Theory of Automated Timetabling (PATAT 1995), 1995.

B. McCollum and N. Ireland, “University timetabling: Bridging the gap between research and practice,” in Proc. PATAT 2006, 2006.

E. K. Burke, P. Cowling, J. L. Silva, and B. McCollum, “Three methods to automate the space allocation process in UK universities,” in Proc. PATAT 2000, 2000.

S. N. Jat and S. Yang, “A guided search genetic algorithm for the university course timetabling problem,” Schneider-Brunel, Tech. Rep., 2009.

S. Even, A. Itai, and A. Shamir, “On the complexity of time table and multi-commodity flow problems,” in 16th Annual Symposium on Foundations of Computer Science, 1975.

M. Hidalgo-Herrero, P. Rabanal, I. Rodriguez, and F. Rubio, “Comparing problem solving strategies for NP-hard optimization problems,” Fundamenta Informaticae, vol. 124, no. 1-2, pp. 1–25, 2013.

A. Schaerf, “A survey of automated timetabling,” Artificial Intelligence Review, vol. 13, no. 2, pp. 87–127, 1999.

G. H. G. Fonseca, H. G. Santos, and E. G. Carrano, “Integrating matheuristics and metaheuristics for timetabling,” Computers & Operations Research, vol. 74, pp. 108–117, 2016.

A. Schaerf, “Local search techniques for large high school timetabling problems,” IEEE Transactions on Systems, Man, and Cybernetics - Part A, vol. 29, no. 4, pp. 368–377, 1999.

E. K. Burke and S. Petrovic, “Recent research directions in automated timetabling,” European Journal of Operational Research, vol. 140, no. 2, pp. 266–280, 2002.

E. K. Burke, B. McCollum, A. Meisels, S. Petrovic, and R. Qu, “A graph-based hyper-heuristic for educational timetabling problems,” European Journal of Operational Research, vol. 176, no. 1, pp. 177–192, 2007.

R. Qu, E. K. Burke, B. McCollum, L. T. G. Merlot, and S. Y. Lee, “A survey of search methodologies and automated system development for examination timetabling,” Journal of Scheduling, vol. 12, no. 1, pp. 55–89, 2009.

J. Thompson and K. A. Dowsland, “A robust simulated annealing based examination timetabling system,” Computers & Operations Research, vol. 25, no. 7-8, pp. 637–648, 1998.

M. Battistutta, S. Ceschia, F. D. Cesco, L. D. Gaspero, A. Schaerf, and E. Topan, “Local search and constraint programming for a real-world examination timetabling problem,” in CPAIOR 2020, ser. LNCS, E. Hebrard and N. Musliu, Eds., vol. 12296. Springer, 2020, pp. 69–81.

E. K. Burke, P. D. Causmaecker, G. V. Berghe, and H. V. Landeghem, “The state of the art of nurse rostering,” Journal of Scheduling, vol. 7, no. 6, pp. 441–499, 2004.

B. McCollum, P. McMullan, A. J. Parkes, E. K. Burke, and S. Abdullah, “An extended great deluge approach to the examination timetabling problem,” in Proc. 4th International Timetabling Competition (ITC 2007), 2007.

D. de Werra, “An introduction to timetabling,” European Journal of Operational Research, vol. 19, no. 2, pp. 151–162, 1985.

S. Daskalaki, T. Birbas, and E. Housos, “An integer programming formulation for a case study in university timetabling,” European Journal of Operational Research, vol. 153, no. 1, pp. 117–135, 2004.

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.

Z. Zhu, Y. Zhou, and Q. Luo, “A hyper-heuristic algorithm based on genetic and greedy strategy for university course scheduling problem,” Applied Soft Computing, 2025.

X. Pan, Z. Duan, and Y. Hu, “An improved genetic algorithm based on reinforcement learning for the university course timetabling problem,” in Proc. Tenth International Forum of Decision Sciences, ser. Uncertainty and Operations Research. Springer, 2023, pp. 513–523.

M. Elveny, S. M. Hardi, T. Rusydi Hega, and M. R. Harahap, “Enhanced class scheduling and classroom reservation with improved genetic algorithm (IGA),” in Proc. IEEE Conference on Computational Intelligence and Applications, Medan, Indonesia, 2025, pp. 1–6.

M. W. Carter and G. Laporte, “Recent developments in practical course timetabling,” Annals of Operations Research, vol. 67, no. 1, pp. 3–17, 1996.

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, 2nd ed. Springer, 2015.

J. Lewis, “A study on timetabling,” Journal of Scheduling, vol. 15, 2021.

T. Müller, H. Rudová, and Z. Müllerová, “Real-world university course timetabling at the international timetabling competition 2019,” Journal of Scheduling, vol. 28, pp. 247–267, 2025.

E. Cantú-Paz, Efficient and Accurate Parallel Genetic Algorithms. Kluwer Academic Publishers, 2000.

A. Zakouni, J. Luo, and F. Kharroubi, “Genetic algorithm and tabu search algorithm for solving the static manycast RWA problem in optical networks,” Journal of Combinatorial Optimization, vol. 33, pp. 726–741, 2017.

F. Kharroubi, J. He, J. Tang et al., “Evaluation performance of genetic algorithm and tabu search algorithm for solving the Max-RWA problem in all-optical networks,” Journal of Combinatorial Optimization, vol. 30, pp. 1042–1061, 2015.

A. Zakouni, J. Luo, and F. Kharroubi, “Random optimization algorithm for solving the static manycast RWA problem in optical WDM networks,” in Proc. IEEE International Conference on Information and Communication Technology Convergence (ICTC), Jeju, Korea (South), 2016, pp. 640–645.

S. K. Smit and A. E. Eiben, “Comparing parameter tuning methods for evolutionary algorithms,” in Proc. IEEE Congress on Evolutionary Computation, 2011, pp. 399–406.