Grundlagen
Wie die automatische Generierung tatsächlich funktioniert
Ohne Marketing. Was die Engine tut, warum das Problem schwierig ist und warum die Qualität Ihrer Bedingungen wichtiger ist als die Raffinesse des Algorithmus.
Das Problem, nüchtern dargestellt
Sie haben eine Menge von Lehrveranstaltungen. Jede benötigt einen Zeitslot, einen Raum und eine lehrende Person. Manche Ressourcen werden gemeinsam genutzt, manche Veranstaltungen dürfen sich nicht überschneiden, und eine lange Liste von Regeln bestimmt, welche Kombinationen zulässig sind. Gesucht ist eine Zuordnung, die keine harte Regel verletzt und möglichst wenige Präferenzen missachtet.
Dies ist ein Constraint-Satisfaction-Problem, und die Stundenplanung an Hochschulen ist ein gut untersuchter schwieriger Fall davon. Die Zahl der möglichen Zuordnungen wächst mit der Zahl der Veranstaltungen explosionsartig: Eine erschöpfende Suche ist nicht bloß langsam, sondern schon für eine bescheidene Fakultät astronomisch undurchführbar.
Deshalb sucht kein praxistaugliches System erschöpfend. Sie verwenden Heuristiken — fundierte Strategien, um zu entscheiden, was als Nächstes zu platzieren ist und was zu tun ist, wenn es nicht weitergeht —, um schnell eine gute Lösung zu finden statt irgendwann eine nachweislich optimale.
Was die Engine tatsächlich tut
- Ordnen. Entscheiden, welche Veranstaltungen zuerst platziert werden. Stark eingeschränkte Veranstaltungen — eine große Kohorte, die ein bestimmtes Labor mit einer einzigen qualifizierten Fachkraft benötigt — werden meist früh platziert, weil eine späte Platzierung bedeutet, alles andere wieder aufzutrennen.
- Platzieren. Eine Veranstaltung einer zulässigen Kombination aus Slot, Raum und lehrender Person zuweisen, die keine harte Bedingung verletzt.
- Zurückverfolgen (Backtracking). Frühere Entscheidungen rückgängig machen, wenn sich zeigt, dass eine Veranstaltung keine zulässige Platzierung mehr hat. Hier entfällt der größte Teil der Laufzeit.
- Bewerten. Beurteilen, wie gut die aktuelle Teillösung die weichen Präferenzen erfüllt, damit die Suche bessere Bereiche des Lösungsraums bevorzugen kann.
- Verbessern. Sobald eine vollständige zulässige Lösung existiert, lokale Änderungen vornehmen, die die Bewertung verbessern, ohne etwas zu verletzen.
Warum Ihre Bedingungen wichtiger sind als der Algorithmus
Das ist der Punkt, den Anbieter am ungernsten aussprechen. Bei einem gut spezifizierten Bedingungssatz liefern die meisten leistungsfähigen Engines vergleichbare Ergebnisse. Bei einem schlecht spezifizierten liefert keine Engine etwas Brauchbares.
Der häufigste Fehler ist nicht algorithmischer Natur. Es ist ein Bedingungssatz, in dem Präferenzen für unverletzlich erklärt wurden, sodass keine zulässige Lösung existiert und die Engine korrekt eine große Zahl nicht platzierbarer Veranstaltungen meldet. Der zweithäufigste sind veraltete oder falsche Eingabedaten — Raumkapazitäten, die seit einer Renovierung niemand geprüft hat, oder vor sechs Wochen erhobene Verfügbarkeiten.
Deshalb lautet die nützliche Frage an einen Anbieter nicht „Welchen Algorithmus verwenden Sie?“, sondern „Wie helfen Sie mir, die Bedingungen und die Verfügbarkeiten richtig zu erfassen?“.
Wie ein gutes System in der Praxis aussieht
Ein brauchbares System generiert so schnell, dass die erneute Generierung Routine ist und keine Aufgabe über Nacht — Wise Timetable generiert auch große Stundenpläne in unter einer Minute neu, sodass Sie experimentieren, statt sich auf einen einzigen Lauf festzulegen.
Es meldet, was es nicht platzieren konnte und warum, statt stillschweigend eine Regel zu brechen, um etwas zu erzeugen, das fertig aussieht. Es respektiert von Ihnen gesperrte Veranstaltungen, sodass automatische und manuelle Arbeit gemischt werden können. Und es erzeugt mehrere Varianten, damit Sie vergleichen können, statt hinzunehmen.
So funktioniert die automatische Generierung in Wise Timetable.
Möchten Sie sehen, wie das funktioniert?
Buchen Sie eine 45-minütige Online-Präsentation, in der wir es anhand des Planungsproblems Ihrer eigenen Hochschule durchgehen.