A Nurse Rostering Algorithm with Compile-Time Customisation and Neighbourhood-Constrained Column Generation

Abstract

The issue of generating automated staff rosters has received a great deal of academic interest of late, and has also led to several timetabling competitions, most notably the First International Nurse Rostering Competition (INRC2010) which was held earlier this year (Haspeslagh et al. 2010). The work detailed in this thesis focuses on customising GENIE++ (Dohn, Mason, and Ryan 2010), an existing staff rostering framework, to suit the model proposed by the INRC2010 specification. A C++ project, the Input File Generator, is created to automate this customisation process for problem instances of the competition formulation. A number of problem instances are provided as part of the competition, which are used to benchmark the performance of the customised GENIE++ framework. We observe some positive initial results, but motivation is established to implement heuristic methodologies within GENIE++ in order to generate optimal or near-optimal solutions relatively quickly. With this goal in mind, a near-steepest descent local search heuristic is developed and implemented within the GENIE++ framework. This heuristic provides some very encouraging results and performs competitively on the more complicated problem instances.