Plant propagation algorithm for nurse rostering

摘要

This paper investigates the nurse rostering problem (NRP), a challenging combinatorial optimisation problem that arises in healthcare institutions. We propose to solve it by using the plant propagation algorithm (PPA). As many successful metaheuristics, PPA is inspired by a life process. It emulates the strategy of reproduction and propagation of the strawberry plant. Before applying PPA, a variable -fixing procedure is used for heuristically discarding variables. In practice, it results in removing up to 99% of the variables without sacrificing solution quality. Elite solutions provided by PPA are used to further discard variables, leaving a very sparse NRP that can be solved directly by an IP solver. Computational and comparative results are presented on a widely used set of benchmark instances.