A novel event insertion heuristic for creating feasible course timetables

Wanka R, Mühlenthaler M (2010)


Publication Language: English

Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2010

Pages Range: 294-304

Conference Proceedings Title: Proc. 8th International Conference on the Practice and Theory of Automated Timetabling (PATAT)

Event location: Belfast

URI: https://www12.informatik.uni-erlangen.de/people/rwanka/publications/MW10b.php

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.

Authors with CRIS profile

How to cite

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: Download