Network flow models for nurse rostering problems

Nurse rostering deals with the task of assigning shifts to nurses subject to various legislative and organisational constraints. It is generally assumed that these problems are hard, whereas, actual proofs supporting such statements are rare. This talk concentrates on simple nurse rostering problems, formulated as minimum cost network flow problems. A class of nurse rostering problems is identified which can thus be solved in polynomial time. In light of these new results, complexity results from the academic literature are revisited, thereby allowing to identify a boundary between easy and hard nurse rostering problems.status: publishe