Pimmer, M. (2010). A timeslot-based heuristic approach to construct high-school timetables [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/160861
E186 - Institut für Computergraphik und Algorithmen
-
Date (published):
2010
-
Number of Pages:
86
-
Keywords:
stundenplanerstellung; heuristik
de
high-school timetabling; scheduling; maximum-weight clique problem
en
Abstract:
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.<br />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.<br />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.<br />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.<br />
de
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.<br />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 heuristic 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.<br />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.<br />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.<br />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.<br />