AN INTEGER LINEAR PROGRAMMING MODEL FOR MAXIMIZING PREFERENCE SATISFACTION IN UNIVERSITY TIMETABLING

Authors

  • Pitchaya Wiratchotisatian Department of Statistics, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand https://orcid.org/0000-0002-7482-1229
  • Nattapon Surasin Department of Statistics, Faculty of Science, Khon Kaen University, Khon Kaen, 40002, Thailand
  • Yanin Sareeso Khon Kaen University
  • Sarun Paisarnsrisomsuk Department of Computer Engineering, Faculty of Engineering, Khon Kaen University, Khon Kaen, 40002, Thailand https://orcid.org/0009-0002-4395-0834

DOI:

https://doi.org/10.55766/sujst12636

Keywords:

Course Timetabling, Integer Linear Programming, Allocation Optimization, University Scheduling, Gurobi

Abstract

Manual university course timetabling is a time-consuming, complex, and conflict-prone combinatorial optimization problem, widely recognized as NP-hard due to its intricate constraints. This research automates and optimizes this task for the Department of Statistics at our university using a novel Integer Linear Programming (ILP) model. Implemented in Python with the Gurobi solver, the model maximizes weighted instructor preferences while strictly adhering to hard constraints, including student cohorts, faculty availability, and room capacity, alongside specific pedagogical constraints necessitating consecutive periods for intensive subjects and non-consecutive days to optimize student study intervals. The model successfully scheduled all 27 courses to global optimality within 285.15 seconds, achieving a 0% MIP gap and an average preference satisfaction rate of 89.6%. The resulting system generates complete, conflict-free timetables that respect constraints such as lunch breaks and workload limits, demonstrating a significant improvement in efficiency and solution quality over traditional manual methods, offering a scalable solution applicable to broader academic contexts.

References

Alvarez-Valdes, R., Crespo, E., & Tamarit, J. M. (2002). Design and implementation of a course scheduling system using tabu search. European Journal of Operational Research, 137(3), 512-523. https://doi.org/10.1016/S0377-2217(01)00091-1

Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266-280. https://doi.org/10.1016/S0377-2217(02)00069-3

Burke, E., Elliman, D., & Weare, R. (1995). A hybrid genetic algorithm for highly constrained timetabling problems. In Proceedings of the 6th International Conference on Genetic Algorithms (ICGA’95) (pp. 605-610). Morgan Kaufmann.

Cooper, T. B., & Kingston, J. H. (1995). The complexity of timetable construction problems. In International Conference on the Practice and Theory of Automated Timetabling (pp. 281-295). Springer. https://doi.org/10.1007/3-540-61794-9_66

Elmohamed, M. S., Coddington, P., & Fox, G. (1997). A comparison of annealing techniques for academic course scheduling. In International Conference on the Practice and Theory of Automated Timetabling (pp. 92-112). Springer. https://doi.org/10.1007/BFb0055883

Gurobi Optimization, LLC. (2025). Gurobi optimizer reference manual (Version 13.0). Gurobi Optimization.

Harrabi, O., Siala, J. C., & Mrad, M. (2024). An optimisation-based system for the university course timetabling: A novel integer linear programming model. International Journal of Industrial and Systems Engineering, 46(2), 195-214. https://doi.org/10.1504/IJISE.2024.136412

Land, A. H., & Doig, A. G. (2009). An automatic method for solving discrete programming problems. In 50 years of integer programming 1958-2008: From the early years to the state-of-the-art (pp. 105-132). Springer. https://doi.org/10.1007/978-3-540-68279-0_5

Mallari, C. B., San Juan, J. L., & Li, R. (2023). The university coursework timetabling problem: An optimization approach to synchronizing course calendars. Computers & Industrial Engineering, 184, 109561. https://doi.org/10.1016/j.cie.2023.109561

Mittelmann, H. D. (2024). Decision tree for optimization software. Arizona State University.

Mokhtari, M., Vaziri Sarashk, M., Asadpour, M., Saeidi, N., & Boyer, O. (2021). Developing a model for the university course timetabling problem: A case study. Complexity, 2021, 9940866. https://doi.org/10.1155/2021/9940866

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. https://doi.org/10.1007/s10951-023-00801-w

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. (2003). A comparison of the performance of different metaheuristics on the timetabling problem. In E. Burke & P. De Causmaecker (Eds.), Practice and theory of automated timetabling IV: PATAT 2002 (Lecture Notes in Computer Science, Vol. 2740, pp. 329-351). Springer. https://doi.org/10.1007/978-3-540-45157-0_22

Talmor, I. (2024). Optimizing academic timetables using integer linear programming: A case study. Educational Sciences and Management, 2(3), 176-187. https://doi.org/10.56578/esm020305

Downloads

Published

2026-09-01

How to Cite

Wiratchotisatian, P., Surasin, N., Sareeso, Y., & Paisarnsrisomsuk, S. (2026). AN INTEGER LINEAR PROGRAMMING MODEL FOR MAXIMIZING PREFERENCE SATISFACTION IN UNIVERSITY TIMETABLING . Suranaree Journal of Science and Technology, 33(4), 010449(1–11). https://doi.org/10.55766/sujst12636

Issue

Vol. 33 No. 4 (2026): July - August

Section

Research Article

Categories

License

Copyright (c) 2026 Suranaree University of Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.