University Scheduling Optimization Using Integer Programming: A Case Study

Gayus Simarmata, Rajainal Saragih, Anil Hakim Syofra

Abstract


This paper presents an Integer Linear Programming (ILP) model to construct a weekly lecture timetable for the Mathematics Study Program at HKBP Nommensen University, Pematangsiantar. The case study comprises 25 courses, three rooms (RK~11, RK~12, and LAB~1), five teaching days (Monday--Friday), and 13 time periods per day. The model enforces hard constraints on room, lecturer, and cohort non-overlap; consecutive periods according to credit load; room-type compatibility between theory and practicum sessions; and an institutional worship-time restriction on Tuesday. Lecturers' availability is represented by a binary acceptance matrix collected at the course level, and rejected time periods are penalized in the objective. The ILP is implemented in Python using the PuLP (Python Linear Programming) library and solved with the CBC (Coin-or Branch and Cut) solver. For the real instance, the solver returns an optimal solution with objective value $Z^*=0$ (no scheduled period falls in a rejected slot) in approximately 94 seconds. The resulting timetable is conflict-free and operationally interpretable, with a weekly room-time utilization of about 31.3\%. To support verification and communication to stakeholders, the paper also provides a heatmap of the acceptance matrix and a graphical timetable by room and day.

Keywords


Branch-and-cut; Course timetabling; Integer linear programming; PuLP; University scheduling

Full Text:

PDF

References


[1] Ibrahim, S., Abdullah, MH, & Rahman, NA (2022). A general mathematical model for university courses timetabling: Implementation to a public university in Malaysia. Malaysian Journal of Fundamental and Applied Sciences, 18 (1), 1–10. https://doi.org/10.11113/mjfas.v18n1.2408

[2] Babaei. H., Karimpour. J., and Hadidi. A., “A Survey of Approaches for University Course Timetabling Problem”, Computers & Industrial Engineering, vol. 86, pp. 43-59, 2015. [Online]. Available , https://doi.org/10.1016/j.cie.2014.11.010

[3] Fong, CW, Asmuni, H., & McCollum, B. 2015. A hybrid swarm-based approach to university timetabling. IEEE Transactions on Evolutionary Computation , vol. 19 , pp. 870–884. https://doi.org/10.1109/TEVC.2015.2411741

[4] Cruz-Rosales, M.H., Cruz-Chávez, M.A., Alonso-Pecina, F., Peralta-Abarca, J. d. C., Ávila Melgar, E.Y., Martínez-Bahena, B., & Enríquez-Urbano, J. 2022. Metaheuristic with cooperative processes for the university course timetabling problem. Applied Sciences, vol. 12, pp. 542. https://doi.org/10.3390/app12020542

[5] Kampke, EH, Scheideger, LM, Mauri, GR, & Boeres, MCS 2019. A network flow based construction for a grasp sa algorithm to solve the university timetabling problem. In Computational science and its applications–ICCSA 2019: Proceedings of the 19th international conference, part III (pp. 215–231). Springer https://doi.org/10.1007/978-3-030-24302-9_16

[6] Guzman, G. A., Martínez, C., & Pacheco, J. (2015). An integer linear programming model for a university timetabling problem considering time windows and consecutive periods. Journal of Applied Operational Research , vol. 6(3), pp. 159– 167. https://doi.org/10.48287/2310-5070.2023.121

[7] Ceschia, RM Rosati, A. Schaerf, P. Smet, G. Vanden Berghe, E. Zanazzo, The i Integrated Healthcare Timetabling Competition 2024 – Problem description and rules, in: Proceedings of the 14 th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2024, 2024, vol. 25, pp. 52 – 65. https://doi.org/10.1016/j.ordal.2025.200481

[8] Lü, Z., & Hao, J. K. (2010). Adaptive Tabu Search for Course Timetabling. European Journal of Operational Research, vol. 200(1), pp. 235-244. https://doi.org/10.1016/j.ejor.2008.12.007

[9] Chen, R. M. (2013). Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search. Algorithms, 6(2), 227–244. https://doi.org/10.3390/a6020227

[10] Rudová, H., Müller, T., & Murray, K. (2011). Complex university course timetabling. Journal of Scheduling, vol. 14(2), pp. 187–207. https://doi.org/10.1007/s10951-010-0171-3

[11] Asmuni, H., Burke, E.K., & McCollum, B. (2020). A practical three-phase ILP approach for solving the examination timetabling problem. International Transactions in Operational Research, vol. 27 (2), pp. 924–944. https://doi.org/10.1111/itor.12471

[12] Al-Shihri, F., & Al-Thoheir, A. (2007). A mixed integer programming model for university course scheduling. Journal of King Saud University – Computer and Information Sciences , vol. 19(2), pp. 53–62. https://doi.org/10.1016/j.jksuci.2007.02.002

[13] Lewis, R. 2008. A survey of metaheuristic-based techniques for university timetabling problems. OR Spectrum, vol 30, pp. 167–190. https://doi.org/10.1007/s00291-007-0097-0

