INSPIRING FUTURES

Two solutions to the general timetable problem using evolutionary algorithms.

Paechter, Ben, Luchian, Henri, Cumming, Andrew and Petriuc, Mihai (1994) Two solutions to the general timetable problem using evolutionary algorithms. In: Proceedings of the IEEE World Congress in Computational Intelligence. IEEE, pp. 300-306. ISBN 0-7803-1899-4

Full text not available from this repository. (Request a copy)

Abstract/Description

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.

Item Type: Book Section
ISBN: 0-7803-1899-4
Uncontrolled Keywords: timetabling; neural networks; evolutionary algorithms; “Lamarckism";
University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods > 006.3 Artificial intelligence
Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Item ID: 3200
Depositing User: Computing Research
Date Deposited: 02 Aug 2010 15:12
Last Modified: 02 Aug 2010 15:12
URI: http://researchrepository.napier.ac.uk/id/eprint/3200

Actions (login required)

View Item

Edinburgh Napier University is a registered Scottish charity. Registration number SC018373