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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2020

Abstract

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.

Institutions

• Department of Mathematics [110000]
• Discrete Optimization Teaching and Research Unit [113320]
• Chair of Operations Research [813310]