Optimization of University Course Timetabling Using a MILP Model and the Penalty Function Method
DOI:
https://doi.org/10.17308/econ.2026.2/13818Keywords:
system analysis, gaps, shadow price of resourcesAbstract
Subject. The problem of university course timetabling is considered as an object of system analysis and optimization, including resources, participants, hard and soft constraints, and quality criteria.
Purpose. To formulate a complete MILP model for timetabling with linear accounting of gaps and to compare the computational and methodological properties of the two approaches.
Methodology. We describe the timetabling system using the following components: (a) input data – a list of classes, instructors, student groups, rooms, and time slots; (b) rules/constraints – hard and soft; (c) output – assignment of classes to (room, time); (d) quality criteria – an aggregated objective function; (e) controllable parameters – penalty weights and resource prices. We implemented the problem formulation as a MILP model and its equivalent using the penalty function method.
Results. We considered a timetabling model is that includes sets and numerical parameters for courses, classrooms, time slots, as well as resource prices. Penalties are provided for time conflicts, instructor conflicts, and the presence of gaps in the schedule.
Conclusions. The presented MILP formulation of the university timetabling problem includes resource prices and linear accounting of gaps. It is shown how, using the penalty function method, constraints can be moved into the objective function, with the parameter ρ controlling the strictness of constraint satisfaction. A comparison of the two approaches shows that the MILP model provides structural transparency and provable optimality, while penalty functions are convenient for heuristics and flexible handling of soft constraints. For real-world problem sizes, matheuristics often offer the best compromise.
Downloads
References
Arias-Osorio, J., & Mora-Esquivel, A. (2020). A solution to the university course timetabling problem using a hybrid method based on genetic algorithms. DYNA-Colombia, 87(215), 47-56. DOI:10.15446/dyna.v87n215.85933
Babaei, H., Karimpour, J., & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43-59. DOI: 10.1016/j.cie.2014.11.010
Bertsekas, D. P. (1997). Nonlinear programming. Journal of the Operational Research Society, 48(3), 334-334.
Bratković, Z., Herman, T., Omrčen, V., Čupić, M., & Jakobović, D. (2009). University Course Timetabling with Genetic Algorithm: A Laboratory Excercises Case Study. In: Cotta, C., & Cowling, P. (eds). Evolutionary Computation in Combinatorial Optimization. EvoCOP. Lecture Notes in Computer Science, 5482, Berlin, Heidelberg: Springer Berlin Heidelberg, 240-251. DOI: 10.1007/978-3-642-01009-5_21
Caramia, M., & Giordani, S. (2020). Curriculum-Based Course Timetabling with Student Flow, Soft Constraints, and Smoothing Objectives: an Application to a Real Case Study. Operations Research Forum, 1(2), 11. DOI: 10.1007/s43069-020-0013-x
Ceschia, S., Di Gaspero, L., & Schaerf, A. (2023). Educational timetabling: Problems, benchmarks, and state-of-the-art results. European Journal of Operational Research, 308(1), 1–18. DOI: 10.1016/j.ejor.2022.07.011
Chen, M. C., Sze, S. N., Goh, S. L., Sabar, N. R., & Kendall, G. (2021). A survey of university course timetabling problem: perspectives, trends and opportunities. IEEE Access, (9), 106515–106529. DOI: 10.1109/ACCESS.2021.3100613
Holm, D. S., Mikkelsen, R. Ø., Sørensen, M., & Stidsen, T. J. R. (2022). A graph-based MIP formulation of the International Timetabling Competition 2019. Journal of Scheduling, 25(4), 405-428. DOI: 10.1007/s10951-022-00724-y
Jat, S. N., & Yang, S. (2009). A Guided Search Genetic Algorithm for the University Course Timetabling Problem. Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2009). Dublin, Ireland, 180-191.
Mahlous, A. R., & Mahlous, H. (2023). Student timetabling genetic algorithm accounting for student preferences. PeerJ. Computer Science, 9, e1200. DOI: 10.7717/peerj-cs.1200
Mikkelsen, R. Ø., & Holm, D. S. (2022). A parallelized matheuristic for the International Timetabling Competition 2019. Journal of Scheduling, 25(4), 429–452. DOI: 10.1007/s10951-022-00728-8
Müller, T., Rudová, H., & Müllerová, Z. (2025). Real-world university course timetabling at the International Timetabling Competition 2019. Journal of Scheduling, 28(2), 247–267. DOI: 10.1007/s10951-023-00801-w
Rappos, E., Thiémard, E., Robert, S., & Hêche, J.F. (2022). A mixed-integer programming approach for solving university course timetabling problems. Journal of Scheduling, 25(4), 391–404. DOI: 10.1007/s10951-021-00715-5
Rogachev, A. F., & Zakharov, D. S. (2025). A Systematic Approach to Ontology Construction for Automating the Scheduling of a Multilevel University. RUDN Journal of Engineering Research, 26(1), 39-51. DOI:10.22363/2312-8143-2025-26-1-39-51
Rogachev, D. A., & Rogachev, A. F. (2025). Structural-Parametric Synthesis of Controllers with Genetic Algorithms for Training Neural Networks Based on a Systematic Approach. In Radionov, A. A., & Gasiyarov, V. R. (eds). Advances in Automation VII. Lecture Notes in Electrical Engineering, 1521. Cham: Springer Nature Switzerland, 704-715. DOI: 10.1007/978-3-032-14742-4_61
Rogachev, D., Yurchenco, I., & Rogachev, A. (2023). Management and optimization of systematic water adjustment by economic-mathematic modeling methods and AI. In 2023 International Russian Automation Conference, IEEE, 888–893. DOI: 10.1109/RusAutoCon58002.2023.10272907
Romaguera, D., Plender-Nabas, J., Matias, Ju., & Austero, L. (2024). Development of a Web-based Course Timetabling System based on an Enhanced Genetic Algorithm. Procedia Computer Science, 234, 1714-1721. DOI:10.1016/j.procs.2024.03.177
Rossi-Doria, O., Sampels, M., Birattari, M., Chiarandini, M., Dorigo, M., Gambardella, L. M., Knowles, J., Manfrin, M., Mastrolilli, M., Paechter, B., Paquete, L., & Stützle, T. (2002). A Comparison of the Performance of Different Metaheuristics on the Timetabling Problem. In Burke, E., & De Causmaecker, P. (eds). Practice and Theory of Automated Timetabling IV. PATAT 2002. Lecture Notes in Computer Science, 2740, Berlin, Heidelberg: Springer Berlin Heidelberg, 329–351. DOI:10.1007/978-3-540-45157-0_22
Sylejmani, K., Gashi, E., & Ymeri, A. (2023). Simulated annealing with penalization for university course timetabling. Journal of Scheduling, 26(5), 497-517. DOI: 10.1007/s10951-022-00747-5
Tung Ngo, S., Jafreezal, J., Hoang Nguyen, G., & Ngoc Bui, A. (2021). A Genetic Algorithm for Multi-Objective Optimization in Complex Course Timetabling. In Proceedings of the 2021 10th International Conference on Software and Computer Applications, 229-237. DOI: 10.1145/3457784.3457821
Захаров, Д. С., & Рогачев, А. Ф. (2025). Статистический анализ функционирования модифицированных генетических алгоритмов для автоматизированного составления расписания многоуровневого вуза. Вестник Российского университета дружбы народов. Серия: Инженерные исследования, 26(3), 288-297. [Zakharov, D. S., & Rogachev, A. F. (2025). Statistical Analysis of the Performance of Modified Genetic Algorithms for Automated Compilation of a Multilevel University Scheduling. RUDN Journal of Engineering Research, 26(3), 288-297. (In Russian).] DOI: 10.22363/2312-8143-2025-26-3-288-297
