Stundenplanungsprobleme treten in vielen Bereichen in verschiedenen Ausprägungen auf, beispielsweise klassisch in Schulen oder Universitäten, aber auch in Arztpraxen oder in ähnlicher Form bei der Personalplanung in Betrieben. Die Planung regelt dabei die Zuordnung von Objekten zu Ressourcen, wie Räumen, Zeit und Personal unter bestimmten technischen, organisatorischen, persönlichen und anderen kapazitiven Einschränkungen. Algorithmen zur Lösung von Stundenplanungsproblemen erfordern exponentiellen Aufwand.

In dieser Studienarbeit wurde als konkrete Planungsdomäne ein Ausschnitt der Semesterplanung der Fakultät 1 der BTU untersucht, ein Vorgehensmodell erarbeitet und ein Planungssystem mit Hilfe der constraint-basierten Java-Bibliothek Choco implementiert.

Datenerhebung

Erste Aufgabe war die Erhebung und Strukturierung der notwendigen Daten und des  derzeitigen manuellen und technischen Vorgehens bei der Stundenplanung. Die der Planung unterliegenden Bedingungen oder Constraints wurden herausgearbeitet und klassifiziert.

Das Stundenplanungsproblem als CSP

Das Planungsproblem wurde im nächsten Schritt in ein CSP umgewandelt.

Ein CSP (Constraint Satisfaction Problem) ist eine formale Problembeschreibung bestehend aus den am Problem beteiligten Variablen, deren Definitionsbereichen und den Bedingungen oder Constraints. Ziel der Lösung eines CSPs ist die Berechnung von  Belegungen der Variablen, so dass alle aufgestellten Constraints erfüllt werden (s. Vorlesung: Einführung in die Constraint-Programmierung).

Bei der Darstellung der Stundenplanung als CSP werden die Startzeiten der angebotenen Kurse, die zu Verfügung stehenden Räume, die Kapazitäten der Lehrenden usw. als Variblen repräsentiert. An sie sind viele unterschiedliche Bedingungen geknüpft. So muss u.a. beachtet werden, dass sich Kurse der gleichen Veranstaltungen nicht überschneiden, Räume zu einem Zeitpunkt nicht mehrfach belegt und Lehrende nicht mehrfach pro Block verbucht werden können.

Warum wird dieses Problem nicht rein imperativ / objekt-orientiert gelöst?

Für CSPs gibt es spezielle Löser oder Solver. Das sind optimierte Lösungsalgorithmen, die dem Nutzer z.B. durch Bibliotheken, wie Choco für Java, zur Verfügung gestellt werden. Algorithmen für solch komplexe Probleme selbst zu schreiben ist aufwendig und fehleranfällig. CSP-Solver werden hingegen extra für solche Probleme entworfen und lösen diese daher bereits recht effizient. Oft sind sie erweiterbar und auf das Problem des Nutzers speziell anpassbar.

Warum ist das Problem dann dennoch so schwierig?

Die Beschreibung von Optimierungs- und Schedulingproblemen in einer Form, so dass ein Solver sie effektiv lösen kann, ist oft sehr komplex.

Beispielsweise kann es schnell passieren, dass zu starke Bedingungen erzeugt werden und so das Problem letztendlich keine Lösung mehr besitzt. Fordern wir bspw., dass "alle Kurse eines Semesters sich nicht überschneiden", so ist dieses Constraint i.d.R. zu stark. Besser ist hier das Constraint "Pflichtveranstaltungen und / oder Veranstaltungen der gleichen Säule eines Semesters dürfen sich nicht überschneiden".

Darüber hinaus enthalten CSPs oft einen Optimierungsanteil, der meist rechenaufwendiger ist als nur eine Lösung zu bestimmen.

Die Stundenplanung an der Fakultät 1

Bei der manuellen Stundenplanung wird zunächst der Stundenplan des vorvorherigen Semesters als Basis angelegt. Zeiten wiederkehrender Kurse können so meist problemlos übernommen werden. Sehr viel aufwendiger ist es hingegen, neue Veranstaltungen oder solche mit veränderten Daten widerspruchsfrei einzufügen. Der manuelle Prozess der Planung nimmt ca. 2 Monate in Anspruch.

Auch die neue maschinelle Planung nimmt einen vorherigen Plan als Vorlage. Darauf basierend werden für alle Veranstaltungen entsprechende Variablen und Constraints erzeugt, so dass ein initialer widerspruchsfreier Plan mit allen Veranstaltungen erzeugt werden kann.

Der initiale Plan wird zunächst allerdings recht unausgewogen sein, z.B. ordnet er bestimmten Blöcken sehr viele und anderen Blöcken nur wenige Veranstaltungen zu. Daher folgt ein Optimierungsprozess, der blockweise über den Plan iteriert und dabei je Block einige Veranstaltungen fixiert und andere entfernt. Danach berechnet der Solver eine neue Lösung. Auf Grund der Iteration hat die Reihenfolge der Blöcke relativ starken Einfluss auf das Gesamtergebnis der Planung. Daher wird die Blockreihenfolge während der Optimierung variiert.

Implementierung der automatisierten Planung

Das Planungsproblem wurde im Rahmen der Arbeit zunächst nur für den Studiengang Informatik konzipiert und getestet. Dies entspricht einer Problemgröße von ca. 150 Kursen (Vorlesungen, Übungen, Praktika etc.), 30 Räumen und 30 Lehrenden. Die Laufzeit des Programms für die genannte Problemgröße beträgt etwa 3 Sekunden inclusive Laden und Speichern der Informationen.