[Back]

M. Pimmer:
"A timeslot-based heuristic approach to construct high-school timetables";
Supervisor: G. Raidl; Institut für Computergraphik und Algorithmen, 2010; final examination: 2010-12.

This master thesis describes an algorithm for creating high-school timetables. In the
history of high-school timetabling, interchangeable and common instances were missing.
Most scientists restricted their work to basic problem definitions, or to instances gathered
from schools nearby. In 2007, the School Benchmarking Project was launched to correct
this issue. A common XML file format and an evaluation function was defined, and scientists
of various countries contributed real-world instances. However, the format, evaluation
function and instances are still under development. We are going to test our algorithm using
these instances.
Our approach is to pick a non-full timeslot. We will then grade the favorability of all
meetings that can be held in this timeslot: All hard constraints and the goal of completely
filling the timetable have to be considered, as well as the soft-constraints, to obtain valid
solutions with low penalties. This information - the meetings and their grades, as well
as which meetings can be held simultaneously - is represented as a weighted graph. We
perform a heurisitc maximum weight clique search on this graph. If there are meetings
with open roles, one out of a certain set of resources shall be assigned, e.g. any english
teacher. This introduces an additional constraint to the maximum-weight clique search.
Before assigning the found clique - a hopefully favorable set of meetings - to the given
timeslot, all open roles are closed with a maximum-cardinalty maximum weight matching.
On top of this basic procedure, we are going to implement higher-level solving strategies.
We try to improve the quality of the timteable by partly refilling it or by reassigning
resources and meetings that cause penalty. There are various parameters that influence the
grading of constraints to construct the weighted graph for the clique search. As the suitability
of the parameters depends on the given instance, we are going to use a hill climbing
procedure to search for appropriate values for these parameters.
This work describes the given approach in detail. The advantages and disadvantages of
this timeslot-based algorithm will be discussed by evaluating it using the before-mentioned
instances. We are also going to present and discuss the results, which are the first results
published based on the School Benchmarking Project, as well as specifics of the format and
instances.
i

Die vorliegende Masterarbeit beschreibt einen Algorithmus zur Erstellung von Schul-
Stundenplänen. Austauschbare, internationale Problem-Instanzen waren in der Geschichte
des "high-school timetabling" oder "Berechnung von Schul-Stundenplänen" genannten Gebietes
kaum vorhanden. Viele Wissenschaftler beschränkten ihre Arbeit auf simplifizierte
Problemdefinitionen oder Instanzen aus Schulen der Umgebung. 2007 wurde das "School
Benchmarking Project" ins Leben gerufen, um diesen Mißstand zu beseitigen. Ein einheitliches
XML-Format sowie eine klare Evaluierungsfunktion wurden definiert, und dank
der Zusammenarbeit von Wissenschaftern verschiedenster Ländern sind heute eben diese
internationalen, austauschbaren Instanzen vorhanden. Diese Instanzen, die wir für die
Evaluierung unseres Algorithmus verwenden, sind teilweise noch ungetestet und in Entwicklung.
Im von uns verfolgten Ansatz werden wiederholt einzelne Stunden mit Unterrichtseinheiten
(Meetings) gefüllt. Zuerst werden alle in der jeweiligen Stunde vorhandenen Meetings
anhand ihrer Dringlichkeit und der vorhandenen Randbedingungen, wie z.B. der Vermeidung
von Freistunden, gewichtet. Dabei werden sowohl verpflichtenden Randbedingungen
(hard-constraints), und die Notwendigkeit einen kompletten Stundenplan zu erstellen,
als auch Wünsche (soft-constraints) berücksichtigt. Die vorhandenen und gewichteten Meetings
werden in einem gewichteten Graph dargestellt, bei dem Meetings verbunden sind
wenn diese gleichzeitig abgehalten werden können. Auf diesem Graph führen wir eine
heuristische Suche nach einer Clique mit dem maximalen Gewicht durch. Diese stellt eine
Menge von Meetings dar, deren Zuweisung zu der gegebenen Stunde dringlich und wünschenswert
ist. Bei der Cliquen-Suche müssen gegebenenfalls auch offene Rollen berücksichtigt
werden, die eine weitere Randbedingung darstellen: Offene Rollen bedeuten, dass
eine beliebige Ressource aus einer Menge an Ressourcen - zB ein beliebiger Englischlehrer
- einem Meeting zugeordnet werden muss. Beim Zuweisen der Meetings zu einer Unterrichtsstunde
werden alle offenen Rollen mit einem maximum-cardinalty maximum weight
matching - derjenigen größten Paarung die das höchste Gewicht aufweist - geschlossen.
Auf diese Basisprozedur setzen generellere Algorithmen auf. Der Stundenplan wird teilweise
neu gefüllt, indem beispielsweise problematische Ressourcen oder Meetings neu
zugeteilt werden. Gute Werte für die Parameter der Bewertungsfunktion von Meetings
sind von der jeweiligen Instanz abhängig. Um geeignete Parameter zu finden wird ein "hill
climbing"-Algorithmus angewendet.
In dieser Arbeit wird der Unterrichtsstunden-basierte Algorithmus im Detail vorgestellt.
Die Vor- und Nachteile dieses Ansatzes werden anhand der Evaluierung an den zuvor erwähnten
Instanzen präsentiert. Neben den Resultaten, welche die ersten veröffentlichten
Ergebnisse dieser Instanzen darstellen, werden auch länder- und instanzabhängige Spezifika
sowie das XML-Format im Allgmeinen diskutiert.
ii

http://publik.tuwien.ac.at/files/PubDat_190513.pdf