Constructing School Timetables Using Simulated Annealing: Sequential and Parallel Algorithms

TLDR

The school timetabling problem requires assigning classes, teachers, subjects, and rooms to a fixed set of time slots. The paper proposes using simulated annealing to solve the school timetabling problem. The authors implement simulated annealing, including a parallel version for multiprocessor execution, within a prototype timetabling environment. The parallel simulated annealing algorithm achieves faster solutions than the sequential counterpart, as shown by experimental results.

Abstract

This paper considers a solution to the school timetabling problem. The timetabling problem involves scheduling a number of tuples, each consisting of class of students, a teacher, a subject and a room, to a fixed number of time slots. A Monte Carlo scheme called simulated annealing is used as an optimisation technique. The paper introduces the timetabling problem, and then describes the simulated annealing method. Annealing is then applied to the timetabling problem. A prototype timetabling environment is described followed by some experimental results. A parallel algorithm which can be implemented on a multiprocessor is presented. This algorithm can provide a faster solution than the equivalent sequential algorithm. Some further experimental results are given.