Stundenplanung (Schulen, Hochschulen, öffentlicher Nahverkehr)

Einen Stundenplan zu erstellen heißt, Unterrichtsstunden, Prüfungen oder Fahrten so auf Zeiten, Räume und Personen zu verteilen, dass harte Regeln nie verletzt und Präferenzen möglichst gut erfüllt werden. Im Kern steht ein kombinatorisches Optimierungsproblem (NP-schwer), das mit Constraint Programming, MIP oder Metaheuristiken gelöst wird, nicht mit einem LLM. KI schafft Nutzen rund um den Solver: Regeln aus Fließtext in Constraints übersetzen, Konflikte erklären, Korrekturen vorschlagen und die Nachfrage prognostizieren.

Problem & Nutzen

• Heute: Viele Schulen planen noch von Hand in Tabellen oder mit Desktop-Werkzeugen über Tage oder Wochen; Hochschulen verbinden zentrale Planung mit Abstimmung in den Fachbereichen; Verkehrsbetriebe planen Angebotsmuster, Fahrzeugumläufe und Dienste in spezialisierten Planungssuiten.
• Nutzen durch KI/Solver: zulässige Pläne in Minuten statt Tagen, explizite Abwägung weicher Regeln (Lücken bei Lehrkräften, Wege der Studierenden, Raumauslastung), schnelle Neuplanung, wenn eine Lehrkraft oder ein Raum ausfällt, und eine transparente Bewertung, die Entscheidungen leichter vertretbar macht.
• Nutzenzahlen: Veröffentlichte Herstellerangaben streuen stark und sind selten unabhängig überprüft; messen Sie Ihre eigene Ausgangslage (Planungsstunden, Verletzungen harter Regeln, Raumauslastung). Hier wird keine allgemeine Zahl genannt.

Varianten

• Schulstundenplanung (Sek. I/II, berufsbildend): Klassen, Lehrkräfte, Räume, Doppelstunden, Teilzeitkräfte, Fachblöcke; stark durch Landesvorschriften geregelt.
• Veranstaltungsplanung an Hochschulen: Zuordnung der Studierenden zu Gruppen, große Räume, mehrwöchige Muster, Studienplan-Konflikte (die Problemklasse des International Timetabling Competition ITC 2019) [3].
• Klausurplanung: keine Studierenden mit zwei Prüfungen gleichzeitig, Prüfungen zeitlich streuen, Regeln zu Kapazität und Aufsicht.
• Öffentlicher Nahverkehr: Linien- und Taktplanung, Fahrpläne, Fahrzeugeinsatzplanung (Umläufe), Dienst- und Dienstplanung; Echtzeit-Wiederherstellung wird in OPT-020 behandelt, die Personaleinsatzplanung in OPT-003.
• Private Nutzung: Familien- oder Vereinspläne, z. B. Planung über gemeinsame Kalender (AGENT-012).

So funktioniert es

master data (teachers, rooms, classes, demand, network)
  -> constraint modelling (hard rules vs weighted soft rules)
  -> solver (CP-SAT / MIP / local search) generates candidates
  -> score + explanation (which constraints are violated, by whom)
  -> human review, manual pinning of lessons/trips, re-solve
  -> publish (SIS/LMS, parent portal, GTFS feed, driver apps)

