Edinburgh Napier University

  The general timetable problem, which involves the placing
of events requiring limited resources into timeslots,
has been approached in many different ways. This paper
describes two approaches to solving the problem using
evolutionary algorithms. The methods allow not only
rhe production of feasible timetables but also the evolution
of timetables that are ‘good’ with respect to some
user specified evaluation function. A major concern of
any approach to the timetable problem is the large proportion
of timetables in a search space where some
resource is not available for some event. These timetables
are. said to be infeasible. The methods described
transform the search space into one in which the proportion
of feasible solutions is greatly increased. This new
search space is then searched by an evolutionary algorithm.
The chromosomes used are encoded instructions
on how to build a timetable in a way that leads to the
above mentioned search space transformation.
“Lamarckism” which allows information gained
through interpretation of the chromosomes to be written
back into the chromosomes, is also used. Test results,
working with real world timetable requirements (for a
university department’s timetable), show a very fast
evolution to a population of chromosomes which build
feasible timetables, and subsequently evolution of chromosomes
which build timetables which are optimal or
nearly optimal.