A memetic approach to the nurse rostering problem

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this p aper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made eff ective, particularly for obtaining reasonably good solutions quickly for sm aller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvemen t heuristic within a genetic algorithm framework. We provide empirical evid ence to demonstrate the best features of a memetic algorithm for the roster ing problem, particularly the nature of an effective recombination operator , and show that these memetic approaches can handle initialisation paramete rs and a range of instances more robustly than tabu search algorithms, at t he expense of longer solution times. Having presented tabu search and memet ic approaches (both with benefits and drawbacks) we finally present an algo rithm that is a hybrid of both approaches. This technique produces better s olutions than either of the earlier approaches and it is relatively unaffec ted by initialisation and parameter changes, combining some of the best fea tures of each approach to create a hybrid which is greater than the sum of its component algorithms.