University Scheduling Optimization Using Integer Programming: A Case Study

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.