Skip to content. | Skip to navigation

Personal tools

Sections

Ausblick

next up previous contents
Next: Bemerkungen zur betrachteten Problemstellung Up: Theorie und Praxis der Previous: Weitere Anmerkungen

Ausblick

 

Mit der hier vorgelegten Arbeit wurden zwei Ziele verfolgt:

Eine Aufgabe der Arbeit war es, einen umfassenden und bewertenden Überblick über das Gebiet der automatischen Stundenplanerstellung zu geben.
Zweitens sollten im Rahmen der Erstellung eines Programms Erfahrungen sowohl mit neuen Lösungsverfahren, als auch mit den Anforderungen einer möglichen praktischen Einsetzbarkeit gewonnen werden.

Bereits bei den ersten Nachforschungen bezüglich realistischer Problemstellungen zeigte sich, daß mit einer einfachen Erweiterbarkeit der im Praktikumgif entwickelten Verfahren nicht zu rechnen war, da selbst bei Realschulen inzwischen eine große Zahl von Differenzierungsstunden auftritt. Deren Auftreten verschiebt die Problemstellungen nicht nur aus tex2html_wrap_inline5238 heraus, sondern bis hinein in den Bereich der Nichtapproximierbarkeitgif.
Um in diesem Bereich gute Ergebnisse zu erzielen, wäre entweder ein nicht zu erwartender theoretischer Durchbruch oder aber jahrelange Erfahrung im Umgang mit derartigen Problemstellungen und den zugehörigen Parameterwahlen notwendig. Aus diesen Gründen wurde daher der Schwerpunkt des Vorgehens zugunsten interaktiver Möglichkeiten verschoben, da sich die Probleme in diesem Bereich zwar auch als komplex, zumindest aber als handhabbar erwiesen. Dennoch wurde - unter einem zunächst eher experimentellen Aspekt - die Untersuchung möglicher Heuristiken parallel weitergeführt.

Diese Verschiebung kam der Erstellung des Satzprogrammes zugute, die sich ohnehin als wesentlich aufwendiger erwies, als dies ursprünglich erwartet worden war. Zeigte der erste Prototyp noch das Verhalten, daß das Löschen eines einzelnen Datensatzes die Neueingabe sämtlicher Parameter verlangte, so zog die Verhinderung dieses Problems eine große Zahl von Konsistenzproblemen nach sich, deren Behebung wiederum sehr aufwendig war, auch da sich das verwendete Framework hier nicht sonderlich kooperativ zeigte. Zudem führte die Allgemeinheit, in der das Problem angegangen wurde, dazu, daß viele Operationen jeweils auf Mengen von Objekten und Relationen zwischen diesen ausgeführt wurden, was den Aufwand hier noch weiter steigerte. Bei anderen Implementierungen, die ein ähnlich komplexes System anbieten [CK95b], war noch auf eine Kodierung über eine Eingabesprache und Batch-Läufe zurückgegriffen worden.

Dennoch konnte dieses Programm mit einigen Funktionen versehen werden, die bisher im Bereich der automatischen Stundenplanerstellung noch nicht angeboten wurden, insbesondere, was die schnellere Vorgabe komplexer Parametermengen und die Unterstützung während des Editierens angeht. Auch die Möglichkeit, beliebige Tabellenformen verwenden und ausdruckenzu können, wird von anderen Produkten nicht so umfassend geboten. Das Programm hat somit in einigen Bereichen den Status eines Prototyps weit hinter sich gelassen, und da durch eine einheitliche Schnittstelle die Integration neuer Algorithmen sehr einfach gestaltet wurde, bietet es sich somit als Basis für deren Weiterentwicklung an.

Im Bereich der Lösungsverfahren konnte eine auf Tabusuche beruhende Methode entwickelt werden. Obwohl das gewählte Verfahren auch in der Lage ist, Problemstellungen mit differenziertem Unterricht zu behandeln, schließt es durch Hybridisierung mit dem Algorithmus nach K¨ONIG ebenso die Vorteile der für Unterricht ohne Differenzierungsstunden vorhandenen Verfahren mit ein, wobei hier sogar immer ein gültiger Stundenplan garantiert werden kann.

Des weiteren wurden erste Anfänge einer Simulated Negotiation - Heuristik entwickelt, wobei die Tatsache, daß die vorgenommenen Implementierungen noch kein vollständig zufriedenstellendes Verhalten zeigen, nicht über das große Entwicklungspotential dieses Verfahrens hinwegtäuschen sollte. Dies ist auch insofern nicht sinnvoll, da sich durch die geeignete Wahl einzelner Routinen im Rahmen dieses Modells herkömmliche Verfahren wie Simulated Annealing emulieren ließen, deren Funktionsfähigkeit inzwischen allgemein anerkannt ist.

Beide Verfahren sind, wie erwartet, vorläufig nur in Ansätzen für den praktischen Einsatz geeignet. Die Einschätzung der Parameter der verschiedenen Teile der Zielfunktion erweist sich hierbei unabhängig vom gewählten Verfahren als sehr schwierig, insbesondere wenn man intuitiv Formulierungen verwenden würde wie aber nur wenn es nicht anders geht. Dies führt dazu, daß bei Zwischenlösungen, bei denen tatsächlich keine andere Möglichkeit gegeben sein kann, von diesem Angebot rege Gebrauch gemacht wird, was es wiederum erlaubt, bei anderen Kriterien einen besseren Wert zu erzielen, als er in der besten Endlösung erwartet werden kann. Hier mit wechselnden Zielfunktionen zu arbeiten erwies sich als wenig ergiebig, da die ersten zu Beginn noch relativ frei setzbaren Stunden später über die relativen Nebenbedingungen den gesamten Plan determinieren. Dies läßt die Wirkung der geänderten Zielfunktion teilweise verpuffen.

Da diese Probleme bei rein theoretischen Betrachtungen nie sichtbar werden bzw. beim Stand der momentanen formalen Durchdringung auch noch nicht sichtbar werden können, bleibt hier somit nach wie vor das Verfolgen ganzheitlicher - d.h. Theorie und Praxis umfassender - Ansätze die einzige Möglichkeit, den Eigenheiten der automatischen Stundenplanerstellung gerecht zu werden.




next up previous contents
Next: Bemerkungen zur betrachteten Problemstellung Up: Theorie und Praxis der Previous: Weitere Anmerkungen

(c) Martin Loehnertz 1999