Authors: Salim Haddadi
Addresses: LabSTIC, 8 Mai 1945 University, P.O. Box 401, 24000 Guelma, Algeria
Abstract: 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.
Keywords: bio-inspired computation; plant-inspired algorithm; plant propagation algorithm; PPA; nurse rostering; elite solutions; variable-fixing.
International Journal of Innovative Computing and Applications, 2020 Vol.11 No.4, pp.204 - 215
Received: 29 Nov 2019
Accepted: 22 Jan 2020
Published online: 16 Nov 2020 *