[14] Rappos, E., Barták, R., & Burke, E.K. (2022). A mixed-integer programming approach for solving university course timetabling problems. Journal of Scheduling, vol. 25, pp. 391–404. https://doi.org/10.1007/s10951-021-00715-5

[15] McCollum, B. (2007). A perspective on bridging the gap between theory and practice in university timetabling. Practice and Theory of Automated Timetabling VI, Lecture Notes in Computer Science, vol. 3867, pp. 3–23. https://doi.org/10.1007/978-3-540-77345-0_1

[16] Antony E. Phillips, HW, Matthias Ehrgott and David M. Ryan, Integer programming methods for large-scale practical classroom assignment problems. Computers & Operations Research, 2014. https://doi.org/10.1016/j.cor.2014.07.012

[17] Daskalaki, S., Birbas, T., & Housos, E. (2004). An Integer Programming Formulation for A Case Study in University Timetabling. European Journal of Operational Research , vol. 153(1), pp. 117–135. https://doi.org/10.1016/S0377- 2217(03)00103-6

[18] Hutomo, AR, Fitrananda, A., Marshadiany, A., Prikarti, GP, & Imah, EM (2011). Implementation of Integer Linear Programming Algorithm for Room Scheduling Information System at Faculty of Computer Science, University of Indonesia. Information Systems Journal, vol. 7(1), pp. 25–33. https://media.neliti.com/media/publications/131947-ID-none.pdf

[19] Feng, X., Lee, Y., & Moon, I. 2017. An integer program and a hybrid genetic algorithm for the university timetabling problem. Optimization Methods & Software , vol. 32 , pp. 625–649. https://doi.org/10.1080/10556788.2016.1233970

[20] MJF Souza, N. Maculan, LS Ochi, A grasp-tabu search algorithm for solving school timetabling problems, in: Maurício GC Resende; Jorge Pinho de Sousa. (Org.). METAHEURISTICS: Computer Decision Making. Dordrech: Kluwer Academic Publishers, 2004, pp. vol 86, pp. 659–672. https://doi.org/10.1007/978-1- 4757-4137-7_31

[21] Perera, WAUD, & Lanel, G.H.J. (2016). A Model to Optimize University Course Timetable Using Graph Coloring and Integer Linear Programming. IOSR Journal of Mathematics, vol. 12(5), pp. 13–18. https://doi.org/10.9790/5728- 1205031318

[22] Tripathy, A. (1984). School timetabling A case in large binary integer linear programming. Management Science, vol. 30(12), pp. 1473–1489. https://doi.org/10.1287/mnsc.30.12.1473

[23] Hossain, S.I., et al. (2019). Optimization of university course scheduling problem using particle swarm optimization with selective search. Expert Systems with Applications, vol. 127, pp. 9–24. https://doi.org/10.1016/j.eswa.2019.02.026

[24] Bakir, M., & Aksop, C. (2008). A 0-1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, vol. 7(1), pp. 41– 55. https://dergipark.org.tr/en/pub/hujms/issue/7771/531004

[25] Wahid, A., & Hussin, H. (2015). Hybrid harmony search algorithm for the course timetabling problem. In 2015 international conference on science and engineering technology (ICSET) (pp. 1–5). IEEE. https://doi.org/10.1007/s10479-010-0769-z

[26] T. Müller, H. Rudová, Z. Müllerová, Real-world university course timetabling at the International Timetabling Competition 2019, J. Sched. 2024 21p. vol 28, pp. 247-267. https://doi.org/10.1007/s10951-023-00801-w

[27] Brandt, J., et al. (2022). An integrated patient-to-room and nurse-to-patient assignment problem in hospitals. Journal of Scheduling. https://doi.org/10.48550/arXiv.2309.10739

[28] Fong, C.W., Asmuni, H., & McCollum, B. 2015. A hybrid swarm-based approach to university timetabling. IEEE Transactions on Evolutionary Computation , vol. 19, pp. 870–884. https://doi.org/10.1109/TEVC.2015.2411741

[29] Demeester, P., & Goossens, K. (2009). The examination timetabling problem: A new integer programming approach. Computers & Operations Research, vol. 36(6), pp. 1845– 1856. https://doi.org/10.1016/j.cor.2008.06.013

[30] Süre, T. (2015). Mixed Integer Linear Programming approach for the course timetabling problem: A real case study. Proceedings of the International Conference on Industrial Engineering and Operations Management (IEOM), Paris. https://doi.org/10.1109/IEOM.2015.7093735




DOI: https://doi.org/10.18860/cauchy.v11i1.37815

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 Gayus Simarmata, Rajainal Saragih, Anil Hakim Syofra

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

Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Gajayana Street 50 Malang, East Java, Indonesia 65144
Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id

Creative Commons License
CAUCHY: Jurnal Matematika Murni dan Aplikasi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.