On the complexity of Nurse Rostering problems

In Nurse Rostering problems the goal is to assign nurses to shifts, subject to a number of constraints. In this paper we consider the computational complexity of such problems. We review the major complexity results obtained so far and show that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even if there are only three work shifts and a day off shift involved. & COPY; 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Automated summary

This paper investigates the computational complexity of Nurse Rostering problems and shows that a problem with coverage constraints, day off requests, and forbidden sequences of shifts of length 2 is NP-hard in the strong sense, even for a small number of work shifts and a day off shift.