Einführung

Die automatische Stundenplanerstellung bildet trotz jahrzehntelanger intensiver Bemühungen eines der letzten Gebiete der kombinatorischen Optimierung, in denen die menschliche Expertise unverzichtbar geblieben ist. Die bisher vollzogene formale Modellbildung reicht noch bei weitem nicht an die Aufgabenstellungen der Praxis heran, obwohl die Problemstellung intuitiv klar und einfach ist und zahlreiche wissenschaftliche Arbeiten anzugeben vermögen, wie ein guter Plan prinzipiell aussehen sollte. Und selbst diese noch zu kurz greifenden Untersuchungen zeigen mit wenigen Ausnahmen, daß mit einer einfachen Lösbarkeit des Problems nicht zu rechnen ist.
Verwundern muß aber in diesem Zusammenhang, daß das Problem - wenn auch meist mit sehr hohem Zeitaufwand - von Personen ohne kombinatorische Vorbildung häufig zufriedenstellend und sogar besser gelöst wird, als dies mit den bestehenden wissenschaftlichen Ansätzen möglich ist. Dies mag daran liegen, daß man sich bei formalen Ansätzen stets um ein gewisses Maß an Allgemeinheit bemüht, während die mit der Planung Beauftragten spezifische und damit vereinfachte Lösungen anstreben können. Aber die Regelmäßigkeit mit der dies geschieht, läßt dennoch vermuten, daß es auch unabhängig von konkreten Problemstellungen bessere Verfahren geben müßte.

Man sieht sich also mit dem sehr interessanten Effekt konfrontiert, daß, obwohl der Rechner Widersprüche, Abweichungen etc. wesentlich sicherer, schneller und zuverlässiger erkennen kann als ein menschlicher Stundenplaner, dieser ihm im Auflösen dieser Konflikte immer noch überlegen ist. Vor diesem Hintergrund, der dem Computer vorläufig nur oder zumindest die Rolle des Helfers zubilligt, erscheint es sinnvoll, sich zunächst mit der Lösbarkeit zunehmend umfangreicherer Teilprobleme zu beschäftigen. Hierdurch kann einerseits dem Planer eine immer bessere Unterstützung gegeben werden und andererseits kann jedes weitere gelöste Teilproblem vielleicht dazu beisteuern, der Lösung der eigentlichen Aufgabe näher zu kommen.

Die Menge dieser Teilprobleme erweist sich dabei als so groß und mannigfaltig, daß ihre Betrachtung einem Streifzug durch die meisten Methoden der kombinatorischen Optimierung gleichkommt. Hier zeigt sich rasch, daß der weitaus überwiegende Teil der Probleme mindestens -hart ist. Insoweit scheint die Frage nach der Existenz guter Algorithmen negativ beantwortet und in den letzten Jahrzehnten konnten hier, abgesehen von der Identifizierung außergewöhnlich spezieller Fälle, kaum Fortschritte verzeichnet werden. Diese Beurteilung scheint erlaubt, wird doch im Rahmen des von der GMD betreuten Projekts INTEGA noch heute der Algorithmus von 1978 verwandt, da es, nach Selbstauskunft der GMD im Internet Ende 1998, seither keine Veränderungen gegeben habe. Die Fortschritte, die in letzter Zeit im Bereich der Approximationsalgorithmen erzielt wurden, haben sich bisher in diesem Gebiet noch nicht bemerkbar gemacht.
Parallel entwickelten sich entsprechende Heuristiken, teilweise auch unter Einfluß der Methoden der künstlichen Intelligenz, weiter, wobei es allerdings bis heute keinerlei gesicherte Aussagen zur Leistungsfähigkeit gibt, mit denen sich zeigen ließe, daß sie den älteren Verfahren überlegen sind. Da hier insbesondere die neueren Methoden eher allgemeine Optimierungsheuristiken für beliebige kombinatorische Probleme sind, hat die automatische Stundenplanerstellung mit wenigen Ausnahmen (s. Kapitel 4.3.5) keine eigenen tieferen Resultate vorzuweisen, sondern bedient sich, soweit diese anwendbar sind, der Ergebnisse anderer Theorien. Mit Ausnahme einiger neuerer Anwendungen der Theorie von Markovketten können aber auch hier zumeist nur die grundlegenden Erkenntnisse verwendet werden.
Das Fehlen einer Abgrenzung der Stundenplanproblematik gegenüber allgemeineren Problemstellungen, wie z.B. dem Färben beliebiger Graphen, führte und führt zudem dazu, daß jeder Fortschritt auf diesem Gebiet sofort wichtige Erkenntnisse für die gesamte Optimierungstheorie mit sich bringen würde. Methodisch wäre es daher in diesem Kontext vorzuziehen, zunächst eine Lösung der theoretischen Probleme anzugehen. Die Langwierigkeit dieses Vorgehens hat jedoch in der Wechselwirkung von hohem Praxisdruck und unzureichender theoretischer Grundlagen zahlreiche Rezepte entstehen lassen, die mehr dem gesunden Menschenverstand folgen, als einem theoretisch abgesicherten Prinzip.

