Two solutions to the general timetable problem using evolutionarymethods

摘要

The general timetable problem, which involves the placing ofevents requiring limited resources into timeslots, has been approachedin many different ways. This paper describes two approaches to solvingthe problem using evolutionary algorithms. The methods allow not onlythe production of feasible timetables but also the evolution oftimetables that are `good' with respect to some user-specifiedevaluation function. A major concern of any approach to the timetableproblem is the large proportion of timetables in a search space wheresome resource is not available for some event. These timetables are saidto be infeasible. The methods described transform the search space intoone in which the proportion of feasible solutions is greatly increased.This new search space is then searched by an evolutionary algorithm. Thechromosomes used are encoded instructions on how to build a timetable ina way that leads to the above-mentioned search space transformation.“Lamarckism”, which allows information gained throughinterpretation of the chromosomes to be written back into thechromosomes, is also used. Test results, working with real worldtimetable requirements (for a university department's timetable), show avery fast evolution to a population of chromosomes which build feasibletimetables, and subsequently evolution of chromosomes which buildtimetables which are optimal or nearly optimal