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.

Bewertungsfunktion und Restriktionen

Eine Regelengine arbeitet auf einer Menge von Fakten. In unserem Beispiel sind dies die aus dem Datenmodell abgeleiteten Objekte (Unterrichtsstunden, Lehrer, Schulstunden usw.). Die Regeln werden in deklarativer Form in der Drools eigenen Regelsprache formuliert. Eine Regel besteht aus zwei Teilen. Einem Bedingungsteil, der definiert, wann die Regel auslösen soll, und einem zweiten Teil, der festlegt, was ausgeführt werden soll, wenn die Regel auslöst. Im Rahmen der Mustererkennung wird überprüft, welche der Regeln der Regelbasis auslösen. Im Normalfall löst jedes Vorkommen eines bestimmten Musters an Fakten, welche die Bedingung einer Regel erfüllen, die Aktionen der jeweiligen Regel aus.

schemaregelengine

Wie zuvor erwähnt, implementiert die Solution Klasse CourseSchedule das Interface org.optaplanner.core.api.domain.solution.Solution. Entsprechend des Interface enthält die Klasse auch ein Feld mit dem Scorewert der Lösung. Der Scorewert einer Lösung erlaubt Optaplanner verschiedene Lösungen qualitativ zu vergleichen. Generell erlaubt Optaplanner verschiedene Arten von Scorewerten (z.B. positive und negative). In unserem Beispiel existieren harte Restriktionen, die alle erfüllt sein müssen, damit ein Stundenplan überhaupt gültig ist, und weiche Restriktionen, an der sich die Qualität unserer Lösung festmachen lässt (Anzahl der Standortwechsel). Wir nutzen hier also einen Scorewert mit zwei Ebenen.

Für jeden Standortwechsel, den ein Lehrer bewältigen muss, verringern wir den Scorewert auf Ebene der weichen Restriktionen. Verletzung von Restriktionen führen zur Verringerung des Scorewertes. Ziel der Optimierung ist es, eine Lösung zu finden, die auf der Ebene der harten Restriktionen einen Wert von 0 erreicht und auf Ebene der weichen Restriktionen möglichst nahe bei 0 liegt (Maximierung).  Bei einem Scorewert von 0 auf beiden Ebenen wäre eine optimale Lösung gefunden – es finden keine Standortwechsel statt und alle harten Restriktionen sind erfüllt.

Dem entspricht Optaplanners BendableScore. Bei diesem lassen sich die Anzahl der Scorelevel für harte und weiche Restriktionen frei konfigurieren. Die Pausen am ONG sind unterschiedlich lange und eignen sich dementsprechend unterschiedlich gut für einen Standortwechsel der ca. 20 Minuten dauert. Neben einem Scorewert auf der Ebene der harten Restriktionen wird für jede Pausenlänge (insgesamt 5) ein eigener Scorewert auf Ebene der weichen Restriktionen konfiguriert:

[code title=”SolverConfig.xml”]
…
<scoreDirectorFactory>
<scoreDefinitionType>BENDABLE</scoreDefinitionType>
<bendableHardLevelsSize>1</bendableHardLevelsSize>
<bendableSoftLevelsSize>5</bendableSoftLevelsSize>
<scoreDrl>de/akquinet/untis/planner/scoreRules.drl</scoreDrl>
</scoreDirectorFactory>
…
[/code]

Der komplette Scorewert einer Lösung besteht also aus 6 Ebenen. Auf jeder Ebene repräsentiert ein Integer Wert die Qualität der Lösung hinsichtlich folgender Kriterien:

harte Restriktionen Wechsel in 5 min Pause Wechsel 10 min Pause Wechsel  20 min Pause Wechsel  30 min Pause Wechsel  > 30 min

Die harten und weichen Restriktionen des Zuordnungsproblems werden in Form von Drools Regeln definiert. Der folgende Ausschnitt zeigt beispielhaft die Regel roomOccupancy:

[code title=”DRL Harte Restriktion – Gleichzeitige Belegung Raum”]
rule "roomOccupancy"
when
$leftLecture : Lecture($leftId : id, period != null, $period : period,
course.room != null, $room : course.room)

