Detailansicht

Adaptive large neighborhood search for the curriculum-based course timetabling problem

Alexander Kiefer

Art der Arbeit

Masterarbeit

Universität

Universität Wien

Fakultät

Fakultät für Wirtschaftswissenschaften

Betreuer*in

Richard F. Hartl

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.30840

URN

urn:nbn:at:at-ubw:1-29104.64528.205262-1

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Bei der Erstellung der Stundenpläne für Universitäten besteht die Aufgabe darin, Kurse, die Vortragende und Studenten betreffen, Perioden und Räume zuzuweisen. Zusätzlich müssen problemabhängige Nebenbedingungen berücksichtigt werden. Curriculum-based Course Timetabling (CB-CCT) kann als Variante des University Course Timetabling verstanden werden, das wiederum Educational Timetabling zuzuordnen ist. Die besondere Charakteristik von CB-CCT ist jene, dass Kurse desselben Curriculums teilweise von denselben Studenten besucht werden und deshalb nicht zeitgleich stattfinden dürfen. Üblicherweise hat jede Universität ihre eigenen Anforderungen an deren Stundenpläne. Aus diesem Grund wurden ursprünglich Algorithmen speziell für das vorliegende Problem der jeweiligen Universität entwickelt. Entsprechend war ein Vergleich der Algorithmen im Bezug auf deren Leistung kaum möglich. Die International Timetabling Competitions (ITC) von 2002 und 2007 versuchten deshalb mittels vereinfachter Problemformulierungen und Vergleichsinstanzen eine allgemeine Basis zu begründen. Stundenpläne für Universitäten zu erstellen ist typischerweise NP-schwer. Deshalb werden heuristische Verfahren benötigt, um große Probleme in vernünftiger Zeit lösen zu können. Die hier vorgestellte Lösungsmethode basiert auf Adaptive Large Neighborhood Search (ALNS). Hierbei wird in jeder Iteration ein relativ großer Teil der Lösung zerstört und anschließend wieder repariert. Der Algorithmus verwendet mehrere Zerstörungsoperatoren. Die resultierende Umgebung der Teillösung kann durch verschiedene Reparaturoperatoren untersucht werden. Die Auswahl der Zerstörungs- und Reparaturoperatoren basiert auf dem Erfolg der Operatoren in früheren Iterationen. Der Algorithmus kann sich dadurch an die jeweilige Probleminstanz anpassen. Neue Lösungen werden anhand von Simulated Annealing akzeptiert. ALNS erweist sich als leistungsstark für CB-CCT. Der hier beschriebene Algorithmus führt zu konkurrenzfähigen Ergebnissen bei den Vergleichsinstanzen. Insbesondere übertreffen die Resultate jene der besten Algorithmen der ITC-2007.

Abstract

(Englisch)

The task of generating timetables for universities consists of assigning courses involving teachers and students to periods and rooms. Additionally certain constraints have to be satisfied depending on the particular problem. Curriculum-based Course Timetabling (CB-CTT) is a variant of university course timetabling, which in turn is a category of educational timetabling. The main characteristic of CB-CTT is, that courses of the same curriculum have students in common. Consequently these courses must not be scheduled at the same time. Typically, universities define their own requirements on a timetable. As a result, algorithms were designed for specific problems of single universities. Consequently the algorithms' performances were hard to compare. Therefore, the international timetabling competitions (ITC) in 2002 and 2007 tried to build a common ground for comparison by defining simplified problem formulations and releasing benchmark instances. Generating university timetables is typically NP-hard. Therefore, it requires heuristic approaches to solve large problems in reasonable time. The solution method presented in this theses is based on Adaptive Large Neighborhood Search (ALNS). In each iteration a relatively large fraction of the solution is destroyed and subsequently repaired. The algorithm makes use of several destroy operators. The resulting neighborhoods can be explored by different repair operators. The selection of the destroy and repair operators is based on their performance in previous iterations. As a result, the algorithm adapts itself to the particular problem instance. New solutions are accepted according to Simulated Annealing. ALNS proves to be very effective for CB-CTT. The algorithm generates competitive results for the benchmark instances. In particular, ALNS outperforms the best algorithms of the ITC-2007.

Autor*innen

Alexander Kiefer

Haupttitel (Englisch)

Adaptive large neighborhood search for the curriculum-based course timetabling problem

Publikationsjahr

2013

Umfangsangabe

X, 79 S.

Sprache

Englisch

Beurteiler*in

Richard F. Hartl

Klassifikation

85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges

AC Nummer

AC11445116

Utheses ID

27451

Studienkennzahl

UA | 066 | 915 | |

Detailansicht

Abstracts

Schlagwörter