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.

Optimierung

Aus den Eingangsdaten der Stundenplanverwaltungssoftware Untis wird hierzu zunächst eine Ausgangslösung erstellt (Zeile 3). Mithilfe der SolverFactory wird ein Solver mit der zuvor erstellten Konfiguration erzeugt (Zeile 5-6). Über einen Eventlistener werden neue Lösungen abgefangen und im Format von Untis in eine CSV Datei geschrieben (Zeile 8-22).

[code language=”java” collapse=”true” title=”Starten des Solvers”]
public static void main(String[] args) throws MalformedURLException {
UntisSolutionIO io = new UntisSolutionIO();
Solution s = io.read(new File(INPUT_FILE));

SolverFactory solverFactory = SolverFactory.createFromXmlResource(SOLVER_CONFIG);
final Solver solver = solverFactory.buildSolver();

solver.addEventListener(event -> {
if (solver.isEveryProblemFactChangeProcessed()) {
final Solution latestBestSolution = event.getNewBestSolution();
long now = new Date().getTime();
try {
List<Lesson> write = LectureLessonConverter
.convertToLessons(((CourseSchedule) latestBestSolution).getLectures());
TimeTableCsvParser.lessonsToCsv(write, "data//untis//solved//lesson_kw45_solved_" + now +
"_" + latestBestSolution.getScore().toString().replace("/", "_") + ".csv");
} catch (IOException e) {
logger.error("Error writing solution to file", e);
}
logger.info("Best solution changed, new score: " + latestBestSolution.getScore());
}
});

solver.solve(s);
}
[/code]

Die Eingangsdaten enthalten 1278 Schulstunden, die von 72 Lehrern unterrichtet und von den Schülern aus 21 verschiedenen Klassen besucht werden. Während der Optimierung werden diese so auf die 50 möglichen Zeiträume einer Schulwoche verteilt, dass alle zuvor definierten Bedingungen erfüllt werden und die Wechsel der Lehrer zwischen den Gebäuden möglichst gering ist.

Ein Blick auf die Logausgabe der Optimierung soll an dieser Stelle die Arbeitsweise des Solvers veranschaulichen:

[code]
[INFO ] 2014-12-27 14:42:32.694 [main] DefaultSolver – Solving started: time spent (1352), best score (0/0/-90/-42/-16/-34), environment mode (REPRODUCIBLE), random (JDK with seed 0).
[TRACE] 2014-12-27 14:42:32.797 [main] LocalSearchDecider – Move index (0), score (0/0/-90/-42/-16/-34), accepted (true), move (EKu Teacher: Lie Grade: 7.1- @ [Period-10] Building: HAUPT Room: d212 untisId: 334 <=> Ku Teacher: Lie Grade: 7.1- @ [Period-11] Building: HAUPT Room: d212 untisId: 282).
[TRACE] 2014-12-27 14:42:32.823 [main] LocalSearchDecider – Move index (1), score (0/0/-90/-42/-16/-34), accepted (true), move (Ku Teacher: Lie Grade: 7.1- @ [Period-11] Building: HAUPT Room: d212 untisId: 282 <=> EKu Teacher: Lie Grade: 7.1- @ [Period-10] Building: HAUPT Room: d212 untisId: 334).
[TRACE] 2014-12-27 14:42:32.852 [main] LocalSearchDecider – Move index (2) not doable, ignoring move (Ku Teacher: Lie Grade: 7.1- @ [Period-11] Building: HAUPT Room: d212 untisId: 282 <=> Ku Teacher: Lie Grade: 7.1- @ [Period-11] Building: HAUPT Room: d212 untisId: 282).
[TRACE] 2014-12-27 14:42:32.873 [main] LocalSearchDecider – Move index (3), score (0/0/-90/-42/-16/-34), accepted (true), move (Ku Teacher: Lie Grade: 7.1- @ [Period-11] Building: HAUPT Room: d212 untisId: 282 <=> EKu Teacher: Lie Grade: 7.1- @ [Period-10] Building: HAUPT Room: d212 untisId: 334).
[TRACE] 2014-12-27 14:42:33.013 [main] LocalSearchDecider – Move index (4), score (-66/0/-90/-51/-16/-32), accepted (false), move (LectureChangeMove: SubsequentLecturesId 58 setting new starting Period[Period-40]).
[TRACE] 2014-12-27 14:42:33.114 [main] LocalSearchDecider – Move index (5), score (-4/0/-90/-42/-16/-34), accepted (false), move (LectureChangeMove: SubsequentLecturesId 69 setting new starting Period[Period-2]).
[TRACE] 2014-12-27 14:42:33.137 [main] LocalSearchDecider – Move index (6), score (-16/0/-96/-42/-14/-34), accepted (false), move (LectureChangeMove: SubsequentLecturesId 581 setting new starting Period[Period-32]).
[TRACE] 2014-12-27 14:42:33.166 [main] LocalSearchDecider – Move index (7), score (0/0/-90/-42/-16/-33), accepted (true), move (LectureChangeMove: SubsequentLecturesId 237 setting new starting Period[Period-0]).
[INFO ] 2014-12-27 14:42:33.324 [main] Main – Best Solution changed, new Score: 0/0/-90/-42/-16/-33
[DEBUG] 2014-12-27 14:42:33.324 [main] DefaultLocalSearchPhase – LS step (0), time spent (1982), score (0/0/-90/-42/-16/-33), new best score (0/0/-90/-42/-16/-33), accepted/selected move count (4/7), picked move (LectureChangeMove: SubsequentLecturesId 237 setting new starting Period[Period-0]).
[/code]

