OptaPlanner hilft bei verteilten Schulstandorten (Teil 1/5)

Aufgrund von Baumaßnahmen muss der Unterricht an einer Berliner Schule auf zwei Standorte aufgeteilt werden. Die Wechsel zwischen den Standorten führen zu einer zusätzlichen Belastung des Lehrkörpers. Die Software, die für die Erstellung der Stundenpläne eingesetzt wird, kann diese Wechsel leider nicht minimieren. Als wir das hörten, kamen wir schnell auf die Idee, die Java Planning Engine OptaPlanner darauf anzusetzen.

In dieser Blogserie berichten wir davon, welche Schritte notwendig waren, um das Problem mit OptaPlanner angehen zu können und wie wir somit letztendlich eine Verbesserung um 70% erreichen konnten.

Das fachliche Problem

Das Dach des Otto-Nagel-Gymnasiums (ONG) wird zurzeit erneuert. Während der Bauphase können nicht alle Räume der Schule genutzt werden. Bis zur Fertigstellung des Umbaus in 2016 wird daher ein Teil der Schüler in einer ca. 25 min Fahrtzeit entfernten Filiale unterrichtet. Dies führt dazu, dass einzelne Lehrer mehrmals pro Woche, zwischen zwei Schulstunden, den Weg zum anderen Standort zurücklegen müssen. Die Anordnung der Unterrichtsstunden im bisherigen Stundenplan berücksichtigt die umbaubedingten Fahrtzeiten nicht. So kommt es zu unnötigen Gebäudewechseln aber auch zu Verzögerungen im Unterrichtsablauf, da nicht alle Pausen zwischen zwei Unterrichtsstunden ausreichend Zeit für den Gebäudewechsel bieten.

blog-akquinet-optaplanner

Dieses Praxisbeispiel ist ein weit verbreitetes Problem aus der Klasse der Zuordnungsprobleme. Bei der Erstellung von Stundenplänen wird festgelegt, wann und in welchen Räumen die verschiedenen Unterrichtsstunden stattfinden. Unterrichtsstunden haben dabei ein bestimmtes Fach (oder Kurs), werden von einem dafür qualifizierten Lehrer gehalten und von einer Menge von Schülern (Klasse) besucht. Die Kurse sind im Rahmen der Planung den Zeiten im Wochenstundenplan und entsprechend verfügbaren und geeigneten Räumen zuzuordnen. Bei der Zuordnung müssen verschiedene Restriktionen beachtet werden. Dabei existieren zwei Arten von Restriktionen: harte Restriktionen (z.B. „Es dürfen nicht mehrere Kurse eines Lehrers zur gleichen Zeit stattfinden.“) sowie weiche Restriktionen, wie z.B. präferierte Arbeitszeiten der Lehrer. Ein erstellter Stundenplan ist dabei nur gültig, wenn er alle harten Restriktionen erfüllt. Die weichen Restriktionen stellen die Kriterien zur Optimierung dar. Ein Stundenplan, der mehr Arbeitszeitenwünsche der Lehrer als ein anderer berücksichtigt, ist die bessere Lösung.

Das Ziel:  Mit Hilfe von OptaPlanner soll der Stundenplan des ONG so optimiert werden, dass eine möglichst geringe Anzahl von Gebäudewechseln von den Lehrern zu bewältigen ist und diese in Pausen mit ausreichend Zeit stattfinden.

Vorgehensweise

OptaPlanner vereint die Konzepte von (Meta-) Heuristiken sowie die Bewertung (oder Scoreberechnung) mithilfe einer Regelengine. Die Formalisierung der Restriktionen des zu lösenden Problems erfolgt dabei in Form von logischen Regeln. (Meta-) Heuristiken sind Suchverfahren, die sich zur Lösung verschiedener allgemeiner Probleme anwenden lassen. Sie finden Anwendung, wenn für das Problem kein spezialisierter Lösungsalgorithmus existiert oder dieser, z.B. aufgrund der Problemgröße, keine Lösung in akzeptabler Zeit findet.
Die folgende Abbildung gibt einen Überblick über die Schritte zum optimierten Stundenplan:

Vorgehensweise mit OptaPlanner

Die folgenden Beiträge dieser Blogserie werden wir in den kommenden Wochen veröffentlichen und darin näher auf die einzelnen Schritte eingehen:

  • Teil 2 beschreibt die Erstellung des Datenmodells
  • Teil 3 zeigt den zweiten Teil der Modellierung unseres Problems, die Formulierung der Restriktionen in Form von Drools Regeln
  • Teil 4 erläutert welche Verfahren zur Optimierung eingesetzt werden und wie diese in OptaPlanners Solver konfiguriert werden.
  • Teil 5 zeigt den Optimierungsvorgang in Aktion und präsentiert das damit erreichte Ergebnis.

We’ll be back in a moment.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s