Was macht die Schulplanung so schwierig? Ein sanfter Rundgang durch ein unsanftes Problem

Der Stundenplan gehört zu einer Familie von Problemen, die Informatiker formell als sehr schwierig einstufen. Deshalb verdient Ihr stellvertretender Leiter mehr Mitgefühl — und wie moderne Löser es trotzdem knacken

Jeder, der schon einmal einen Stundenplan von Hand erstellt hat, kennt diesen Moment. Das Netz ist zu 90% voll. Wochenlange Arbeit steht vor der Tür. Und die letzten paar Lektionen werden nicht passen — nicht weil du einen Fehler gemacht hast, sondern weil ein Praktikum, das du in der ersten Stunde des ersten Tages vor Wochen gemacht hast, diese Sackgasse still und leise unausweichlich gemacht hat.

Dieser Moment ist kein Pech. Es liegt in der mathematischen Natur des Problems, das sich von selbst ankündigt

Nehmen wir ein bewusst winziges Beispiel: 10 Lehrer, 8 Klassengruppen, 30 einstündige Unterrichtsstunden pro Woche pro Gruppe, 25 Unterrichtsplätze pro Woche.

Selbst in dieser Spielzeugschule besteht die Anzahl der Möglichkeiten, den Unterricht zu arrangieren, aus Zahlen mit Dutzenden von Ziffern. Eine echte Sekundarschule — 50 Lehrer, 25 Gruppen, spezialisierte Räume, Teilzeitverträge, Optionsblöcke — hat einen Suchraum, der die Anzahl der Atome im beobachtbaren Universum deutlich übersteigt

Die Zeitplanung gehört zu der Klasse von Problemen, bei denen die Überprüfung einer Lösung einfach ist (ein fertiges Raster auf Kollisionen zu überprüfen ist schnell), aber eine Lösung zu finden, kann astronomisch teuer sein, da die einzig garantierte Methode darin besteht, im schlimmsten Fall eine unvorstellbare Anzahl von Kombinationen auszuprobieren. Das ist das Gebiet, das Informatiker als NP-schwer bezeichnen, und der Stundenplan der Schulen ist ein Mitglied, das eine Karte trägt

Die praktische Konsequenz: Noch so viel Erfahrung macht den manuellen Ansatz skalierbar. Erfahrung macht einen menschlichen Planer besser darin, offensichtliche Fallen zu vermeiden, aber die Fallen, die weh tun, sind niemals die offensichtlichen

Viele Branchen planen Dinge. Was Schulen besonders macht, ist die Dichte der ineinandergreifenden Zwänge

Alles teilt sich. Ein Schichtplan im Krankenhaus schränkt hauptsächlich einen Ressourcentyp (Personal) ein. Ein Stundenplan schränkt gleichzeitig drei ein — Lehrer, Räume und Schülergruppen — und jede Unterrichtsstunde nimmt jeweils eine Unterrichtseinheit in Anspruch. Wenn Sie eine einzelne Lektion platzieren, werden Optionen in drei Dimensionen gleichzeitig entfernt.

Harte und weiche Beschränkungen existieren nebeneinander. Einige Regeln sind Physik: Ein Lehrer kann nicht in zwei räume gleichzeitig sein. Andere sind Vorlieben: Frau Ortiz würde lieber vormittags unterrichten. Ein guter Stundenplan muss alle der ersten Art und so viele wie möglich der zweiten Art erfüllen — und diese beiden Ziele kämpfen ständig gegeneinander.

Struktur lebt in Struktur. Doppelte Perioden müssen aufeinanderfolgende Zeiträume belegen — und dürfen oft nicht die Mittagspause überschreiten. Für Optionsblöcke müssen vier verschiedene Lektionen, die von vier Lehrern in vier räume unterrichtet werden, gleichzeitig stattfinden, sodass die Schüler die Fächerwahl kombinieren können. Laborsitzungen benötigen bestimmte Räume. Bei Personalversammlungen müssen bestimmte Gruppen von Personen zur gleichen Stunde freigeben sein. Jede dieser Bedingungen ist eine Beschränkung für Gruppen von Platzierungen, was weitaus schwieriger ist als Einschränkungen für einzelne Platzierungen.

