Bi-criteria Simulated Annealing for the Curriculum-based Course Timetabling Problem With Robustness Approximation

Abstract

In the process of developing a university’s weekly course timetable, changes in the data, such as the available time periods of professors or rooms, render the timetable infeasible, requiring the administrators to repair or update the timetable. Since such changes almost always occur, it would be a sensible approach to identify a robust initial timetable, that is, one that can be repaired by making a limited number of changes, while still maintaining a high solution quality. This article formulates the problem as a bi-criteria optimization one, in which robustness is a stochastic objective, and the goal is to identify a good approximation to the Pareto frontier. It is assumed that multiple data changes, or disruptions, of multiple types can occur. The solution approach is a multi-objective simulated annealing (MOSA) algorithm, where a surrogate measure is used to approximate the robustness objective. Inspired by the concept of slack in machine and project scheduling, ten alternative measures of slack and a total of thirty surrogate measures are defined. Preliminary computational experiments are used to narrow the list of promising ones first to eight and then to two measures, which are then tested within a MOSA algorithm. Computational experiments show that one of these measures, when implemented in a multi-start MOSA algorithm, consistently provides the best Pareto frontier.