Variable neighborhood search for nurse rostering problems
Metaheuristics: Computer Decision-Making
Burke, E. D. C., P; Petrovic, S; Vanden Berghe, G. (2004). Variable neighborhood search for nurse rostering problems. [Book Chapter]. Metaheuristics: Computer Decision-Making, 153-172.
Nurse rostering problems consist of assigning varying tasks, represented; as shift types, to hospital personnel with different skills and work regulations. The; goal is to satisfy as many soft constraints and personal preferences as possible while; constructing a schedule which meets the required personnel coverage of the hospital; over a predefined planning period. Real-world situations are often so constrained that; finding a good quality solution requires advanced heuristics to keep the calculation; time down.; In this paper, we present a variable neighbourhood search approach for the nurse; rostering problem. It takes the broad variety of constraints into consideration and; succeeds better in escaping from local optima than other previously tested metaheuristics.; Hidden parts of the solution space become accessible by applying appropriate; problem specific neighbourhoods. The method allows for a better exploration; of the search space, by combining shortsighted neighbourhoods, and very greedy; ones. Experiments demonstrate how heuristics and neighbourhoods can be assembled; for finding good quality schedules in a short calculation time.; We modelled Belgian nurse rostering problems, that appear to be among the most; complex in the world. However, the nurse rostering search algorithms discussed in; this paper are not aimed at specific hospitals. On the contrary, the intention is that; such algorithms should be applicable across the whole sector.