Die Daten sind menschlich. Teilzeitverträge, gemeinsame Lehrer, die ihre Woche auf zwei Schulen aufteilen, ein Trainer, der an Spieltagen früh abreist. Echte Schulen sind ein Bündel von Ausnahmen, und ein Stundenplan, der sie ignoriert, ist kein Stundenplan — es ist ein Vorschlag

Moderne Fahrplanungssoftware verwendet keine brutale Gewalt im Universum der Kombinationen und verwendet keine Magie. Es verwendet eine Reihe von Techniken aus den Bereichen Constrainungserfüllung und kombinatorischer Optimierung, die wirklich schön sind, wenn man sie sich einmal vor Augen führt:

Fortpflanzung: Lass dir von jedem Praktikum etwas beibringen. Wenn der löser eine Lektion platziert, propagiert er sofort die Konsequenzen — dieser Lehrer hat jetzt Dienstag-Periode 2 zu tun, dieser Raum ist besetzt, diese Gruppe ist besetzt. Jede Option, die gerade unmöglich geworden ist, wird überall sonst außer Betracht gezogen. Der Suchraum kollabiert mit jedem selbstbewussten Schritt um Größenordnungen

Scheitere schnell, mache einen klugen Rückzieher. Anstatt wie ein Mensch nach Wochen eine Sackgasse zu entdecken, stellt ein löser innerhalb von Millisekunden fest, dass ein Zweig der Suche nicht erfolgreich sein kann — einige zukünftige Lektionen haben bereits keine legalen Zeitfenster mehr — und gibt sie sofort auf. Es kann auch erkennen, welche frühere Entscheidung die Sackgasse verursacht hat, und genau dorthin zurückkehren.

Heuristik: Platziere die schwierigsten Dinge zuerst. Erfahrene menschliche Planer tun dies instinktiv (planen Sie die Optionsblöcke und Teilzeitkräfte früh ein, füllen Sie die einfachen Singles zuletzt aus). Löser tun dies systematisch und ordnen jede unplatzierte Lektion danach ein, wie eingeschränkt sie bei jedem Schritt ist

Reparieren und verbessern. Einen realisierbaren Stundenplan zu finden ist nur die halbe Miete. Die Löser verbessern es dann, indem sie Unterrichtsketten verschieben und austauschen, um die Unterschiede zwischen den Lehrern zu verringern, mehr Präferenzen zu berücksichtigen und die Belastung auszugleichen — ohne dabei eine harte Einschränkung zu durchbrechen. Hier wird „gültig“ zu „gut“.

Das Ergebnis in einem Tool wie Arignote Timetable ist, dass innerhalb von Minuten ein vollständiger, konfliktfreier Stundenplan für eine echte Schule entsteht — wobei jede harte Einschränkung maschinell überprüft und die weichen weit über den Punkt hinaus optimiert wurden, an dem ein Mensch am vierzehnten Tag verständlicherweise aufgegeben hätte.

Hier ist der Teil, der die Leute überrascht: Durch die Automatisierung wird die menschliche Rolle wichtiger, nicht weniger.

Der löser ist nur so gut wie das Modell der Schule, die ihm gegeben wurde. Die Entscheidung, dass Doppelstunden nicht über das Mittagessen verteilt werden sollten, dass der neue Lehrer ein sanftes erstes Semester braucht, dass der Donnerstagnachmittag den Abteilungsbesprechungen heilig ist — das ist die Schulleitung, verschlüsselt. Die Aufgabe der Software besteht darin, sicherzustellen, dass, wenn Sie es einmal gesagt haben, überall und immer wahr ist, auf eine Weise, die kein Mensch, der alleine arbeitet, garantieren kann.

Und wenn der generierte Stundenplan zurückkommt, überarbeitest du ihn wie ein Redakteur, nicht wie eine Schreibkraft: passe hier eine Platzierung an, hefte dort eine Lektion an — wobei jede Bearbeitung live auf Konflikte geprüft wird — und den Rest nach deinen Entscheidungen neu generieren.

Wochenlange mechanische Arbeit werden zu Rechenminuten plus Stunden des Urteilsvermögens. Das Urteil war immer der wertvolle Teil.