A hybrid approach for solving real-world nurse rostering problems

Nurse rostering is the process of creating a plan for nurse working hours over a given time horizon. This problem, most variants of which are NP-hard, has been studied extensively for many years. Still, practical nurse rostering is mostly done manually, often by highly qualified health care personnel. This underlines the need to address the challenges of realistic, applied nurse rostering, and the implementation of advanced rostering methods in commercial software. In this paper, we present an industrial case study of a nurse rostering software currently used in several hospitals and other health care institutions in Norway and Sweden. The presented problem model has a rich set of hard and soft constraints, as required by Norwegian hospitals. Our solution approach is a hybrid: An {Iterated Local Search} framework that uses {Constraint Programming} for initial solution construction and diversification, and a {Variable Neighborhood Descent} for iterative improvement. The search method shows good results in terms of solution quality and computation time on a set of real world instances. We make these test instances available on-line.