School timetabling problem under disturbances

• We present methods to solve the school timetabling problem under disturbances.
• A multi-objective approach is used to obtain stable schedules.
• We test the approaches with data of 5 different schools in The Netherlands.
• The methods presented avoid designing schedules from scratch as a disturbance occurs.
• The methods generate robust solutions of high quality for different types of schools.

School timetables are one or multiple times per year generated to assign class-teacher combinations to class rooms and timeslots. Post-publication disturbances such as absence of teachers typically pose a need for schedulers to rapidly implement some minor changes to avoid empty periods in the timetable. In this paper our aim is to define methods to efficiently solve the school timetabling problem under disturbances. We present three types of solution methods, namely a simple rule-of-thumb, a heuristic and an optimization approach. Exhaustive numerical experiments have been performed with data from five high schools in The Netherlands, each with their unique characteristics in number of classes, number of teachers and number of daily meetings. For each of the three methods we show advantages and disadvantages as well as the effects of resulting changes in the schedules.