• Solver-Kern: Constraint Programming (z. B. CP-SAT) für enge Zulässigkeitsprobleme, MIP für Zuordnung und Dienstbildung mit Spaltengenerierung, Metaheuristiken (lokale Suche, Simulated Annealing, Late Acceptance) für große Instanzen mit vielen weichen Regeln.
• ML rund um den Solver: Nachfrage- und Fahrgastprognosen bestimmen das Angebot im Nahverkehr; historische Daten sagen Kursbelegungen und Raum-No-Shows voraus (PRED-Familie, tabular-ml/Zeitreihen).
• LLM-Schicht: Ein LLM übersetzt „Frau X unterrichtet nur Mo-Mi, höchstens zwei Freistunden pro Tag“ in strukturierte Constraints oder Solver-Code, fasst Unlösbarkeit zusammen und beantwortet Was-wäre-wenn-Fragen (siehe OPT-018). Das LLM erzeugt den Plan nie selbst; der Solver validiert jede Ausgabe.
• Mensch-in-der-Schleife (Human-in-the-Loop): Die Planerin bzw. der Planer fixiert („pinnt“) Zuordnungen, genehmigt die Gewichte der weichen Regeln und gibt den veröffentlichten Plan frei; Beschäftigte und Betriebsrat sehen die verwendeten Regeln.

Datenaufbereitung

Benötigte Daten: Kurse, Lehrkräfte, Räume, Kapazitäten, Ausstattung, Belegungen und, für den Nahverkehr, das GTFS/NeTEx-Netz, Nachfrage und Fahrerregeln. Sie liegen typischerweise im Schulverwaltungssystem, im Campus-Management- oder ERP-System, in Excel-Tabellen der stellvertretenden Schulleitung bzw. der Planenden und in den Köpfen erfahrener Planer. Typische Lücken: Regeln, die nur als ungeschriebene Gesetze existieren („Frau X unterrichtet nie freitagnachmittags“), uneinheitliche Raum- und Ausstattungsbezeichnungen, doppelte Lehrkraft-Datensätze, veraltete Belegungsdaten und Verfügbarkeiten der Lehrkräfte, die per E-Mail oder auf Papier erfasst werden.

Schritte der Aufbereitung: 1. Quellen inventarisieren und pro Quelle eine verantwortliche Person benennen (PREP-004). 2. Alle harten und weichen Regeln in einer strukturierten Liste festhalten; das ist der wertvollste Schritt. 3. Stammdaten (Räume, Lehrkräfte, Kurse) in saubere Tabellen überführen (PREP-011). 4. Aus Altsystemen per Datei oder API exportieren (PREP-005). 5. Den Stundenplan des Vorjahres als Regressionstest für den Solver aufbewahren.

Werkzeuge: Excel/CSV, Python mit pandas, die Importformate des Solvers. Grober Anteil am Aufwand: 15-25 Prozent, überwiegend für die Erfassung der Regeln statt für technische Bereinigung.

Umsetzungswege

Welcher Weg für wen

• Öffentlicher Sektor (Schulen, Hochschulen, kommunaler Verkehr): A, weil zertifizierte Stundenplan-Produkte (z. B. Untis, Elementary, Planungsmodule von Verkehrssoftware) ausgereift und beschaffbar sind und bereits Formate von Schulverwaltungssystemen und GTFS sprechen.
• Großunternehmen (Verkehrsunternehmen, große Hochschulen): B, weil die Dienst- und Fahrzeugeinsatzplanung zum Kerngeschäft gehört, eine tiefe Integration in eigene Daten braucht und am besten auf einem OR-Solver mit LLM-Oberfläche aufgebaut wird.
• Entwickler: C, weil OR-Tools, Timefold oder OptaPlanner vollständig als Open Source auf HW1 laufen und der Solver unter Ihrer Kontrolle bleibt.
• KMU (Privatschulen, Bildungsanbieter): A, weil die Standard-Stundenplanung eine gelöste Produktkategorie zu KMU-Preisen ist.

Weg A — Kaufen (Standardsoftware)

