Minimum Penalty Perturbation Heuristics for Curriculum-Based Timetables Subject to Multiple Disruptions

Abstract

Course timetables are often rendered infeasible due to unexpected changes in requirements and must be repaired. Given an initial timetable, planners prefer a repaired timetable whose quality is worsened as little as possible while its structural difference is also as little as possible. This paper formulates this problem as one of minimizing the quality degradation subject to an upper limit on the structural difference and presents one simulated annealing algorithm and a set of integer programming-based algorithms to solve it. These algorithms are tested on instances comprised of the ITC-2007 curriculum-based course timetabling test-bed and a set of randomly generated disruption scenarios, where each disruption scenario is based on a set of four disruption types that affect teacher and room availability. The results are analyzed with respect to two main goals, one being repairing a timetable after a single disruption scenario, and the other being the calculation of an estimated robustness of a solution based on a sample of disruption scenarios.