Folgende Materialien helfen beim Erstellen von wissenschaftlichen Arbeiten:

• Vorlage für Studien-, Bachelor und Masterarbeiten am FG Echtzeitsysteme [Github]
• Vorlage für Präsentationen am FG Echtzeitsysteme [Github]

Type of thesis: Bachelor-Thesis
State: Laufende Arbeiten
Tutor: M.Sc. Maximilian Kratz

Back to overview

Motivation

Das Graph-Based (M)ILP Problem Specification (GIPS) Framework wurde am Fachgebiet Echtzeitsysteme entwickelt und kombiniert Graph-Transformation (GT) mit (Mixed) Integer Linear Programming (MILP) um komplexe Optimierungsprobleme systematisch zu modellieren und zu lösen. Damit eine spezifische Probleminstanz von GIPS verarbeitet werden kann, muss sie konform zu ihrem übergeordneten Metamodell sein. Durch die domänenspezifische Sprache GIPSL können dann für das Modell GT-Regeln, Constraints und die zu optimierende Zielfunktion definiert werden. Eine GT-Regel wird durch eine linke Seite (engl. Left Hand Side, kurz LHS) beschrieben, welche ein mögliches Pattern im Modell spezifiziert und eine rechte Seite (engl. Right Hand Side, kurz RHS), die angibt, wie ein Musterfund durch Anwenden der Transformationsregel angepasst werden soll. Wird im Modell ein solches Pattern gefunden, spricht man von einem Match, woraus GIPS automatisch eine binäre ILP-Variable konstruiert und diese in einem Mapping mit der entsprechenden GT-Regel verknüpft. Ein externer MILP-Solver erhält anschließend alle generierten ILP-Variablen und berechnet die optimale Anwendung der GT-Regeln im Kontext der Zielfunktion und allen spezifizierten Constraints. Im Rahmen der Modellierung in GIPS entstehen regelmäßig Situationen, in denen Regeln und deren Anwendung implizit voneinander abhängig sind. Diese können in Form einer Bool’schen Implikation auftreten, die beispielsweise definiert, dass vor der Anwendung von Regel y erst Regel x ausgeführt werden muss.

y ⇒ x

Durch die zeitliche Abhängigkeit kann es dazu kommen, dass Regel y nicht korrekt ausgeführt wird, da das benötigte Match noch nicht existiert. Solche Anwendungsfälle treten bei der Integrated Healthcare Timetabling Competition (IHTC) auf. Die IHTC formuliert ein integriertes Optimierungsproblem im Bereich der Krankenhausplanung, das die drei NP-schweren Probleme Patient Admission Scheduling, Nurse-to-Room Assignment und Surgical Case Planning miteinander verknüpft. Im Rahmen der Planungsaufgabe müssen dabei folgende Entscheidungen getroffen werden:

• Festlegung des Aufnahmedatums für jeden Patienten oder gegebenenfalls die Verschiebung der Aufnahme in den nächsten Planungszeitraum.
• ZuweisungeinesZimmers,indemderPatientwährendseinesgesamtenAufenthaltsuntergebracht ist.
• Zuteilung einer Pflegekraft zu jedem belegten Zimmer in jeder Schicht des Planungszeitraums.
• Auswahl des Operationssaals, in dem der Patient am Tag seiner Aufnahme operiert wird.

Task

Bisher müssen implizite Regelabhängigkeiten vollständig manuell in der GIPS-Spezifikation hinterlegt werden. Der Anwender definiert explizit, dass eine Regel x angewendet werden muss, bevor Regel y ausgeführt werden kann. Diese Vorgehensweise ist nicht nur zeitaufwendig, sondern auch fehleranfällig, da Abhängigkeiten zwischen Regeln leicht übersehen oder falsch definiert werden können. Insbesondere ergeben sich jedoch Probleme bei der Patternsuche für die implizit auszuführende GT-Regel, wenn durch die Anwendung von Regel x erst ein Teil der Vorbedingung von Regel y erfüllt wird. In GIPS erfolgt das Pattern Matching einmalig zu Beginn des Optimierungsprozesses. Dabei werden alle erkannten Matches von GT-Regeln und Mustern, die Teil eines Mappings sind, mit ILP-Variablen versehen.Da Regel x und Regel y zeitlich nacheinander ausgeführt werden müssen, kann es vorkommen, dass die Anwendung von Regel x neue Strukturen im Modell erzeugt, die erst dann als gültiges Match für Regel y dienen. Da der Pattern Matcher jedoch nur auf die ursprüngliche Probleminstanz zugreift, bleiben solche Abhängigkeiten unberücksichtigt, wodurch Regel y möglicherweise nicht im ILP-Problem enthalten ist. Dies kann dazu führen, dass notwendige Transformationen nicht durchgeführt werden und ein fehlerhaftes oder nicht optimales Modell entsteht.

Um diesem Problem entgegenzuwirken, wird im Rahmen dieser Arbeit ein angepasster Spezifikationsansatz für GIPS eingeführt: Anstatt Constraints und Optimierungsziele direkt über Regelanwendungen zu formulieren, erfolgt die Modellierung über neu eingeführte virtuelle Kanten. Diese verhalten sich wie reguläre Kanten im Graphen, sind jedoch eindeutig als virtuell markiert. Für die Erzeugung dieser Kanten wird eine Teilmenge der GT-Regeln aus dem in der GIPSL-Spezifikation enthaltenen Regelsatz entnommen und erschöpfend angewendet. So werden alle potentiellen Anwendungsstellen erst einmal unabhängig von der Anwendung anderer GT-Regeln im aktuellen Modellzustand erkannt. Dieser neue Regelsatz wird iterativ ausgeführt, wobei jede Regelanwendung pro Iteration höchstens eine neue virtuelle Kante erzeugen darf. Mehrfache Anwendungen des Regelsatzes sind möglich, sofern sich dadurch der Graph verändert, allerdings muss der Anwender sicherstellen, dass dieser Vorgang terminiert. Nach der Terminierung des modifizierten GT-Regelsatzes enthält der Graph alle virtuellen Kanten, die für das konkrete Modell überhaupt erzeugt werden können. Im Anschluss erfolgt die eigentliche Optimierung ausschließlich über die erzeugten virtuellen Kanten.

Jede dieser Kanten wird im ILP-Modell durch eine binäre Variable repräsentiert, die entweder deaktiviert (Wert 0) oder aktiviert (Wert 1) sein kann. Constraints entscheiden, welche Kanten zulässig sind, während das Optimierungsziel darüber bestimmt, welche Kanten bevorzugt aktiviert werden. Die aktivierten virtuellen Kanten werden schließlich in den Graphen übernommen. Auf diese Weise können potentielle Matches für die implizit angegebene GT-Regel gefunden werden, ohne dass der Pattern Matcher nach der Durchführung von Regel x erneut ausgeführt werden muss.

Eine solche Implikation kann anschaulich bei der Verlängerung des Aufenthalts eines Patienten im Kontext des IHTC dargestellt werden:

• Regel x plant die Erstaufnahme eines Patienten in eine Schicht und erzeugt eine neue Kante.
• Regel y verlängert den Aufenthalt eines Patienten um eine Folgeschicht. Dies darf nur erfolgen, wenn der Patient bereits aufgenommen wurde und eine passende Kante existiert.
• Für Regel y wird kein gültiges Match gefunden, wenn die Aufnahme des Patienten noch nicht erfolgt ist.

Back to overview

Zu den abgeschlossenen Arbeiten