Friedrich-Alexander-Universität DruckenUnivisEnglish FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Codesign
Lehrstuhl für Informatik 12
MW10b
Department Informatik  >  Informatik 12  >  Personal  >  Rolf Wanka  >  Veröffentlichungen  >  MW10b

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


  Impressum Stand: 30 October 2010.   R.W.