A stepping horizon view on nurse rostering

The present paper introduces a stepping horizon approach to opti- misation problems for which the data can be considered static within a lim- ited time horizon. The idea is that instances of a problem need to be solved at certain moments in time, thereby imposing constraints on the subsequent period's instance. Nurse rostering can be identied as an optimisation prob- lem for which a stepping horizon approach is recommended whereas a static approach is suitable for academic algorithm development objectives. In order to support this claim, the paper focuses on the sprint instances from the 2010 Nurse Rostering Competition. These instances represent a su- ciently realistic set of constraints while still being solvable to optimality with a general purpose solver. Two dierent sets of experiments are presented. First, it is shown that a static horizon approach risks to generate unbalanced rosters regarding some counter constraints. A second set of experiments points at the benets of a stepping horizon approach with respect to constraints of the se- ries type. In both experimental setups, lower bounds are computed for rosters spanning more than one time horizon. The stepping horizon approach yields rosters that violate fewer constraints than those obtained in a static setting.status: publishe