$rightLecture : Lecture(period == $period,course.room == $room,id > $leftId,
$rightId : id, $leftLecture.coupledId != $rightLecture.coupledId)
then
scoreHolder.addHardConstraintMatch(kcontext,0 ,-1);
end
[/code]

Diese Regel löst aus, wenn im Arbeitsspeicher der Regelengine zwei Unterrichtsstunden existieren, die den gleichen Raum zur gleichen Schulstunde belegen – was nicht möglich ist. Als Aktion wird der Scorewert der Lösung für harte Restriktionen um 1 verringert (siehe Zeile 9). Der Scorewert ist damit kleiner 0 und die Lösung kann von Optaplanner als unzulässig identifiziert werden.

Ein Standortwechsel kann in Pausen verschiedener Länge stattfinden. Die weiche Restriktion für die Standortwechsel wird daher auf eine Regel und vier, für jede Pausenlänge jeweils eine, Erweiterungen (extends) aufgeteilt. Die Regel teacherChangesBuildinginBreak identifiziert einen Standortwechsel.
Entsprechend der Länge der Pause, in der dieser Standortwechsel stattfindet, löst eine der ableitenden Regeln aus. Findet der Standortwechsel beispielsweise nach der 6. Schulstunde statt stehen dem Lehrer 30 Minuten dafür zur Verfügung. Die Regel teacherChangesBuildingin30minBreak verringert den Scorewert für weiche Restriktionen um den Wert 2 (siehe Zeile 33).

[code title=”DRL Weiche Restriktion – Gebäudewechsel” collapse=”true”]
rule "teacherChangesBuildinginBreak"
when
$leftLecture : Lecture($leftId : id, $leftCourse : course, $leftPeriod : period,
period != null,

$leftTeacher : course.teacher, $leftBuilding : course.room.building, period != null,
$leftTeacher != null,
$leftTimeslotIndex : period.timeslot.timeslotIndex)

not(Lecture(course.teacher == $leftTeacher,period.day == $leftLecture.period.day,
course.room.building == $leftLecture.course.room.building,
period.timeslot.timeslotIndex == $leftLecture.period.timeslot.timeslotIndex,
getId() > $leftLecture.getId()))

$rightLecture : Lecture($rightId : id, $rightPeriod : period, period != null,
course.teacher == $leftTeacher,
period.day == $leftPeriod.day,
course.room.building != $leftBuilding,
period.timeslot.timeslotIndex == $leftPeriod.timeslot.timeslotIndex+1)

not(Lecture(course.teacher == $rightLecture.course.teacher,
period.day == $rightLecture.period.day,
course.room.building == $rightLecture.course.room.building ,
period.timeslot.timeslotIndex == $rightLecture.period.timeslot.timeslotIndex,
getId() > $rightId))
then
end

rule "teacherChangesBuildingin30minBreak" extends "teacherChangesBuildinginBreak"
when
eval($leftTimeslotIndex == 5)
then
scoreHolder.addSoftConstraintMatch(kcontext,3, -2);
end

rule "teacherChangesBuildingin20minBreak" extends "teacherChangesBuildinginBreak"
when
eval($leftTimeslotIndex == 1)
then
scoreHolder.addSoftConstraintMatch(kcontext,2, -3);
end

rule "teacherChangesBuildingin10minBreak" extends "teacherChangesBuildinginBreak"
when
eval($leftTimeslotIndex == 3)
then
scoreHolder.addSoftConstraintMatch(kcontext,1, -6);
end

rule "teacherChangesBuildingin5minBreak" extends "teacherChangesBuildinginBreak"
when
eval($leftTimeslotIndex == 7)
then
scoreHolder.addSoftConstraintMatch(kcontext,0, -12);
end
[/code]

Nachdem die Restriktionen formalisiert und damit auch die Möglichkeit zur Bewertung verschiedener Lösungen geschaffen ist, kann das Zuordnungsproblem mit den generischen Heuristiken von Optaplanner gelöst werden.

Mehr dazu im nächsten Teil dieser Serie.