Ziele der Arbeit und Überblick

Die vorliegende Arbeit stellt die erste ausführlichere Untersuchung zum Gebiet der automatischen Stundenplanerstellung am Institut für Informatik dar und dient in erster Linie dazu, neben einem umfassenden Überblick den Rahmen der Anwendbarkeit vorhandener Theorien innerhalb dieses Gebietes zu sondieren. Zweites Ziel ist es, durch die Erstellung eines Programms zur automatischen Stundenplanerstellung erste praktische Erfahrungen mit Implementierungen zu gewinnen, die über die Ansprüche eines Prototyps zum Algorithmentest hinausgehen, und in diesem Rahmen die Funktionsfähigkeit verschiedener Lösungsmethoden zu untersuchen.

Angestrebt wurde hierbei ein Programm, das sowohl den Anforderungen einer Realschule, als auch denen einer Fachhochschule gerecht werden würde. Da bei ersteren der Klassenunterricht überwiegt, während bei letzteren verstärkt Kursunterricht auftritt, umfassen die Anforderungen damit auch die Ansprüche von Gymnasien und Gesamtschulen. Die somit erfolgte Konkretisierung der Anforderungen ist Garant dafür, daß der dringend notwendige Praxisbezug bei der Betrachtung der Verfahren nicht vernachlässigt werden kann, während die Unterschiedlichkeit der Voraussetzungen dennoch eine ausreichende Allgemeinheit sichert.

Die Arbeit gliedert sich in drei Teile, wobei der erste Stand und Möglichkeiten der Entwicklung referiert, während die beiden anderen sich mit den im Rahmen dieser Arbeit entwickelten Verfahren befassen:

Der erste Teil gibt in Kapitel 2 zunächst einen Überblick über die verschiedenen Probleme, die unter dem Begriff der automatischen Stundenplanerstellung zusammengefaßt werden und führt den benötigten Begriffsapparat ein. Des weiteren wird aufgezeigt, daß einige der zunächst verschieden scheinenden Problemstellungen übereinstimmen.
In Kapitel 3 wird die Komplexität des Problems untersucht, wobei insbesondere die Nichtapproximierbarkeit unter den bisher formulierbaren Nebenbedingungen betrachtet wird. Die hier feststellbaren Eigenschaften lassen die Tatsache, daß alle Schulen über einen funktionsfähigen Stundenplan verfügen, erstaunlich erscheinen, was darauf hindeutet, daß es weitere noch nicht identifizierte Nebenbedingungen geben muß (Abschnitt 3.7 S. ). Es wird ebenfalls kurz auf die Komplexität verschiedener Teilprobleme eingegangen.
In Kapitel 4 folgt dann eine Übersicht über die bisher eingesetzten Lösungsverfahren, wobei hier ein kleiner Schwerpunkt bei graphentheoretischen Ansätzen liegt, da auf einen relativ neuen Satz eingegangen wird, der bisher im Timetablingnoch keine Beachtung gefunden zu haben scheint (Abschnitt 4.3.4 S. ). Außerdem wird hier für eine große Zahl erfolgversprechend scheinender Verfahren die meist einen möglichen Einsatz auschließende Grenze ihrer Anwendbarkeit nachgewiesen.

Der zweite Teil beschreibt die in dieser Arbeit näher untersuchten Lösungsverfahren.
In Kapitel 5 wird zunächst ein Überblick über das Gesamtkonzept gegeben und das verwendete Modell, sowie die betrachteten Zielfunktionen werden diskutiert. Ebenso wird hier aufgezeigt, wie sich die im Rest dieses Teils untersuchten Verfahren in die Struktur des Gesamtprogramms einfügen.

Das erste Verfahren (Kapitel 6) folgt dem aktuell meistversuchten Ansatz, der Tabusuche, wobei diese zusätzlich mit einem komplexen graphentheoretischen Ansatz hybridisiert wurde (Abschnitt 6.6 S. ). Hier wurde basierend auf einer genauen Betrachtung des Lösungsraums eine neue Form der Tabuliste eingesetzt.
Das zweite Lösungsverfahren basiert auf einer neuen Methode, die unter anderem durch das Verfahren von BACHEM [BHM96] inspiriert wurde. Hier werden in Kapitel 7 ausgehend von dem bei BACHEM beschriebenen heuristischen Verfahren, das auf der Simulation einer Handelssituation beruht, die Möglichkeiten einer theoretischen Fundierung untersucht und eine erste Testimplementierung vorgenommen.

Der dritte Teil geht auf die Struktur und auf die wesentlichen Algorithmen des im Rahmen der Arbeit erstellten Programms ein.
Hierbei werden in Kapitel 8 sowohl die verwendeten Datenstrukturen, als auch die Entscheidungen, die zur Festlegung der Semantik einiger Operationen notwendig waren, dokumentiert. Da benutzerfreundliche Dialoge und Eingabemöglichkeiten vorgesehen wurden und somit auch Konsistenzprüfungen und Eingabeinterpretationen notwendig waren, erreichen Teile dieses Rahmenprogramms durchaus auch die Komplexität, die man eigentlich nur in den Lösungsverfahren vermuten würde (z.B. Abschnitt 8.4.2 S. ). Des weiteren wurde dem oben angesprochenen Paradigma hoher Interaktivität folgend eine Beratungsfunktion zur Ergänzung der interaktiven Veränderungsmöglichkeiten geschaffen, die den Benutzer je nach Situation mehrere Schritte vor dem Auftreten einer Kollision auf diese hinweisen kann (Abschnitt 8.3 S. ).

Die Arbeit endet mit einer Evaluation der durchgeführten Testläufe in Kapitel 9 und mit einem kurzen Ausblick in Kapitel 10.

Insgesamt stellt sich das ganze also wie folgt dar: