On the Complexity of Nurse Scheduling Problems

Abstract

The Nurse Scheduling Problem is a specific rostering problem for situations that need 24-hour coverage. There is a wide variety of constraints, and while some combinations have been proven NP-complete in the past, there is still a large number of problems that remain unclassified. We have defined a number of constraints for a version of the Nurse Scheduling Problem that are common in literature and are able to model a wide variety of problems. For most combinations of these constraints we have shown whether the problem is NP-complete or whether it is polynomially solvable.