Anatomie des Stundenplan-Motors: wie ein Plan wirklich entsteht
Wer Stundenplansoftware kauft, kauft eigentlich den Motor. Wir nehmen unseren Schicht für Schicht auseinander — von den Schuldaten bis zum beweisbar guten Plan.
Wer Stundenplansoftware auswählt, entscheidet sich eigentlich nicht für eine Oberfläche. Die Bildschirme ähneln sich, die Bedienung lernt man an einem Nachmittag. Wie viel von Ihrem August Sie zurückbekommen, entscheidet der Motor hinter der Schaltfläche „Generieren“ — und in fast jedem Produkt ist dieser Motor eine geschlossene Kiste.
Dieser Beitrag öffnet unsere. Der Bildena-Motor besteht aus fünf Schichten. Wir gehen der Reihe nach durch, was jede tut, wozu es sie gibt und woran wir merken würden, dass sie unbemerkt falsch arbeitet.
1. Schuldaten werden verlustfrei in ein Modell übersetzt
Der Motor arbeitet nicht mit Unterrichtskarten, sondern mit Entscheidungsvariablen. Jede Karte wird nach ihrer Wochenstundenzahl in Blöcke zerlegt, und jeder Block erhält einen Tag, aufeinanderfolgende Stunden und, wo nötig, einen Raum. Die ganze Woche einer Schule ist eine widerspruchsfreie Kombination dieser Entscheidungen.
Für diese Übersetzung gilt genau eine Regel, und sie ist streng: Sie muss verlustfrei sein. Der Motor sagt nie: „Diese Bedingung habe ich nicht verstanden, ich überspringe sie.“ Kopplungen, Gruppenteilungen, Wahlpflichtbänder, A/B-Wochen, Schichtbetrieb — alles steht im selben Variablenraum und wird in derselben Mathematik ausgedrückt. Jedes Feld, nach dem die Oberfläche fragt, hat eine Entsprechung im Modell; ein Feld ohne Entsprechung wird gar nicht erst abgefragt.
Diese Zusage wiegt schwerer, als sie klingt. Eine Bedingung in der Oberfläche anzubieten, ohne sie ans Modell zu binden, ist Etikettenschwindel: Sie setzen den Haken, der Plan entsteht, die Regel wurde nie angewendet — und im September merkt es eine Lehrkraft.
2. Unmöglichkeit wird erkannt, bevor gerechnet wird
Der teure Weg, herauszufinden, dass ein Plan nicht aufgeht, heißt: ausprobieren. Klassische Prüfungen betrachten jede Dimension für sich — hat die Klasse genug offene Stunden, hat die Lehrkraft genug freie? Beide Prüfungen können mit Spielraum bestanden werden, und der Plan bleibt trotzdem unmöglich. Denn eine Stunde kann nur dort liegen, wo die Klasse offen und die Lehrkraft frei ist; sind beide Mengen groß, ihre Schnittmenge aber klein, bemerken reine Zähltests nichts.
Bildena baut stattdessen für jede Klasse und jede Lehrkraft eine bipartite Zuordnung zwischen Unterrichtsstunden und zulässigen Zeitfenstern. Eine Klasse hat zu jeder Zeit nur einen Unterricht, eine Lehrkraft ist nur an einem Ort; jede Stunde braucht also ihr eigenes Zeitfenster. Gibt es keine vollständige Zuordnung, ist der Plan sicher unmöglich — keine Schätzung, sondern eine Folge der Hall-Bedingung.
Eine Regel dieser Schicht steht nicht zur Verhandlung: sie liefert keine falschen Alarme. Die Kandidatenmengen werden bewusst großzügig gehalten. Meldet die Vorprüfung „machbar“, heißt das nur, dass dieser Test bestanden ist; meldet sie „unmöglich“, dann ist es unmöglich. Eine Stundenplanerin einem Engpass hinterherjagen zu lassen, den es gar nicht gibt, kostet mehr als eine späte Warnung.
3. Harte Bedingungen und Wünsche landen nie in derselben Schublade
Im Kern arbeitet ein Constraint-Solver auf Basis von Googles Optimierungstechnologie, von uns für die Schulplanung angepasst. Genau in dieser Anpassung liegt die Arbeit: über das Ergebnis entscheidet nicht der Kern selbst, sondern wie genau ihm eine Schule beschrieben wurde.
Im Zentrum dieser Beschreibung steht eine einzige Unterscheidung. Manches darf nicht verletzt werden, anderes ist bloß erwünscht, und beides landet nie in derselben Schublade.
| Hart — nie verletzt | Weich — wird gegeneinander gewichtet |
|---|---|
| Kollisionen bei Lehrkraft, Klasse, Gruppe, Raum | Verteilung eines Fachs über die Woche |
| Schülerkollisionen (bei schülerbezogener Planung) | Springstunden der Lehrkräfte |
| Sperrzeiten und geschlossene Tage | Gleichmäßige Tagesbelastung |
| Trennung von A- und B-Woche | Weiche Reihenfolgewünsche |
| Tages- und Wochenlimits der Lehrkraft | Nutzung markierter Stunden |
| Harte Reihenfolgeregeln, Vorbereitungsgrenzen |
4. „Nichts Besseres“ ist eine Schranke, kein Gefühl
Während der Suche führt der Solver zwei Zahlen mit: die Kosten des besten Plans, den er hat, und die theoretische untere Schranke, unter die keine Anordnung kommen kann. Im Verlauf sinkt die eine, die andere steigt. Treffen sie sich, ist die Arbeit fertig — und das Ergebnis ist nicht nur gut, seine Optimalität ist bewiesen.
Treffen sie sich nicht, erfahren Sie den verbleibenden Abstand. „Dieser Plan ist höchstens so weit vom bestmöglichen entfernt“ ist der Satz, mit dem Sie entscheiden, ob Sie den Plan annehmen oder den Motor weiterlaufen lassen. Eine Heuristik kann diesen Satz nicht liefern: Wer das Ideal nicht kennt, kann den Abstand dazu nicht messen. Sie weiß am Ende nur, dass sie aufgehört hat.
Diesen Unterschied haben wir in einem eigenen Beitrag behandelt: was es heißt, dass ein Stundenplan beweisbar optimal ist.
5. Das Ergebnis hat eine Kennzahl — aber nicht die des Solvers
Jeder Lauf bekommt eine Perfektionspunktzahl von höchstens 100. Achtzig Punkte entfallen auf die Platzierung: volle Punktzahl, wenn jede Unterrichtsstunde einen Platz gefunden hat. Die übrigen zwanzig bewerten messbare Qualität — Hohlstunden der Klassen, Springstunden der Lehrkräfte, bedingte Situationen und verletzte Planungsregeln.
Diese Wahl ist bewusst: die Strafsumme des Solvers wird nicht als Punktzahl verwendet. Sie ist eine einzige Summe, zwischen Schulen nicht vergleichbar, und ihre Bedeutung verschiebt sich, sobald Sie ein Gewicht ändern — die 1.240 von letzter Woche und die 980 von dieser Woche messen nicht dasselbe. Die Punktzahl wird deshalb am Plan selbst neu gemessen, und auf dem Server läuft dieselbe Formel wie im Browser: Verschieben Sie eine Stunde im Plan, ändert sich der Wert noch vor dem Speichern.
Wer prüft den Motor?
Der gefährlichste Fehler eines Planungsmotors ist kein Absturz, sondern unbemerkt falsch zu rechnen. Der Plan entsteht, alles steht auf Grün, und eine Bedingung wurde nie angewendet. Diese Fehlerklasse findet man nicht durch Hinsehen — man findet sie mit Tests. Allein auf der Motorseite laufen über 2.800 automatisierte Tests, und drei Gruppen davon zielen genau auf dieses Risiko:
- Bindungstests. Für jede harte Bedingung bauen wir eine Eingabe, die sie absichtlich verletzt, und verlangen vom Motor die Antwort nicht lösbar. Zu bestätigen, dass ein Plan „richtig aussieht“, genügt nicht: nur so zeigt sich, ob eine Regel aus dem Code wirklich im Modell angekommen ist.
- Regression an echten Schulen. Läufe auf importierten Daten realer Schulen mit festem Startwert. Verschlechtert eine Verbesserung am Motor den Plan einer anderen Schule, sieht man es vor dem Release.
- Äquivalenz der Formulierung. Dasselbe Problem wird auf zwei Arten beschrieben und die Ergebnisse werden auf Gleichwertigkeit geprüft — der Beweis, dass ein geändertes Modell seine Bedeutung behalten hat.
Die Aufsichtsplanung nutzt denselben Motor, aber ein eigenes Modell
Auch die Aufsichtsplanung läuft über denselben Kern und bildet sowohl Pausenaufsichten als auch tageweise Aufsichtsdienste ab. Entscheidend ist die architektonische Grenze: Der Aufsichtsplaner liest die Stundenplatzierungen und schreibt sie nie. Ein neu erzeugter Aufsichtsplan verändert Ihren Stundenplan nicht. Diese Regel wird im Code-Review durchgesetzt, nicht dem guten Willen überlassen.
Was wir nicht versprechen
Die Grenzen vorab zu nennen ist billiger, als sie später zu erklären.
- Optimalität gilt für das Ziel, das Sie definiert haben. Gewichten Sie Springstunden mit null, erzeugt der Motor bereitwillig einen Plan voller Springstunden und beweist dessen Optimalität. Die Mathematik hält sich an Ihre Prioritäten — auch an Ihre Fehler.
- Er erfindet keine Ressourcen. Kein Solver schafft einen Raum, den Sie nicht haben, oder eine Stunde, die es nicht gibt. Er kann nur früh und präzise sagen, dass sie fehlen.
- Der Beweis gelingt nicht immer innerhalb des Zeitlimits. Bei sehr großen Schulen oder solchen mit sehr wenig Spielraum kann der Motor mit einem kleinen Restabstand anhalten. Der Unterschied: Er nennt diesen Abstand, statt eine abgebrochene Suche als fertige Antwort auszugeben.
Die Zusage, die wir geben
Am Ende eines Laufs wissen Sie, welcher von drei Fällen eingetreten ist: dieser Plan ist optimal; dieser Plan ist zulässig und höchstens so weit vom Optimum entfernt; oder diese Anforderungen sind nicht alle gleichzeitig erfüllbar, und hier ist die Gruppe, die sich widerspricht.
„Mehr habe ich nicht geschafft“ bekommen Sie nie. Das ist der Unterschied.
Bildena Scheduler ist ein webbasiertes System für die Schulstundenplanung auf Basis von Googles Optimierungstechnologie und eigenen Planungsalgorithmen, in Deutschland entwickelt und gehostet. In der kostenlosen Testphase können Sie einen vollständigen Lauf mit Ihren eigenen Daten starten — importiert aus aSc TimeTables, Untis oder Excel — und das Ergebnis mit Ihrem heutigen Plan vergleichen.