Log In

On the complexity of Nurse Rostering problems

Files

How and where to find an Open Access version of this publication?

Publication date

2023-09

Authors

den Hartog, Steven J. M.
Hoogeveen, J.A.ISNI 0000000352147824
van der Zanden, Tom C.ISNI 0000000493301143

Editors

Advisors

Supervisors

DOI

https://doi.org/10.1016/j.orl.2023.07.004

Document Type

Article

Metadata

Show full item record

Collections

Utrecht University Repository

License

Abstract

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.

Keywords

Complexity, NP-completeness, Nurse scheduling, Scheduling

Citation

den Hartog, S J M, Hoogeveen, H & van der Zanden, T C 2023, 'On the complexity of Nurse Rostering problems', Operations Research Letters, vol. 51, no. 5, pp. 483-487. https://doi.org/10.1016/j.orl.2023.07.004

URI

https://dspace.library.uu.nl/handle/1874/432247