A Novel Event Insertion Heuristic for Creating
Feasible Course Timetables
Moritz Mühlenthaler
and
Rolf Wanka
Department of Computer Science
University of Erlangen-Nuremberg, Germany
{moritz.muehlenthaler,rwanka}@informatik.uni-erlangen.de
Abstract.
We propose a novel event insertion heuristic for finding feasible
solutions for instances of the University Course Timetabling Problem (UCTP).
We introduce and apply a new neighbourhood structure on partial
timetables that permits to approach a feasible timetable.
The key insight is that an event can be inserted in a time slot
if all the events conflicting with it are moved to other time slots.
In order to prevent our event insertion
heuristic from running into local optima, a simple perturbation strategy
is employed additionally.
Our experimental results show that our event insertion heuristic yields
superior results compared to
other state-of-the-art feasible solution generation algorithms for a large
number of corresponding
benchmark instances.
Full article in PDF (183 KB)
8th Int. Conf. on the Practice and Theory of Automated
Timetabling (PATAT) 2010, pp. 294-304.
Full conference proceedings PDF (596 pages)
BibTex entry
|