Was es bedeutet, wenn ein Stundenplan beweisbar optimal ist
Die meisten Stundenplanprogramme hören auf, wenn ihnen die Ideen ausgehen. Ein Solver, der Optimalität beweisen kann, hört auf, wenn es nichts Besseres mehr zu finden gibt — und er weiß, welcher der beiden Fälle vorliegt.
Jedes Stundenplanprogramm liefert Ihnen am Ende einen Stundenplan. Doch die Frage, die darüber entscheidet, wie viel von Ihrem August draufgeht, stellt niemand: Was meint das Programm eigentlich, wenn es „fertig“ meldet?
Es gibt nur zwei ehrliche Antworten. Entweder hat die Software gesucht, bis ihr Zeit, Versuche oder Geduld ausgingen, und Ihnen die beste Anordnung geliefert, auf die sie zufällig gestoßen ist. Oder sie hat gesucht, bis sie beweisen konnte, dass es keine bessere Anordnung gibt. Das klingt nach zwei Spielarten derselben Sache. Das ist es aber nicht. Dahinter steckt grundverschiedene Mathematik — und entsprechend unterschiedlich verlaufen Ihre Wochen.
Der Kompromiss der Heuristik
Klassische Stundenplanprogramme rechnen heuristisch. Sie setzen Stunden nach Faustregeln, stoßen auf Konflikte, nehmen Schritte zurück, probieren eine andere Reihenfolge — und immer so weiter. Das ist bewusst eine maschinelle Fassung dessen, was ein Mensch mit Karten auf dem Tisch tut — und die Hersteller beschreiben es genau so. Das Handbuch von aSc TimeTables sagt, das Programm nutze „dynamische und heuristische Algorithmen, die es ihm erlauben, dem gleichen Vorgehen zu folgen wie ein Mensch“. Untis beschreibt ein zweistufiges Verfahren aus Setzoptimierung und anschließender Tauschoptimierung, gesteuert über Gewichtungsregler, die der Stundenplaner selbst einstellt.
Dieser Ansatz hat einen echten Vorzug: Er ist schnell, und für eine Schule mit lockeren Randbedingungen erzeugt er einen völlig brauchbaren Plan. Millionen Stundenpläne sind so entstanden.
Dieser Kompromiss hat allerdings eine Kehrseite, über die selten gesprochen wird. Eine Heuristik kann Ihnen nicht sagen, wo Sie stehen. Wenn sie fertig ist, weiß sie nur eines: dass sie aufgehört hat. Sie weiß nicht, ob der Plan hervorragend, mittelmäßig oder nur zwei Tauschschritte von einem deutlich besseren entfernt ist. Es gibt kein Maß für den Abstand zum Ideal, weil das Ideal in ihr gar nicht abgebildet ist.
Die Dokumentation räumt das offen ein. aSc warnt, dass bei einem Fehlschlag „einige wenige nicht verplante Karten übrig bleiben“, und dass ein Neustart „nur zwei oder drei Versuche wert ist, danach ist es besser, die Kriterien zu ändern“. Zu den Generierungsparametern gehört eine Option, mit der Bedingungen automatisch gelockert werden — das Programm setzt also stillschweigend Bedingungen außer Kraft, die Sie festgelegt haben, um die restlichen Karten unterzubringen. Bei Untis liefert erst die Übernacht-Optimierung die besten Ergebnisse: Der Rechner läuft die ganze Nacht durch.
Was ein Solver stattdessen tut
Bildena setzt auf einen Constraint-Solver, den wir ganz auf eine einzige Aufgabe zugeschnitten haben: Unterricht über eine Schulwoche zu verteilen. Er ahmt keinen Menschen nach, der Karten verschiebt. Er übersetzt Ihre Schule in ein mathematisches Modell — jede Stunde eine Variable, jede Regel eine Bedingung — und durchsucht dieses Modell systematisch.
Entscheidend ist nicht, dass er schneller ist. Entscheidend ist, dass er zwei Zahlen gleichzeitig führt: die beste bisher gefundene Lösung und eine Schranke für die bestmögliche Lösung überhaupt. Im Verlauf der Suche verbessert sich die Lösung und die Schranke wird enger. Treffen sie sich, ist die Suche beendet — nicht weil die Zeit abgelaufen ist, sondern weil es beweisbar nichts Besseres gibt. Das ist Optimalität, und das ist eine mathematische Aussage, keine Marketingaussage.
Drei Dinge, die dadurch möglich werden
1. Ein Plan, der belegt ist — nicht bloß erhofft. Wenn Bildena null Konflikte meldet, heißt das nicht „es sind keine Konflikte aufgefallen“. Es heißt: „Es gibt Anordnungen dieser Stunden, die keine Ihrer harten Regeln verletzen — und dies ist eine davon.“ Verstöße gegen harte Bedingungen — eine Lehrkraft in zwei Räumen, eine Klasse an zwei Orten, ein doppelt belegter Raum — sind im Modell von vornherein ausgeschlossen, statt erst nachträglich bestraft zu werden.
2. Unlösbarkeit als Antwort, nicht als Fehlschlag. Manchmal ist die ehrliche Antwort, dass kein Stundenplan alles erfüllt, was Sie verlangt haben. Sechs Stunden Mathematik in einer Fünf-Tage-Woche mit einer Lehrkraft, die an drei Tagen verfügbar ist, sind kein schweres Problem, sondern ein unlösbares. Eine Heuristik reagiert auf Unmöglichkeit genauso wie auf Schwierigkeit — sie probiert weiter und lässt am Ende Karten liegen. Ein Solver kann beweisen, dass die Anforderungen sich widersprechen, und das sagen — vor dem Lauf statt danach. Der Bildena-Berater prüft genau das vorab: Kapazität, Verfügbarkeit, Raumtypen, Lehrerdeputat.
3. Ein sinnvoller Stopp-Knopf. Weil es immer eine aktuell beste Lösung und einen bekannten Abstand gibt, können Sie jederzeit unterbrechen und das Gefundene behalten — samt einer ehrlichen Angabe, wie weit es vom Optimum entfernt sein könnte. „98,4 von 100, höchstens 1,8 % von der theoretischen Schranke entfernt“ — diesen Satz bringt keine Heuristik zustande.
Harte Regeln und weiche Wünsche
Ein Stundenplan ist nicht ein Problem, sondern zwei übereinandergelegte. Manches ist absolut: Eine Lehrkraft kann nicht in zwei Räumen sein, eine Chemiestunde mit Versuchen braucht den Fachraum. Anderes sind Präferenzen, die gegeneinander abgewogen werden — Springstunden vermeiden, Fächer über die Woche verteilen, Tagesbelastung ausgleichen, keine Einzelstunde nach der Mittagspause. Jede Schule gewichtet das anders, und keine Software kann Ihnen die Gewichtung abnehmen.
Die Unterscheidung ist wichtig, weil beides unterschiedlich behandelt werden muss. Harte Anforderungen sind Constraints: Der Solver liefert niemals eine Lösung, die eine davon verletzt. Präferenzen fließen als Terme in eine Zielfunktion ein, deren Gewichte Sie selbst festlegen. Dann tut der Solver etwas, das ein Mensch von Hand nicht verlässlich schafft — er findet die Anordnung, die die gewichtete Summe über alle Präferenzen gleichzeitig maximiert, statt eine Beschwerde nach der anderen abzuarbeiten und dabei zwei neue auszulösen.
Warum Sie niemand beim Rechnen zusehen lässt
Auf diesem Markt gibt es eine merkwürdige Lücke. Jeder Anbieter nennt die Generierung das Herzstück seines Produkts, und kein einziger lässt Sie dabei zusehen. aSc wirbt damit, der Generator prüfe „über 5.000.000 Möglichkeiten“, zeigt dabei aber nichts an. Untis meldet Qualitätsprozente im Nachhinein. Nutzer fragen seit Jahren danach; in Rezensionen wird immer wieder bemängelt, dass es während der Generierung keinerlei Fortschrittsanzeige gibt.
Bei uns sehen Sie beim Rechnen live zu. Während Bildena arbeitet, sehen Sie die Zahl der harten Konflikte fallen, den Qualitätswert steigen, die Phase von der Zulässigkeitssuche zur Optimierung wechseln und den Abstand zur theoretischen Schranke schrumpfen — laufend über eine stehende Verbindung übertragen, kein Fortschrittsbalken mit erfundener Prozentzahl.
Das ist zum Teil Transparenz und zum Teil Diagnose. Ein Lauf, der bei 12 verbleibenden Konflikten hängen bleibt, die sich alle um die Verfügbarkeit der Lehrkräfte drehen, sagt Ihnen etwas Konkretes über Ihre Daten. Ein Wartekreisel sagt Ihnen nichts.
Was wir nicht behaupten
Beweisbare Optimalität ist eine Eigenschaft des Modells, kein Zauberstab — und ihre Grenzen sollte man genau benennen.
- Optimal heißt optimal für das Ziel, das Sie definiert haben. Wenn Sie Springstunden mit null gewichten, liefert der Solver bereitwillig einen Plan voller Springstunden und beweist dessen Optimalität. Die Mathematik ist Ihren Prioritäten treu — auch Ihren Irrtümern.
- Müll rein, beweisbarer Müll raus. Ein Solver kann keinen Raum erfinden, den Sie nicht haben, und keine Stunde, die es nicht gibt. Er kann Ihnen nur präzise und früh sagen, dass sie fehlen.
- Optimalität wird nicht immer in der vorgegebenen Zeit erreicht. Bei sehr großen Schulen oder sehr engen Vorgaben kann beim Zeitlimit noch ein kleiner Restabstand bleiben. Der Unterschied ist, dass er Ihnen diesen Abstand nennt, statt eine unvollständige Suche als fertige Antwort auszugeben.
Was wir zusagen
Wenn der Lauf endet, wissen Sie, welcher von drei Fällen eingetreten ist: Dieser Stundenplan ist optimal; dieser Stundenplan ist zulässig und liegt innerhalb eines angegebenen Abstands zum Optimum; oder diese Anforderungen sind nicht alle gleichzeitig erfüllbar, und hier sind diejenigen, die sich gegenseitig ausschließen.
Sie bekommen nie ein „Mehr habe ich nicht geschafft“. Das ist der Unterschied — und nach dreißig Jahren Stundenplansoftware ist es seltsam, dass man das überhaupt noch eigens sagen muss.
Bildena Scheduler ist ein in Deutschland entwickeltes und gehostetes webbasiertes Stundenplansystem; sein Kern ist ein auf die Stundenplanung spezialisierter Constraint-Solver. In der kostenlosen Testphase können Sie eine vollständige Generierung mit Ihren eigenen Daten laufen lassen — Import aus aSc TimeTables, Untis oder Excel — und das Ergebnis mit Ihrem aktuellen Plan vergleichen.