Journal
OPERATIONS RESEARCH LETTERS
Volume 51, Issue 5, Pages 483-487Publisher
ELSEVIER
DOI: 10.1016/j.orl.2023.07.004
Keywords
Scheduling; Complexity; NP-completeness; Nurse scheduling
Categories
Ask authors/readers for more resources
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.
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/).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available