Educational Timetabling: Suggesting Timetable Perturbations

Educational timetabling poses a classic and important problem within Operations Research. Most research focuses on the static problem of timetabling entire semesters at a time, whereas research into more dynamic methods is scarce. Consequently, many timetabling systems lack proper support for assisting practical timetablers in changing established timetables. We propose and apply an approach for supporting timetablers in making focused changes to a timetable by providing perturbation suggestions based on their input. Suggestions focus on improving the timetable for specific entities while considering negative consequences for the timetable as a whole. We apply a Mixed Integer Programming (MIP) approach to the high school timetabling problem in Denmark. We show how to adapt such a MIP model to force timetable perturbations and to prefer positive changes for user-defined timetable entities. We also introduce an approximation of the implemented model and compare the two models through a series of computational tests performed on real-world data. The tests show that the approximation provides suggestions much more quickly and of only slightly lower quality.