Improving a Heuristic Repair Method for Large-Scale School Timetabling Problems

Timetable construction is extremely difficult and time- consuming in large high-schools and universities. Even latest high-quality heuristic repair methods leave constraint violations to be fixed manually. This paper describes two improvements, initialization and repair. The improved initialization method applies a heuristic repair method whenever inconsistencies are found during the construction. The improved repair method escapes from local minima by moving two lectures at once in a way similar to the way billiard balls move. Evaluating these methods by using them on real high-school and university timetabling problems showed that they left between 30% and 97% fewer violations than a previous method left.