Research Output

Two solutions to the general timetable problem using evolutionary algorithms.

  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.

  • Type:

    Book Chapter

  • Date:

    30 November 1993

  • Publication Status:

    Published

  • Publisher

    IEEE

  • DOI:

    10.1109/ICEC.1994.349935

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

Citation

Paechter, B., Luchian, H., Cumming, A. & Petriuc, M. (1993). Two solutions to the general timetable problem using evolutionary algorithms. In Proceedings of the IEEE World Congress in Computational Intelligence, 300-305. IEEE. doi:10.1109/ICEC.1994.349935. ISBN 0-7803-1899-4

Authors

Keywords

timetabling; neural networks; evolutionary algorithms; “Lamarckism";

Available Documents