Eine andere, aber mindestens ebenso wichtige Dimension des Problemes liegt in der bisher unzureichenden Kommunikation zwischen Mensch und Algorithmus. So kann es vorkommen, daß gemäß gegebener Zielfunktionen tatsächlich optimale Pläne für die praktische Anwendung inakzeptabel sind, weil die Unzulänglichkeiten des Planes hierbei vom Benutzer erst erkannt werden können, wenn ihm dieser fertig präsentiert wird. Häufig ist es so, daß ein zufriedenstellender Plan erst durch mehrfaches Nachbessern der Parameter und durch einen Arbeitseinsatz seitens des Benutzers, der dem Aufwand nahekommt, den er ohne Unterstützung hätte erbringen müssen, erzielt werden kann. Da aber bisher noch keine Möglichkeit gefunden wurde, die Wünsche des Anwenders von vorneherein korrekt zu erfassen, ist man hier auf hochgradig interaktive Systeme angewiesen.
Aus diesem Grunde darf sich die Untersuchung des Problems, sofern man sich nicht auf einen vollständig theoretischen Standpunkt zurückziehen will, nicht auf die Untersuchung eines einzelnen isolierten Verfahrens mit statischen Parametern beschränken. Erst eine Einbindung in ein vollständiges System und der Vergleich mit anderen Vorgehensweisen im Rahmen dieses größeren Zusammenhangs vermag die Vor- und Nachteile einer konkreten Methode sichtbar werden zu lassen. Dies bringt es mit sich, daß derartige Unterfangen eine Mindestgröße aufweisen, die deutlich über der üblicher prototypischer Implementierungen liegen. Programme zur Unterstützung der manuellen Planung mit der Möglichkeit zum Datenexport wie MIMOSA
citeMimosa können hier keine Abhilfe schaffen, es sei denn, man entschiede sich, den Paradigmen, die den zur Verfügung gestellten Daten inhärent sind, vollständig zu folgen.

Haben auch die meisten Menschen ihre früheren (Schul-) Stundenpläne als eine profane Regelung in Erinnerung, die angab, ob gerade Geschichte oder Biologie zu lernen sei, so verbarg und verbirgt sich dahinter doch die Arbeit von Wochen oder aber die von Tagen und eines rechnerbasierten Hilfsmittels. Insbesondere der schulische Stundenplan, dessen Struktur einerseits zahlreichen ministerialen und arbeitsrechtlichen Regelungen unterworfen ist, andererseits aber auch pädagogische Absichten unterstützen und für das Lehrpersonal erträglich sein soll, erweist sich als eine der großen Herausforderungen auf diesem Gebiet. Nahezu alle Nebenbedingungen, die bei anderen Planungsaufgaben auftreten, finden sich im Bereich der Bildungsanstalten wieder. Daher bietet sich dieses, fast prototypisch zu nennende Problem für eine Untersuchung besonders an.