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
Possible start of thesis: 01.12.2024
Tutor: M.Sc. Maximilian Kratz
Student: Walid Tokhy

Back to overview

Motivation

Das Nurse Rostering Problem (NRP) ist ein Optimierungsproblem zur Schichtplanung in Krankenhäusern.
Grundsätzlich ist das Problem dafür zuständig eine gültige Zuordnung von Angestellten wie Stationspersonal zu Schichten (z. B. Tagesschicht, Spätschicht, Nachtschicht) zu finden.
Dabei müssen einige harte und weiche Bedingungen eingehalten werden.

Beispiele für harte Bedingungen könnten unter anderem folgende sein:

• Angestellte dürfen nicht mehr als eine Schicht pro Tag arbeiten.
• Sind Personen im Urlaub, so dürfen sie nicht für Schichten eingeplant werden.
• Jeder Schicht muss genau eine für die Station verantwortliche Person zugeteilt bekommen.

Weiche Bedingungen könnten beispielsweise sein:

• Schicht-Präferenzen der einzelnen Personen.
• Die Anzahl an Stunden, welche eine einzelne Person pro Woche arbeitet.
• Gewisse Kombinationen von Personen sollten nach Möglichkeit nicht in der selben Schicht auftauchen, da sie sich nicht gut vertragen.

Mit steigender Anzahl von Personen, Schichten und Nebenbedingungen wird das (manuelle) Finden eines gültigen Schichtplans immer komplizierter.
Ein Ansatz um das beschriebene Problem nicht manuell sondern automatisiert zu lösen ist die Verwendung von Integer Linear Programming (ILP).
ILP ist ein mathematisches Optimierungsverfahren, welches eine lineare Zielfunktion optimiert und dabei auf die Einhaltung mehrere linearer Nebenbedingungen achtet.
Zusätzlich müssen in der Kategorie der ILP Probleme alle verwendeten Variablen ganzzahlig sein, beispielsweise x_ij = 1 für Person i bekommt Schicht j und x_ij = 0 sonst.
ILPs können automatisiert durch hochentwickelte (kommerzielle) Programme (sog. Solver) automatisch gelöst werden.
Ein Nachteil ist jedoch, dass für jede Probleminstanz eine Vielzahl von (Un-)Gleichungen und Variablen per Hand erstellt und in den Solver eingelesen werden müssen, was die Verwendung mühselig macht.

Das am Fachgebiet Echtzeitsysteme entwickelte Framework GIPS (Graph-Based (M)ILP Problem Specification, https://gips.dev) schafft dafür Abhilfe indem es Graph Transformation (GT) und ILP verbindet.
Eine eigene domänenspezifische Sprache (GIPSL) wird dazu verwendet eine abstrakte Spezifikation zu erstellen, die GT-Muster und -Regeln verwendet um mit einer konkret Modell automatisiert ein ILP-Problem zu bauen und durch einen Solver lösen zu lassen.
Der Solver bestimmt welche GT-Regeln angewendet werden sollen um anschließend das Modell zu verändern und somit in einen optimalen Zustand zu überführen.
Im Kontext dieser Arbeit bedeutet das Anwenden von GT-Regeln beispielsweise eine Person einer Schicht zuzuweisen.

Task

In dieser Abschlussarbeit soll eine GIPSL-Spezifikation entwickelt werden, mit deren Hilfe unter Verwendung des GIPS-Frameworks automatisiert gültige Zuteilungspläne für ein(e) Krankenhaus(station) berechnen werden können.
Dafür sind folgende Arbeitspakete notwendig:

• Literaturrecherche zum NRP: Welche Bedingungen müssen eingehalten werden? Gibt es standardisierte Benchmarks mit Beispielproblemen, die gelöst werden können?
• Erstellung eines Lastenheftes und Arbeitsplans in Absprache mit dem Betreuer.
• Falls die Suche nach einem Benchmarkszenario erfolgreich war: Implementierung einer (manuellen) Modelltransformation um das gefundene Szenario (später) in GIPS einlesen und nach der Lösung durch GIPS validieren zu können.
• Falls die gefundenen Benchmarkszenarien nicht zufriedenstellend dokumentiert sind: Implementierung eines Aufgabengenerators sowie eines Lösungsvalidators für Modelle.
• GIPSL-Spezifikation entwickeln, welche das Szenario automatisiert lösen kann.
• Forschungsfragen:
  • Bis zu welchem Grad lässt sich das NRP mit GIPSL spezifizieren?
  • Bis zu welcher Modellgröße ist der Ansatz (aufgrund der langen Laufzeit des Solvers) in der Praxis verwendbar?
  • Wie können Heuristiken gewinnbringend eingesetzt werden um die Laufzeit der Implementierung zu verkürzen (z. B. wochenweises statt jahresweise Planen)?
• Evaluation:
  • Performanzmessung des Ansatzes für mehrere Modellgrößen.
  • Idealerweise Vergleich mit einem anderen Ansatz aus der Literatur.

Referenzen

• Ein guter Startpunkt für eine Literaturrecherche ist dieses Survey-Papier:
  • C. M. Ngoo, S. L. Goh, S. N. Sze, N. R. Sabar, S. Abdullah, G. Kendall, "A Survey of the Nurse Rostering Solution Methodologies: The State-of-the-Art and Emerging Trends," in IEEE Access, vol. 10, pp. 56504-56524, 2022, doi: https://doi.org/10.1109/ACCESS.2022.3177280.
• Grundlagen zu ILP finden sich in diesem Buch:
  • S. P. Bradley, A. C. Hax, T. L. Magnanti, "Applied Mathematical Programming," Addison-Wesley Publishing Company, 1977, isbn: 9780201004649.
• Eine Vorstellung des GIPS-Frameworks ist in diesem Papier enthalten:
  • S. Ehmes, M. Kratz, A. Schürr, "Graph-Based Specification and Automated Construction of ILP Problems," in Proceedings of the 13th International Workshop on Graph Computational Models - GCM 2022, pp. 3-22, 2022, doi: https://doi.org/10.4204/EPTCS.374.3.

Preconditions

• Sehr gute Java-Programmier-Kenntnisse
• Vorkenntnisse über ILP (wünschenswert aber optional)
• Vorkenntnisse über GT (wünschenswert aber optional)
• Kenntnisse über den Planungsablauf einer Krankenhausstation (hochoptional)

Back to overview

Zu den abgeschlossenen Arbeiten