Skip to content. | Skip to navigation

Personal tools

Sections

Der Normalfall

next up previous contents
Next: Zusammenfassung Up: Komplexität des Problems Previous: Die Komplexität von Teilproblemen

Der Normalfall

  All diese Überlegungen zeigen, daß es nach dem derzeitigen Stand der Dinge aus informatischer Sicht eigentlich nahezu unmöglich sein müßte, einen geeigneten Stundenplan zu erzeugen. Dennoch kann jede Schule einen solchen vorweisen. Dies legt nahe, daß es in der Realität irgendwelche noch nicht erfaßte Randbedingungen gibt, die das Problem wesentlich vereinfachen. Untersuchungen dieser Art gibt es z.B. für das Vehicle Routing Problemgif. Dort konnte gezeigt werden, daß die Eckpunkte des zugehörigen Polyeders der möglichen Lösungen überdurchschnittlich häufig ganzzahlig sind [RF88]. Bei der automatische Stundenplanerstellung ist auffällig, daß die Aufgabenstellung zumeist aus der nach [CK95b] ebenfalls nur mit exponentiellem Aufwand zu bestimmenden Lehrerverteilung hervorgeht, wenn auch, wie auch von diesen Autoren betont, deren Integration in das Gesamtproblem eleganter wäre.
Hinzu kommt, daß in der schulischen Praxis ein Stundenplan kein isoliertes Problem, sondern eine Problemabfolge ist: Es ist relativ einfach, zu einem gegebenen Stundenplan für die Klassen Lehrer so (neu) einzustellen, daß der Plan erfüllt werden kann: Es genügt bei ähnlichen Curricula, z.B. alle Klassen die Fächer in derselben Reihenfolge durchnehmen zu lassen, diese aber jeweils um 1 gegeneinander zu verschieben. D.h. sozusagen, der erste Stundenplan, den eine Schule benötigt, ist einfach zu erstellen. Beim Übergang von einem Jahr zum nächsten ändern sich strukturell meist nur wenige Dinge, da die Jahrgangsgrößen in Klassenzahlen selten um mehr als tex2html_wrap_inline5542 schwanken und nur ein Jahrgang ausgewechselt wird. Zudem bleiben die Curricula zumeist gleich.

tex2html_wrap5544

Die Frage hier wäre also, ob die Lösbarkeit des letztjährigen Stundenplanproblems hinreichend ist für die Existenz eines neuen Stundenplans. Beim Hinzunehmen der Gymnasialen Oberstufe verschwindet dieser Effekt allerdings teilweise, da hier die individuellen Wahlen der Schüler den Plan in starkem Maße verändern können.
Auch scheint es so, daß die Prüfungsverteilung (vgl. Kapitel 2.6), bei der solche Regelmäßigkeiten noch seltener auftreten, in der Praxis schwieriger ist.


next up previous contents
Next: Zusammenfassung Up: Komplexität des Problems Previous: Die Komplexität von Teilproblemen

(c) Martin Loehnertz 1999