Projekt

Allgemein
Das Problem der Zeitplanerstellung (Timetabling) besitzt zahlreiche Anwendungsbereiche, so zum Beispiel die Schulstundenplanung, die Personaleinsatzplanung oder die Stundenplanung an Universitäten. Aufgrund des großen Aufwands, den die manuelle Erstellung solcher Zeitpläne erfodert, besteht Bedarf nach einer automatisierten Vorgehensweise.
Daher wurden in den letzten Jahren verschiedene computergestützte Verfahren getestet und auch angewendet. Beispiele für solche Verfahren sind Genetische Algorithmen, Tabu Search, Constraint-Logische Programmierung oder diverse andere Heuristiken. Jedoch unterscheiden sich alle bisherigen Implementierungen der Algorithmen für Timetabling-Probleme in ihren Datenstrukturen und damit auch in ihrer Problemlösung, die an die jeweilige Datenstruktur angepasst werden muss.
Um den Beschreibungs- und Implementierungsaufwand für neue Timetabling-Probleme zu reduzieren sowie eine größere Vergleichbarkeit unterschiedlicher Timetabling-Probleme zu gewährleisten, wurde daher im Jahr 2002 zunächst eine formale Beschreibung des Timetabling-Problems vorgenommen. Daraus wurde eine allgemeine Timetabling-Sprache basiernd auf XML und ein Timetabling-Framework, implmentiert in Java, entwickelt, mit der beliebige Timetabling-Probleme beschrieben werden können. Für einen konkreten Planungzeitraum kann dann mit Hilfe eines Algorithmus ein Zeitplan erstellt werden.
Nächstes Forschungsziel wird der Vergleich unterschiedlicher Optimierungsverfahren sein, mit dem Ziel, die Eignung der Verfahren zur Erstellung von Zeitplänen zu untersuchen. Weiterhin ist die Untersuchung der Struktur von Zeitplanungsproblemen von Interesse, um Rückschlüsse auf die Lösbarkeit von Zeitplanungsproblemen unterschiedlicher Komplexität ziehen zu können.

Die Sammlung der Problembeschreibungen wurde überarbeitet und insbesondere die Beschränkungen zur Schulstundenplanerstellung um spezielle Constraits für Grund- und Haupt/Real-Schulen erweitert.