• Schulen (DACH/EU): Untis (Untis Group, Österreich; EU), Stundenplan-Werkzeuge wie TimeTabler und aSc Timetables (aSc, Slowakei; EU), Lantiv Timetabler, Edval (Australien, weit verbreitet).
• Hochschulen: UniTime (Open Source, Apache-lizenziert, plus kommerzielles Hosting) [4], Scientia, CELCAT (UK/Frankreich), Infosilem, Ad Astra; Campus-Systeme wie HISinOne, CAMPUSonline.
• Öffentlicher Nahverkehr: Hacon/Siemens Mobility HaCon (DE; EU), PTV Group (DE; EU), GIRO HASTUS (CA), Optibus (IL), IVU Traffic Technologies (DE; EU) für Planung, Fahrzeug- und Dienstplanung.
• Prüfen: EU-Hosting, Import/Export von Schul- oder HR-Stammdaten, Transparenz des Solvers, Unterstützung landesspezifischer Regeln, Preis pro Schülerin bzw. Schüler/Studierenden.

Weg B — Auf Cloud-KI-Diensten aufbauen

• Solver als Dienst / Bibliothek: Timefold Solver (Java/Python; EU, Belgien) bietet einen Schulstundenplan-Quickstart und eine Timefold Platform für Mitarbeiter-, Außendienst- und Schichtplanung [1]; Google OR-Tools CP-SAT mit dokumentierten Stundenplan-Beispielen [2]; kommerzielle Solver Gurobi, CPLEX, FICO Xpress oder HiGHS (offen).
• LLM-Schicht: ein Frontier-Modell mit strukturierten Ausgaben (Claude, Gemini, GPT, Mistral in EU-Regionen), um Regeln aus Textdokumenten zu extrahieren und Erklärungen zu erzeugen; die Codegenerierung für Modelldefinitionen folgt dem Muster von OPT-018.
• Integration: REST-Dienst vor dem Solver, nächtlicher Import aus dem Schul- oder HR-System, GTFS/NeTEx-Export für den Nahverkehr.

Weg C — Selbst betreiben (Open Source)

• Werkzeuge: FET (freie Stundenplan-Software für Schulen) [5], UniTime [4], Timefold Solver Community, OR-Tools, HiGHS, OptaPlanner-Linie, jMetal/pymoo für eigene Metaheuristiken.
• LLM-Schicht (optional): ein Open-Weight-Modell der Klasse Qwen oder Mistral auf einer GPU über vLLM/Ollama.
• Hardware: Solver laufen auf der CPU (HW1); ein Server mit 16-32 Kernen genügt für die meisten Schulen und Hochschulen; ein LLM-Helfer ist optional auf HW2.

Weg D — Eigenes Training

Für den Kern selten nötig. Eigenes ML lohnt sich für Nachfrageprognosen, für das Lernen von Solver-Parametern und Heuristiken (Reinforcement Learning oder gelernte Nachbarschaften sind aktive Forschung) oder für das Feintuning eines kleinen LLM auf eine fachspezifische Constraint-Sprache. Erfordert historische Stundenpläne und Belegungen.

Stand der Technik (2026)

• Exakte und hybride Solver dominieren: CP-SAT sowie MIP/CP-Hybride mit Large-Neighbourhood-Search gewinnen die meisten Benchmark-Klassen; die ITC-2019-Instanzen mit realen Hochschuldaten bleiben der Standard-Benchmark [3].
• Constraint Streams und deklarative Modelle (Timefold, OR-Tools) erlauben es Planenden, Regeln nah an der Fachsprache auszudrücken, und machen Erklärungen der Bewertung möglich.
• LLM-gestützte Modellierung: Forschung und Produkte übersetzen Anforderungen in natürlicher Sprache in Solver-Modelle und erklären Unlösbarkeit; die Genauigkeit bei komplexen Modellen ist begrenzt, und jede erzeugte Regel muss an bekannten Fällen getestet werden.
• Lerngestützte Suche: RL und Graph-Neuronale-Netze schlagen Zuordnungen oder Heuristiken vor; sie helfen bei großen Instanzen, schlagen aber bei harten Zulässigkeitsproblemen selten gut abgestimmte Solver.
• Grenzen: schlechte oder fehlende Stammdaten, widersprüchliche Regeln zwischen Beteiligten und politische Abwägungen sind die üblichen Hindernisse, nicht die Rechenleistung. Übermäßig optimierte Pläne sind anfällig für Störungen; planen Sie Puffer ein und halten Sie einen Reparaturmodus bereit.

