Two solutions to the general timetable problem using evolutionary methods

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 the 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