Verschiedene generierte Moves werden ausgewählt, auf die derzeitige Lösung angewendet und evaluiert, ob diese Auswahl zu einer gültigen und evtl. besseren Nachbarlösung führt. Die abgebildeten Logausgabe des ersten Schritts der Optimierung zeigt, dass acht Moves pro Optimierungsschritt evaluiert werden (Zeile 2-9) und dabei, neben einem ungültigen Move (Zeile 4), auch ein Move, der zu einer neuen beste Lösung, mit dem Scorewert 0/0/-90/-42/-16/-33, gefunden wird (Zeile 10).

Ausgehend des zuvor festgelegten Schemas der Scorewerte, lässt sich dieser Scorewert wie folgt interpretieren:

			Wechsel in Pause mit:
	Scorewert	Verletzung harte Restriktionen	5 min	10 min	20 min	30 min	> 30 min	Summe
Ausgangslösung	0/0/-90/-42/-16/-34	0	0	15	14	8	34	71
Lösung nach Schritt 1	0/0/-90/-42/-16/-33	0	0	15	14	8	33	70

Ergebnis

Nach einer Laufzeit von etwa einer Minute konnte die Optimierung folgendes Ergebnis erzielen:

			Wechsel in Pause mit:
	Scorewert	Verletzung harte Restriktionen	5 min	10 min	20 min	30 min	> 30 min	Summe
Ausgangslösung	0/0/-90/-42/-16/-34	0	0	15	14	8	34	71
Lösung nach Schritt 1	0/0/-90/-42/-16/-33	0	0	15	14	8	33	70
Lösung nach Schritt n	0/0/-12/-27/-4/-9	0	0	2	9	2	9	22

Insgesamt können also durch eine optimierte Planung der exemplarischen Schulwoche 49 Standortwechsel der Lehrer vermieden werden. Dies trägt zu einem deutlich reibungsloseren Ablauf des Schulalltages, weniger gefahrenen Kilometern und zu erholsameren Pausen für alle bei.

Zusammenfassung

Dieser Blogbeitrag hat anhand eines einfachen Beispiels aus der Praxis einen Einblick in den Einsatz von OptaPlanner gegeben. OptaPlanner lässt sich auf vielfältige Art und Weise in Java und Java EE Anwendungen integrieren und stellt technische Komponenten zur Optimierung verschiedenster Planungsprobleme zur Verfügung.

Haben Sie Anregungen oder ein spannendes Planungsproblem? Melden Sie sich bei uns!