A fix-and-optimize heuristic for the high school timetabling problem

The high school timetabling is a classical combinatorial optimization problem that takes a large number of variables and constraints into account. Due to its combinatorial nature, solving medium and large instances to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Among the different requirements that are considered in Brazilian schools, two compactness requirements must be met on a teacher׳s schedule: the minimization of working days and the avoidance of idle timeslots. In this paper, we present a mixed integer linear programming model and a fix-and-optimize heuristic combined with a variable neighborhood descent method. Our method uses three different types of decompositions - class, teacher and day – in order to solve the high school timetabling problem. The method is able to find new best known solutions for seven instances, including three optimal ones. A comparison with results reported in the literature shows that the proposed fix-and-optimize heuristic outperforms state-of-the-art techniques for the resolution of the problem at hand.