Gemeinsame Bausteine & Kombinationen

• Gemeinsamer Baustein: der Optimierungs-Solver-Stack (CP-SAT, MIP, lokale Suche), den OPT-002 (Produktion), OPT-003 (Personal), OPT-019 (Außendienst) und OPT-027 (Projekte) wiederverwenden.
• Naheliegende Kombinationen: OPT-018 (LLM-zu-Solver-Copilot), OPT-020 (Störungsbewältigung auf denselben Daten), OPT-028 (bedarfsgesteuerter Verkehr), OPT-025 (Verkehrssignale), AGENT-012 (Kalender-Agenten).
• Datenpipelines: Der Stammdatenabgleich mit SIS/HR und GTFS/NeTEx wird mit Anwendungsfällen aus Mobilität und öffentlichem Sektor geteilt.

Aufwand, Kosten & Kennzahlen

• Weg A: Wochen bis wenige Monate inklusive Datenbereinigung; Lizenzen pro Schule/Schüler bzw. Schülerin oder pro Fahrzeug.
• Weg B/C: 2-6 Monate bis zum ersten produktiven Modell; der meiste Aufwand liegt in der Modellierung der Regeln und der Abstimmung der Beteiligten, nicht in der Rechenleistung. Open-Source-Werkzeuge kosten vor allem Arbeitszeit.
• Kennzahlen: Verletzungen harter Regeln (Ziel 0), gewichteter Wert der weichen Regeln, Lücken bei Lehrkräften und Leerlaufzeiten der Studierenden, Raumauslastung, Planungsvorlaufzeit, Neuplanungszeit nach einer Änderung; im Nahverkehr: Anzahl Fahrzeuge und Fahrer, Leerfahrtenanteil, Pünktlichkeit, Wartezeit der Fahrgäste.

Menschen & Veränderung

Binden Sie früh die Leitung für Umfang und Fairnessgrundsätze ein, die Leitung der Stundenplanung als Prozessverantwortliche und die IT für Integration und Zugänge. Lehrkräfte und Beschäftigte sind die Anwender und vom Ergebnis stark betroffen; beziehen Sie sie vor dem Pilotbetrieb ein, nicht danach. Betriebsrat oder Personalrat: ja. Stunden- und Dienstpläne berühren die Arbeitszeit (§87 Abs. 1 Nr. 2 BetrVG), und das System verarbeitet personenbezogene Beschäftigtendaten, wodurch auch §87 Abs. 1 Nr. 6 relevant ist; unterrichten Sie den Betriebsrat rechtzeitig nach §90 Abs. 1 Nr. 3 und ziehen Sie eine Sachverständige bzw. einen Sachverständigen nach §80 Abs. 3 in Betracht. In öffentlichen Schulen gilt der Personalrat bzw. die Lehrervertretung nach Landesrecht. Datenschutz: Daten von Beschäftigten und Lernenden sind personenbezogen; beziehen Sie daher die Datenschutzbeauftragte bzw. den Datenschutzbeauftragten ein und schließen Sie mit jedem Auftragsverarbeiter einen Auftragsverarbeitungsvertrag (AVV, Art. 28 DSGVO) ab; eine Datenschutz-Folgenabschätzung (DSFA, Art. 35 DSGVO) ist nur nötig, wenn eine systematische Bewertung von Personen hinzukommt.

KI-Kompetenz: Der Solver ist kein LLM; schulen Sie daher die Planenden darin, was die LLM-Oberfläche kann und was nicht, als Maßnahme zur KI-Kompetenz (KI-Verordnung (AI Act) Art. 4). Kommunizieren Sie, dass die Fairnessregeln sichtbar und anpassbar sind. Starten Sie mit einer Abteilung oder einem Teilplan für ein Halbjahr. Typische Sorge: „Die Maschine entscheidet über meinen Stundenplan.“ Begegnen Sie ihr mit transparenten Regeln, einem Verletzungsbericht und damit, dass stets die Planerin bzw. der Planer den endgültigen Plan freigibt.

