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.
