Überschneidungsfreie Stundenpläne

Das Projekt carpe diem!

Ausgangslage

Wegen stark angewachsener Studierendenzahlen ab dem Winter 2013 brauchten vor allem mittlere und große Vorlesungen (noch) größere Räume und damit größtenteils auch neue Zeiten. Durch viele interdisziplinäre Studiengänge und der sich daraus ergebenden Abhängigkeiten kam damit der gesamte Stundenplan, auch die kleineren Veranstaltungen, komplett ins Wanken. Für die über 20 Verantwortlichen, die die Planung für jedes Fachgebiet getrennt bis dahin von Hand gemacht hatten, war schnell klar: Kleinere Korrekturen am bestehenden Plan würden keine Abhilfe schaffen können.

Jede Vorlesung und Übung, jedes Praktikum, Seminar und Tutorium braucht einen geeigneten Raum und eine wöchentliche Zeit. Selbstverständlich können keine zwei Veranstaltungen zur selben Zeit denselben Raum belegen; auch können Dozierende zeitgleich nur eine Veranstaltung abhalten. Vor allem aber dürfen keine zwei Veranstaltungen, die in einem Studiengang im selben Fachsemester als Pflichtveranstaltung vorgesehen sind zur selben Zeit liegen. Und diese letzte Forderung ist extrem schwer zu erfüllen, da sehr viele Veranstaltungen über interdisziplinäre Studiengänge miteinander verwoben sind. Hinzu kommt, dass Dozierende z.B. wegen Gremientätigkeiten oder weil sie externe Lehrbeauftragte sind, in ihren verfügbaren Zeiten sehr eingeschränkt sein können.

Durchführung

Wir haben die automatisierte Veranstaltungs- und Prüfungsplanung In einem Kooperationsprojekt mit der TU Berlin und dem dortigen Spin-Off MathPlan GmbH eingeführt. Das Optimierungsverfahren (s.u.) wurde von MathPlan in eine mittlerweile kommerzielle Software gegossen. Unser Lehrstuhl war gemeinsam mit einem Team aus Stundenplanenden für alles Organisatorische verantwortlich: Kommunikation mit allen Gruppen, Zeitplanung, Dokumentation, Schulungen, individuelle Unterstützung z.B. durch ein Ticketsystem, usw. Wie bei allen OR-Projekten ist eine solide Datenbasis unerlässlich. Diese herzustellen und aufrecht zu erhalten war wegen eines gewachsenen, uneinheitlichen Altsystems eine besondere, personalintensive Herausforderung. Alle Aufgaben, die die Modellierung von Informationen oder die Schnittstelle zwischen den Systemen betreffen, liegen noch immer an unserem Lehrstuhl.

Ergebnisse

Die Einführung einer automatisierten Planung brachte eine Reihe weiterer Vorteile mit sich. Da Stundenpläne “auf Knopfdruck” erstellt werden können, wird die Bewertung verschiedener what-if Szenarien möglich. Wenn Bau- oder Renoviermaßnahmen anstehen, reichen die restlichen Hörsaalkapazitäten? Müssen dann evtl. die Zeiten um Abende oder Samstage ausgeweitet werden? Nach anfänglicher großer Skepsis, ob eine solch komplexe Planung überhaupt automatisiert durchgeführt werden könne (und solle), sind die Rückmeldungen mittlerweile fast durchweg positiv. Nicht zuletzt ermöglichte das Projekt den Dozierenden erstmals, Wunschzeiten und -räume für ihre Lehre anzugeben. Vor carpe diem! hat man die Zeiten und Räume meist von Vorgängerin oder Vorgänger übernehmen müssen, weil Verlegungen großer interdisziplinärer Veranstaltungen kaum möglich waren. Dass die Möglichkeit, Studierende frühzeitig in Planungen mit einzubeziehen auf Anklang stößt, versteht sich von selbst. Außerdem konnten alle von Lehrstühlen “zur Sicherheit” reservierten Räume (“Bunker”) für die Planung freigegeben werden, weil das System in aller Regel die Wünsche der Lehrstühle berücksichtigen kann.

Wissenschaftlicher Hintergrund

Die Stundenplanung ist als das University Course Timetabling Problem in der Literatur gut bekannt. Eine naive Modellierung als ganzzahliges Programm basiert auf Binärvariablen für jedes mögliche Tripel von Kurs, Raum und Zeit. Als Zielfunktion kommt z.B. die Minimierung der auftretenden Pflichtfach-Konflikte in Frage. Für Instanzen der RWTH-Größe ist ein solches Modell nicht in akzeptabler Zeit lösbar. Stattdessen zerlegen wir das Modell in einer Art Benders Dekomposition in eine erste Stufe, in der Veranstaltungen nur Zeiten zugeordnet werden und eine zweite Stufe, die diesen Paaren dann Räume zuweist. Mit Hilfe von Hall’s Heiratssatz findet man für das ganzzahlige Programm auf erster Stufe Ungleichungen, die garantieren, dass jeder Zeit nur eine Menge von Veranstaltungen zugeordnet wird, für die in der zweiten Stufe auch ein Raum gefunden werden kann. Diese exponentiell vielen Ungleichungen lassen sich polynomiell separieren.

Weiterer Forschungsbedarf ergibt sich unmittelbar aus der Praxis. So haben die Dozierenden den großen Wunsch, dass die Stundenpläne über die Jahre - wenn schon nicht identisch, dann doch zumindest - ähnlich bleiben. Diese Stabilität der Planung hat Bezug zur robusten Optimierung und muss weiter untersucht werden.