A novel event insertion heuristic for creating feasible course timetables

Beitrag bei einer Tagung
(Konferenzbeitrag)


Details zur Publikation

Autorinnen und Autoren: Wanka R, Mühlenthaler M
Jahr der Veröffentlichung: 2010
Tagungsband: Proc. 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT)
Seitenbereich: 294-304
Sprache: Englisch


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Mühlenthaler, Moritz Dr.-Ing.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)
Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Zitierweisen

APA:
Wanka, R., & Mühlenthaler, M. (2010). A novel event insertion heuristic for creating feasible course timetables. In Proc. 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT) (pp. 294-304). Belfast.

MLA:
Wanka, Rolf, and Moritz Mühlenthaler. "A novel event insertion heuristic for creating feasible course timetables." Proceedings of the 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT), Belfast 2010. 294-304.

BibTeX: 

Zuletzt aktualisiert 2018-10-08 um 00:53