Lösung von Optimierungsproblemen mit dem Open-Source-Tool

JBoss OptaPlanner: Optimierung 2.0

Christian Treptau, David Jorch, Jan-Philipp Friedenstab
© shutterstock.com/Manczurov

Wettbewerbsfähigkeit unter Kostendruck erfordert einen effizienten Einsatz von Ressourcen. Dafür müssen die geeigneten Mittel in angemessener Menge zur richtigen Zeit eingeplant werden. Das gilt für die Maschinennutzung ebenso wie für Transportmittel oder Personal. Durch die toolgestützte Nutzung mathematischer Optimierungsverfahren lassen sich komplexe Planungsaufgaben lösen, automatisieren und ergebnisseitig verbessern. In diesem Artikel skizzieren wir ein Vorgehensmodell am Beispiel des Open-Source-Tools JBoss OptaPlanner. Ausführlicher wird das Werkzeug demnächst im Java Magazin vorgestellt.

Automatisierte Planung des Ressourceneinsatzes

Unternehmen stehen regelmäßig vor der Herausforderung, ihren Ressourceneinsatz optimieren zu müssen, um durch Effizienzsteigerungen im Wettbewerb bestehen zu können. In der Produktion müssen Maschinenbelegungspläne, in der Logistik Tourenpläne und im Workforce-Management Dienstpläne erstellt werden.

Häufig entstehen komplexe Planungsprobleme aus einer Vielzahl möglicher Optionen und der damit verbundenen Schwierigkeit, die beste Lösung zu finden. In Forschung und Wirtschaft existieren mathematische Optimierungsverfahren zur Lösung solcher Probleme. Viele dieser Verfahren sind ohne IT-Unterstützung praktisch nicht durchführbar. Dank marktreifer Software, auch aus dem Open-Source-Bereich, lassen sich die Vorteile der automatisierten Optimierung nutzen.

Software-Komponenten wie JBoss OptaPlanner schaffen die Möglichkeit, automatisierte Optimierungsschritte in Individualsoftware oder eine existierende Anwendungslandschaft zu integrieren und so den individuellen Anforderungen von Unternehmen gerecht zu werden.

JBoss OptaPlanner

OptaPlanner ist ein Java-basiertes Open-Source-Framework (Apache Software License 2.0) zur automatisierten Lösung von Planungsproblemen. Zentrale Komponente ist der so genannte Solver. Dieser wendet heuristische und metaheuristische Optimierungsalgorithmen an, um durch eine möglichst effiziente Suche im Lösungsraum eine gute Lösung für das gegebene Planungsproblem in annehmbarer Zeit zu finden.

Die Entwicklung von OptaPlanner erfolgt als JBoss „Community Project“ im Rahmen der KIE-Projektfamilie (KIE = „Knowledge Is Everything“). Die im August 2014 veröffentlichte Version 6.1.0 ist Grundlage dieses Artikels.

Ein wenig Theorie: Planung und Optimierungsprobleme

Bei einem Optimierungsproblem sind eine Menge von möglichen Lösungen (der Lösungsraum) und eine Zielfunktion gegeben. Das Ziel ist es nun, für die Problemstellung die optimale Lösung gemäß der Zielfunktion zu finden. Diese kann zum Beispiel Kosten ausdrücken, die minimiert werden sollen, oder einen zu maximierenden Gewinn.

Bei der Problemlösung sind in der Regel Constraints (Nebenbedingungen) zu beachten. Sind diese zwingend einzuhalten, damit eine vorliegende Lösung gültig ist, werden sie auch als Hard Constraints bezeichnet. Soft Constraints dagegen dürfen, sollten aber nicht verletzt werden. Dieser Umstand wird in der Zielfunktion über so genannte Strafkosten abgebildet, die mit der Schwere der Verletzung von Nebenbedingungen steigen.

