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] S. Ibrahim, M. H. Abdullah, and N. A. Rahman, “A general mathematical model for university courses timetabling: Implementation to a public university in malaysia,” Malaysian Journal of Fundamental and Applied Sciences, vol. 18, no. 1, pp. 1–10, 2022. doi: 10.11113/mjfas.v18n1.2408.

[2] H. Babaei, J. Karimpour, and A. Hadidi, “A survey of approaches for university course timetabling problem,” Computers & Industrial Engineering, vol. 86, pp. 43–59, 2015. doi: 10.1016/j.cie.2014.11.010.

[3] H. Rudová, T. Müller, and K. Murray, “Complex university course timetabling,” Journal of Scheduling, vol. 14, no. 2, pp. 187–207, 2011. doi: 10.1007/s10951-010-0171-3.

[4] M. H. Cruz-Rosales et al., “Metaheuristic with cooperative processes for the university course timetabling problem,” Applied Sciences, vol. 12, p. 542, 2022. doi: 10.3390/app12020542.

[5] W. A. U. D. Perera and G. H. J. Lanel, “A model to optimize university course timetable using graph coloring and integer linear programming,” IOSR Journal of Mathematics, vol. 12, no. 5, pp. 13–18, 2016. doi: 10.9790/5728-1205031318.

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

[7] 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. doi: 10.1016/S0377-2217(03)00103-6.

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

[9] Z. Lü and J. K. Hao, “Adaptive tabu search for course timetabling,” European Journal of Operational Research, vol. 200, no. 1, pp. 235–244, 2010. doi: 10.1016/j.ejor.2008.12.007.

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

[11] E. H. Kampke, L. M. Scheideger, G. R. Mauri, and M. C. S. Boeres, “A network flow based construction for a grasp-sa algorithm to solve the university timetabling problem,” in Computational Science and Its Applications – ICCSA 2019, Springer, 2019, pp. 215–231. doi: 10.1007/978-3-030-24302-9_16.

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

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

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

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

[16] A. E. Phillips, M. Ehrgott, and D. M. Ryan, “Integer programming methods for large-scale practical classroom assignment problems,” Computers & Operations Research, 2014. doi: 10.1016/j.cor.2014.07.012.

[17] P. Demeester and K. Goossens, “The examination timetabling problem: A new integer programming approach,” Computers & Operations Research, vol. 36, no. 6, pp. 1845–1856, 2009. doi: 10.1016/j.cor.2008.06.013.

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




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

Refbacks

  • There are currently no refbacks.


Copyright (c) 2026 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.