Algorithmic and practical aspects of appointment scheduling

Roth, Sarah Katharina; Lübbecke, Marco (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen : RWTH Aachen University (2020, 2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2020

Kurzfassung

Diese Dissertation motiviert sich aus dem Terminplanungsproblem in Krankenhäusern. Hierbei brauchen die Patienten Termine für mehrere Untersuchungen, wobei Reihenfolgebeziehungen zwischen den Untersuchungen bestehen können. Für jede Untersuchung wird eine Ressource benötigt. Es wird zwischen stationär aufgenommenen und ambulanten Patienten unterschieden. In dieser Arbeit wird eine zeitindizierte Formulierung für das Problem vorgestellt. Um mit den sehr langen Zeithorizonten umgehen zu können, wird eine geschachtelte Zeitaggregierung verwendet. Die zeitindizierte Formulierung wird durch (online) Heuristiken ergänzt, um Terminanfragen von ambulaten Patienten zeitgerecht beantworten zu können. Der Ansatz wird in einer ereignisorientieren Simulation getestet. Das betrachtete Terminplanungsproblem ist ein Spezialfall des Jobshop Scheduling Problems, wobei die Patienten Jobs entsprechen und die Termine den Vorgängen des Jobs. Basierend auf einer Flussformulierung für das Einmaschinenproblem wird eine erweiterte Formulierung für das Jobshop Problem mit Earliness/Tardiness Zielfunktion entwickelt, die mithilfe von Zeilen- und Spaltengenerierung (row and column generation) gelöst werden kann. Durch Anwendung des vorgestellten Verfahrens können für mehrere Instanzen aus der Literatur neue obere und untere Schranken gezeigt werden. Weiterhin wird ein budgetiertes Minimalkostenflussproblem vorgestellt, in dem das Minimalkostenflussproblem, um die Möglichkeit die Kosten auf höchstens K Kanten zu reduzieren, erweitert wird. Es wird gezeigt, dass das Problem NP-vollständig ist und Algorithmen für polynomiell und pseudo-polynomiell lösbare Spezialfälle vorgestellt.