Bei vielen Problemstellungen im Kontext der Planung ist der Lösungsraum so groß, dass es nicht möglich ist, effizient eine optimale Lösung zu finden. Die bisher bekannten Algorithmen finden optimale Lösungen meist nur mit exponentiellem Rechenaufwand. Eine wichtige Eigenschaft dieser Problemstellungen ist jedoch, dass eine vorgeschlagene Lösung in annehmbarer Zeit verifiziert werden kann (s. Gerdts, Matthias; Lempio, Frank: „Mathematische Optimierungsverfahren des Operations Research“, De Gruyter, 2011, S. 8‑9). Daher kommen Metaheuristiken zum Einsatz, die Lösungen iterativ und „intelligent“ vorschlagen und verifizieren. Metaheuristiken sind Algorithmen, die problemunabhängig für die Lösungssuche durchzuführende Schritte definieren, die in angemessener Zeit zu guten Lösungen führen (vgl. Nickel, Stefan; Stein, Oliver; Waldmann, Karl-Heinz: „Operations Research“, 2. Aufl., Springer Gabler, 2014, S. 209‑221 sowie Luke, Sean: „Essentials of Metaheuristics“, Lulu Press, 2. Aufl., 2013, S. 17‑30: http://cs.gmu.edu/~sean/book/metaheuristics).

Ein Beispiel wäre die Tabu-Suche, die von Fred W. Glover entwickelt wurde:

Schritt 1: Erzeugung einer Initiallösung (zufällig oder Konstruktionsheuristik)

Schritt 2: Erzeugung einer Menge von ähnlichen Lösungen

Schritt 3: Daraus Auswahl der Lösung mit dem besten Zielfunktionswert, falls Lösung nicht in Tabu-Liste, sonst Auswahl der nächstbesten Lösung, die nicht in Tabu-Liste

Schritt 4: Ausgewählte Lösung in Tabu-Liste aufnehmen; die Tabu-Liste hat eine Größenbeschränkung, daher ggf. alte Einträge entfernen; weiter mit Schritt 2.

Sobald ein definiertes Terminierungskriterium erreicht ist, endet die Tabu-Suche, und die beste der gültigen, gefundenen Lösungen wird gewählt. Typische Bedingungen sind: 

  • Die maximale Zeitdauer für die Lösungsfindung ist erreicht oder
  • die maximale Anzahl an Iterationen ohne Verbesserung der Lösung ist erreicht oder
  • eine Lösung mit geforderter Mindestqualität wurde gefunden.

Der Sinn einer Tabu-Suche wird anhand der folgenden Metapher verdeutlicht (Abb. 1). Ein Bergsteiger möchte den Gipfel erklimmen (globales Maximum, die optimale Lösung). Um diesen zu erreichen, darf er seinen Aufstieg nicht auf kleineren Anhebungen beenden (lokale Maxima), nur weil es in der näheren Umgebung nicht weiter bergauf geht. Die Tabu-Liste soll verhindern, sich mit bereits bekannten, scheinbar optimalen Lösungen zufrieden zu geben. Nur so besteht die Chance, noch bessere Lösungen zu erreichen.

Tabusuche

Aufmacherbild: businessman writing optimization concept on black background von shutterstock.com / Urheberrecht: Manczurov

[ header = Vorgehensmodell ]

Vorgehensmodell

Die Lösung von Planungsaufgaben mit OptaPlanner folgt einem vierschrittigen Vorgehen, das wir im Folgenden vorstellen (Abb. 2). Dabei wird der vierte Schritt – Optimierung durchführen – bei wiederholt anstehenden Planungsaufgaben immer wieder durchgeführt.

Vorgehensmodell

 

Planungsproblem modellieren

Im ersten Schritt ist zunächst die fachliche Fragestellung bzw. das Ziel der Optimierung zu definieren. Auf dieser Grundlage kann anschließend die Umsetzung mit OptaPlanner erfolgen. Für die fachlich relevanten Objekte wird dabei ein Domänenmodell aus einfachen Java-Klassen erstellt. Unterschieden werden hier problem facts, planning entities und planning solutions. Im Gegensatz zu problem facts werden planning entities in der Optimierungsphase aktiv durch den Solver verändert. Eine planning solution hat zwei mögliche Funktionen – sie kann das zu lösende Planungsproblem oder eine mögliche Lösung für dieses Problem repräsentieren.

Score-Berechnung implementieren

Die Score-Berechnung in OptaPlanner bildet Zielfunktion und Nebenbedingungen ab. Der Score drückt somit die Güte und Gültigkeit einer Lösung aus. Während der Optimierung berechnet OptaPlanner den Score für eine Vielzahl von Lösungen, um diese miteinander zu vergleichen.

Es ist Aufgabe des Problemmodellierers, die Art und Weise der Score-Berechnung festzulegen. Eine Besonderheit von OptaPlanner besteht darin, dass die Berechnung nicht nur in Java, sondern auch mit der Business Rules Engine JBoss Drools Expert erfolgen kann. Dabei wird mithilfe von Regeln ausgedrückt, wie sich der Score bei Verletzung von Hard Constraints und Soft Constraints verändert. Der Vorteil dieser Variante liegt u. a. darin, dass etablierte Pattern-Matching-Algorithmen zum Einsatz kommen, um die Regeln abzuarbeiten, d. h. den Score zu ermitteln. Das Konzept des Forward Chainings erlaubt dabei implizit eine inkrementelle Berechnung: Die Score-Berechnung baut auf einer Delta-Ermittlung zur vorherigen Lösung auf.

Solver konfigurieren

Die Konfiguration des OptaPlanner-Solvers geschieht über eine XML-Datei und besteht im Wesentlichen aus drei Teilen: 

Konfiguration des Modells

In der Konfiguration wird auf die Solution- und die PlanningEntity-Klasse des Planungsproblems verwiesen.

Konfiguration des Scores

In der Konfiguration werden der Pfad zur Regel-Datei und der Score-Typ angegeben.

Konfiguration der Optimierungsalgorithmen

Die Lösung eines Optimierungsproblems erfolgt bei OptaPlanner in so genannten Phasen, für die jeweils die zu verwendenden Optimierungsalgorithmen festzulegen sind. In jeder Phase wird eine Anzahl von Schritten durchgeführt. Jeder Schritt führt wieder zu einer Lösung.

Jede Optimierung startet mit einer Konstruktionsphase (Phase 0). Die Aufgabe der Konstruktionsphase ist es, eine Lösung zu finden, die die Grundlage für die eigentliche Optimierung bildet. Die nächsten Phasen führen die Optimierung auf Basis einer konfigurierbaren Metaheuristik wie zum Beispiel der Tabu-Suche durch.

Ein wichtiges Element der Solver-Konfiguration ist die Definition von Terminierungskriterien. Mögliche Kriterien sind zum Beispiel die Anzahl der maximal durchzuführenden Schritte ohne Verbesserung der Lösung, ein bestimmter, zu erreichender Score oder der Abbruch nach einer festgelegten Zeitdauer.

Optimierung durchführen

Die Durchführung der Optimierung mit OptaPlanner besteht aus vier Teilschritten:

Laden der Ausgangsdaten und Erstellung des Planungsproblems

Im ersten Schritt werden die zu optimierenden Ausgangsdaten aus einer Datenquelle gelesen. Mit diesen Daten wird ein Objekt einer PlanningSolution-Klasse erstellt.

Erzeugung eines Solvers

Im zweiten Schritt wird auf Grundlage der Solver-XML-Konfiguration mithilfe der SolverFactory ein Solver-Objekt erzeugt.

Lösung des Planungsproblems durch den Solver

Im dritten Schritt wird dem Solver das Planungsproblem übergeben und die Optimierung gestartet. Der Solver führt nun die in der Konfiguration festgelegten Optimierungsalgorithmen aus. Die Ausführung der solve-Methode endet, wenn eines der definierten Terminierungskriterien erreicht ist.

Abruf der besten gefundenen Lösung

Nach Abschluss der Optimierung kann die beste durch den Solver gefundene Lösung abgerufen werden. Diese Lösung kann nun weiterverwendet werden.

Im Allgemeinen hängt die Qualität der gefundenen Lösung von verschiedenen Faktoren ab. Dazu gehören insbesondere die Problemgröße, die für die Optimierung zur Verfügung stehende Zeit und die Konfiguration der Optimierungsalgorithmen.

Beispielszenario

Auf GitHub stellen wir ein Beispielprojekt zur Lösung eines Optimierungsproblems mit OptaPlanner bereit. Als Problemstellung haben wir die Raum- und Vorlesungsplanung an Schulen und Universitäten gewählt, mit der viele schon einmal in Berührung gekommen sind. Das Beispiel ist bewusst einfach gehalten und basiert auf dem komplexeren Course-Timetabling-Szenario von OptaPlanner (siehe hier und hier).

Fazit

Steigende Ressourcenkosten oder sinkende Absatzpreise für Produkte oder Dienstleistungen (ob am Markt oder innerbetrieblich) erfordern eine Produktivitätssteigerung als Reaktion. Je nach Wettbewerbslage gilt es, weniger Ressourcen bei gleichbleibendem Output einzusetzen oder aber den (wertmäßigen) Output bei gleichbleibendem Ressourceneinsatz zu erhöhen. Überkapazität sollte nur bewusst – etwa als Risiko- und Flexibilitätspuffer – in Kauf genommen werden.

Die Optimierung des Ressourceneinsatzes erfordert oft die Lösung komplexer Planungsprobleme. Dank der Verfügbarkeit von Softwarekomponenten wie OptaPlanner, die mathematische Optimierungsverfahren anwenden, können Planungsaufgaben automatisiert werden. Dabei kommen etablierte Lösungsalgorithmen zum Einsatz, während die Rahmenbedingungen (Zielfunktion und Nebenbedingungen) individuell festgelegt werden.

Wegen der Funktionalität, der einfachen Integrierbarkeit und des Open-Source-Charakters von OptaPlanner fällt die Kosten-Nutzen-Abwägung auch in kleineren Projekten positiv für dessen Einsatz aus.  

Geschrieben von
Christian Treptau
Christian Treptau
Christian Treptau ist als Projektleiter für die viadee Unternehmensberatung GmbH tätig. In vielen Projekten hat er als Projektleiter oder Softwarearchitekt mitgewirkt. Sein Fokus liegt auf Prozessautomatisierung und Prozessoptimierung in komplexen Umfeldern. E-Mail: Christian.Treptau@viadee.de
David Jorch
David Jorch
David Jorch ist als Unternehmensberater in Kundenprojekten tätig. Seine Projekterfahrung umfasst u. a. den Einsatz von Rules Engines und Optimization Engines in verschiedenen Branchen, z. B. in der Automobilindustrie und im Modehandel. Ein weiterer Schwerpunkt liegt im Einsatz von Data Mining. E-Mail: David.Jorch@viadee.de
Jan-Philipp Friedenstab
Jan-Philipp Friedenstab
Jan-Philipp Friedenstab ist als IT-Berater bei der viadee Unternehmensberatung GmbH tätig. Sein Arbeitsschwerpunkt liegt im Java-Umfeld – hier war er in verschiedenen Kundenprojekten an der Konzeption und Realisierung von Webanwendungen und Job-basierten Backend-Systemen beteiligt. Mit OptaPlanner hat er komplexe Optimierungsprobleme im Bereich der Personaleinsatzplanung gelöst. E-Mail: Jan-Philipp.Friedenstab@viadee.de
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.