Exact and heuristic approaches to nurse scheduling

By Jonas Bæklund
PhD Dissertations
October 2013

This thesis addresses the nurse scheduling problem of finding a duty roster for a set of nurses such that the rosters comply with work regulations and meet the management’s requests. This problem is usually referred to as nurse rostering. For today’s hospitals, personal in general but in particular nurses are becoming more and more a scarce and expensive resource. Accordingly, a careful nurse scheduling that at the same time matches economic needs as well as nurses’ preferences is of increasing importance.

The nurse rostering problem is a complex combinatorial optimisation problem and generally very difficult so solve. No general model describes all nurse rostering problems, because there are so many differences between the specific problems encountered at the different wards around the world. The problem confronted in this thesis is from a ward at Aarhus University Hospital Skejby in Denmark. However, the solution methods proposed are general enough, so the methods would probably generalise to other wards in Denmark.

A branch-and-price method for solving the problem exactly is proposed. The master problem is to assign schedules to the nurses, and its linear relaxation is solved by means of column generation. The pricing sub-problem is to generate feasible schedules for the nurses and is solved by constraint programming. A number of specific algorithms for handling the constraints in the sub-problems are proposed. Computational tests show that optimal solutions can be found for instances with a two weeks planning period in a reasonable amount of computing time.

For instances with a longer planning period, two heuristics are proposed. The methods are a variable neighbourhood search and a scatter search. Both methods use the exact branch-and-price method as a sub-routine for performing the search in the heuristics. The experimental results shows that the scatter search outperforms the variable neighbourhood search when more than an hour of computation time is allocated. The scatter search seems to find solutions of high quality, and it generally returns a set of high quality solutions. A set of high quality solutions – instead of just a single solution – is from a practical point of view a valuable feature.

Thesis advisor: Andreas Klose
Format available: PDF (959.1 kb)