Exact and heuristic approaches for a multi-stage nurse rostering problem

Abstract

Die automatische Erstellung von Schichtplänen für Angestellte in Spitälern und ähnlichen Einrichtungen ist seit Jahrzehnten ein wichtiges Forschungsfeld. Der Bedarf an Arbeitskräften muss für jede Zeitperiode sichergestellt werden, während gleichzeitig gesetzliche und vertragliche Bestimmungen eingehalten und Wüsche der Angestellten berücksichtigt werden müssen. In der für die Second International Nurse Rostering Competition (INRC-II) verwendeten Problemstellung müssen Schichtpläne für mehrere aufeinanderfolgende und untereinander abhängige Zeiträume erstellt werden. In diesem Format sind Informationen über die Anforderungen zukünftiger Planungsperioden erst verfügbar, nachdem der aktuelle Plan fixiert wurde. Das entspricht eher der täglichen Praxis, wie sie in Spitälern zu finden ist, wo sich die Anforderungen innerhalb kurzer Zeiträume ändern können, als die monolithischen Problemstellungen, die in der Literatur üblicherweise behandelt werden. Diese Struktur macht es notwendig, dass Planungsprogramme bereits im Voraus zukünftige Planungsperioden mit unbekannten Anforderungen in ihre Lösungen miteinbeziehen, um Ungleichgewichte und hohe Einbußen bei der globalen Qualität der Lösungen zu vermeiden. In dieser Diplomarbeit wird eine Integer Programming Formulierung des ursprünglichen Problems vorgestellt und dann mittels zusätzlicher Constraints erweitert, die diese speziellen Anforderungen berücksichtigen. Diese Constraints sind so allgemein formuliert, dass sie einfach auch an andere Probleme mit der selben Struktur angepasst werden können. Mithilfe dieser Erweiterungen werden deutliche Verbesserungen in der Qualität der erzeugten Schichtpläne erzielt, ohne dabei die von der INRC-II vorgeschriebenen Zeitlimits zu überschreiten. Außerdem wird ein heuristisches Local Search Framework implementiert, das sich ebenfalls die zusätzlichen Constraints zu Nutze macht, um seine Ergebnisse zu verbessern. Die Resultate beider Methoden werden experimentell ausgewertet und es wird gezeigt, dass sie mit den Ergebnissen der Finalisten der INRC-II vergleichbar sind.

The generation of working schedules for employees in hospitals and similar institutions has been an important field of study for multiple decades. Demand for each time period must be met, while at the same time conforming to various regulations, employment contracts and employee preferences. In the problem variant posed for the Second International Nurse Rostering Competition (INRC-II), solvers need to produce schedules for multiple consecutive and interdependent periods. In this setting, also called a stepping horizon, information about future periods becomes available only after the current schedule has been fixed. This corresponds more closely to the real-word practice found in hospitals, where demand can change within short periods, compared to the monolithic problem formulations usually studied in the literature. The problem structure requires solvers to take future stages with unknown requirements into account during the solution of the current week in order to avoid imbalances and high overall penalties to the quality of the whole schedule. In this thesis, an Integer Programming model of the problem is introduced and then extended with additional constraints that consider the special requirements of this problem, but are general enough to fit also other problems of a similar structure. It is shown that using these extensions, substantial improvements in the quality of the generated schedules can be achieved, while still keeping solution times within the time limits imposed by the competition. Further, a Local Search framework is implemented that also makes use of these additional constraints to improve its solutions. The results of both approaches are experimentally evaluated and compared to each other. They are shown to be competitive with those of the finalists in the INRC-II.