Ziele der Arbeit und Überblick
Next: Übersicht über das Spektrum Up: Einleitung Previous: Einführung
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:
Next: Übersicht über das Spektrum Up: Einleitung Previous: Einführung (c) Martin Loehnertz 1999