Two solutions to the general timetable problem using evolutionary algorithms.

Paechter, Ben; Luchian, Henri; Cumming, Andrew; Petriuc, Mihai

Abstract

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.

Citation

Paechter, B., Luchian, H., Cumming, A., & Petriuc, M. (1994, June). Two solutions to the general timetable problem using evolutionary algorithms. Presented at First IEEE Conference on Evolutionary Computation, 1994 IEEE World Congress on Computational Intelligence

• Conference Name: First IEEE Conference on Evolutionary Computation, 1994 IEEE World Congress on Computational Intelligence
• Start Date: Jun 27, 1994
• End Date: Jun 29, 1994
• Publication Date: 1994
• Deposit Date: Aug 2, 2010
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 1
• Pages: 300-305
• Book Title: Proceedings of the IEEE World Congress in Computational Intelligence
• ISBN: 0-7803-1899-4
• DOI: https://doi.org/10.1109/ICEC.1994.349935
• Keywords: timetabling; neural networks; evolutionary algorithms; “Lamarckism"
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/3200