Siehe GUIDE-004, GUIDE-008 und GUIDE-005.

Risiken, Regulierung & Compliance

• KI-Verordnung (AI Act): in der Regel minimales Risiko; die Planung von Klassenräumen oder Fahrten steht nicht in Anhang III (Bildung: Zulassung, Bewertung von Lernergebnissen, Prüfungsaufsicht) [6]. Sie kann hochriskant werden, wenn das System Aufgaben zuteilt oder Beschäftigte anhand individuellen Verhaltens oder persönlicher Merkmale bewertet (Anhang III Nr. 4, Beschäftigung/Aufgabenzuteilung) oder wenn die Fahrplanung eine Sicherheitskomponente kritischer Infrastruktur ist. Kein Verbot nach Art. 5 ist einschlägig, es sei denn, es würde eine Emotionserkennung in Schule oder Arbeit ergänzt, was nicht geschehen darf. KI-Kompetenz (Art. 4) gilt.
• DSGVO: Daten von Lehrkräften und Lernenden (Präferenzen, Förderbedarf, Teilzeitstatus, Fehlzeiten) sind personenbezogen; gesundheitsbezogene Einschränkungen sind besondere Kategorien von Daten (Art. 9). Nutzen Sie Datenminimierung, pseudonyme IDs im Solver, einen Auftragsverarbeitungsvertrag und EU-Hosting.
• Arbeitsrecht/Mitbestimmung: In Deutschland sind Betriebs- oder Personalräte in der Regel einzubinden (BetrVG/Personalvertretungsrecht); Arbeitszeit- und Lenkzeitregeln (Verordnung (EG) Nr. 561/2006 für Fahrer) sind harte Regeln.
• Fairness und Transparenz: Dokumentieren Sie die Regeln und Gewichte; dokumentieren Sie, wie die Präferenzen der Lehrkräfte gewichtet werden, um eine systematische Benachteiligung von Teilzeitkräften oder Pflegenden zu vermeiden.
• Gegenmaßnahmen: menschliche Freigabe, Validierung durch einen unabhängigen Constraint-Prüfer, versionierte Pläne.

Erste Schritte

1. Sammeln Sie den Regelsatz bei den Beteiligten, ordnen Sie die Regeln als hart oder weich ein und halten Sie sie schriftlich fest.
2. Bereinigen Sie die Stammdaten (Lehrkräfte, Räume, Klassen) und legen Sie den Stundenplan des Vorjahres als Vergleichsmaßstab fest.
3. Führen Sie einen Pilot mit FET, UniTime oder Timefold für eine Abteilung oder einen Jahrgang durch und vergleichen Sie mit der manuellen Planung.
4. Ergänzen Sie einen LLM-Assistenten für Regelaufnahme und Änderungswünsche erst, wenn das Solver-Modell stabil ist.
5. Richten Sie einen Änderungsprozess (Pinnen, erneut lösen, Kommunikation) ein und messen Sie die Kennzahlen jedes Halbjahr.

Quellen

1. Timefold — Solver documentation and school timetabling quickstart — https://docs.timefold.ai
2. Google OR-Tools — CP-SAT scheduling examples — https://developers.google.com/optimization/scheduling
3. International Timetabling Competition 2019 — https://www.itc2019.org
4. UniTime — university timetabling system — https://www.unitime.org
5. FET — Free Timetabling Software — https://lalescu.ro/liviu/fet/
6. Regulation (EU) 2024/1689 (AI Act), Annex III — https://eur-lex.europa.eu/eli/reg/2024/1689/oj
7. HiGHS open-source solver — https://highs.dev
8. GTFS reference — https://gtfs.org/documentation/schedule/reference/