Nachdem Restriktionen, Bewertungsfunktion und Lösungsverfahren implementiert und konfiguriert sind (siehe Teil 4), kann letztendlich die Optimierung des Stundenplans ausgeführt werden. Dieser letzte Beitrag der Blogreihe stellt den Optimierungsvorgang sowie die dabei erzielten Ergebnisse vor.
Weiterlesen
ressourceneffizienz
OptaPlanner hilft bei verteilten Schulstandorten (Teil 4/5)
Die vorigen Teile dieser Serie haben beschrieben, wie das Optimierungsproblem modelliert und das Modell mit Hilfe von OptaPlanner umgesetzt wird. Dieser Teil beschäftigt sich mit dem eigentlichen Lösungsverfahren des Problems.
Ablauf der Optimierung
Der Solver übernimmt die Optimierung des Problems und durchläuft dabei mindestens zwei Phasen. In der ersten Phase wird eine Ausgangslösung erstellt. Diese wird in der oder den darauf folgenden Phase(n) inkrementell optimiert. Für beide Phasen stellt OptaPlanner unterschiedliche Heuristiken zur Verfügung, die je nach Art des Optimierungsproblems auszuwählen sind. OptaPlanner bietet zudem eine Benchmarkingfunktionalität, welche die Evaluation verschiedener Heuristiken durch automatische Läufe und Gegenüberstellung verschiedener Konfigurationen des Solvers mit grafischen Reports zu Performance und Skalierbarkeit unterstützt.
OptaPlanner hilft bei verteilten Schulstandorten (Teil 3/5)
Modellierung des Problems
Eine Zuordnung von verfügbaren Schulstunden zu Unterrichtsstunden ist mit dem Datenmodell aus Teil 2 dieser Serie nun prinzipiell möglich. Für eine sinnvolle Optimierung mit Hilfe von (Meta-) Heuristiken fehlen jedoch die Restriktionen des Zuordnungsproblems sowie eine Möglichkeit zur Bewertung verschiedener Lösungen. Umgesetzt werden können diese innerhalb von Optaplanner mit Hilfe der Regelengine Drools Expert oder Java Prozeduren. Der Einsatz einer Regelengine bringt zum einen bewährte Techniken zur Erkennung von Mustern out of the box (z.B. die Verteilung der Berechnungen auf mehrere Kerne). Zum anderen lassen sich die Restriktionen in Form von Drools Regeln leichter sukzessive und granular an veränderte Modelleigenschaften anpassen.
Weiterlesen
OptaPlanner hilft bei verteilten Schulstandorten (Teil 2/5)
Nachdem der erste Teil dieser Blogserie das fachliche Problem beschreibt, folgt hier der erste Teil der Modellierung.
Modellierung des Problems
In unserem Beispiel muss der Stundenplan nicht komplett neu erstellt werden. Wir können von einem bereits erstellten Stundenplan ausgehen und diesen optimieren. Zur Erstellung der Stundenpläne wird am ONG das weit verbreitete Stundenplanprogramm Untis genutzt. Der damit von der Schulleitung erstellte Stundenplan wird den Schülern und Lehrern u.a. über einen HTML-Export zur Verfügung gestellt. Zur Weiterverarbeitung in externen Programmen stellt das Modul Infostundenplan einen sogenannten Datenbank-Export zur Verfügung.
Weiterlesen
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.
Du muss angemeldet sein, um einen Kommentar zu veröffentlichen.