Algorithmic and practical aspects of appointment scheduling

Roth, Sarah Katharina; Koster, Arie Marinus; Lübbecke, Marco

doi:10.18154/RWTH-2021-01724

Algorithmic and practical aspects of appointment scheduling

Roth, Sarah Katharina^RWTH*

2020 & 2021

Verantwortlichkeitsangabevorgelegt von Diplom-Mathematikerin Sarah Katharina Roth, geb. Kirchner

ImpressumAachen : RWTH Aachen University 2020

Umfang1 Online-Ressource (x, 119 Seiten) : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2020

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2021

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Lübbecke, Marco (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2020-05-06

Online
DOI: 10.18154/RWTH-2021-01724
URL: https://publications.rwth-aachen.de/record/812189/files/812189.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
appointment scheduling (frei) ; budgeted minimum cost flow (frei) ; jobshop scheduling (frei) ; row and column generation (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

This thesis is motivated by the Appointment Scheduling Problem as is appears in hospitals. The problem consists of a set of patients. Each patient needs appointments for several treatments that need to be processed in a predefined order. Each appointment itself can be processed by any resource out of a set of possible resources. Special requirements are considered when scheduling inpatients compared to outpatients. A time-indexed integer programming formulation for this problem is introduced. To cope with large time horizons a nested time aggregation scheme is proposed. The integer programming approach is supplemented with (online) heuristics to cope with the dynamic environment and special requirements for outpatients. Simple proactive and reactive approaches are proposed to handle uncertain processing times. The approach is tested using a discrete event simulation. The Appointment Scheduling Problem is a special case of the well studied Jobshop Scheduling Problem, where patients correspond to jobs and appointments correspond to operations of a job. In this thesis a row-and-column generation approach along with problem specific branching rules and cutting planes is proposed to solve the Jobshop Scheduling Problem with earliness/tardiness objective function. Using this approach several improved lower- and upper bounds for benchmark instances from literature are presented. Furthermore, the budgeted minimum cost flow problem with unit upgrading costs is discussed. The problem extends the classical minimum cost flow problem by allowing one to reduce the cost of at most K arcs. The NP-completeness of the problem is proved and algorithms for polynomial and pseudo-polynomial special cases are presented.

OpenAccess:
PDF
(additional files)