Evolutionary algorithms to solve the school timetabling problem

Abstract

Evolutionary Computation (EC) have been applied to a great number of optimisation problems with some success, specially in fields such as production operations in manufacturing industry, parallel and distributed systems, logistics and traffic. The Timetabling problem is a kind of three-dimensional cutting problems, but it can be considered as a kind of scheduling problems too.. The problem of creating a valid timetable involves scheduling classes, teachers and rooms into a fixed number of periods, in such a way that no teacher, class or room is used more than once per period. The EC mimics the process of natural selection, with the effect of creating a number of potentially optimal solutions to some complex search problem. This work shows an evolutionary approach to solve the school-timetabling problem. To ensure the birth of valid offspring this approach uses a population of decoders. Implementation details for a set of timetabling instances of distinct complexity, using evolutionary approaches to the problem, are shown.