NSPLib - a nurse scheduling problem library: a tool to evaluate (meta-)heuristic procedures. In this paper, we propose a large set of data instances based on different complexity indicators for the well-known nurse scheduling problem (NSP). The NSP assigns nurses to shifts per day taking both hard and soft constraints into account. The objective is to maximize the nurses’ preferences and to minimize the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. Due to its complexity and relevance in practice, many researchers have developed (meta-)heuristic procedures to solve a NSP instance heuristically in an acceptable time limit. However, these solution procedures are often very case-specific towards one hospital and hence, cannot be compared with each other. Moreover, lack of data and the many interpretations of how to evaluate solution procedures have contributed to the never-ending amount of newly developed procedures without any effort to benchmark them in literature. The contribution of this paper is threefold. First, we propose a large set of benchmark instances for the nurse scheduling problem in order to facilitate the evaluation of existing and future research techniques. Secondly, we propose a computer platform independent stop criterion to evaluate and compare meta-heuristic procedures for the NSP. Finally, we propose a newly developed website where the benchmark instances can be downloaded and where the best known solutions can be uploaded.
Keywords for this software
References in zbMATH (referenced in 7 articles )
Showing results 1 to 7 of 7.
- Constantino, Ademir Aparecido; Landa-Silva, Dario; De Melo, Everton Luiz; De Mendonça, Candido Ferreira Xavier; Rizzato, Douglas Baroni; Romão, Wesley: A heuristic algorithm based on multi-assignment procedures for nurse scheduling (2014)
- Smet, Pieter; Bilgin, Burak; De Causmaecker, Patrick; Vanden Berghe, Greet: Modelling and evaluation issues in nurse rostering (2014)
- Ansótegui, Carlos; Bofill, Miquel; Palahí, Miquel; Suy, Josep; Villaret, Mateu: Solving weighted CSPs with meta-constraints by reformulation into satisfiability modulo theories (2013)
- De Causmaecker, Patrick; Vanden Berghe, Greet: A categorisation of nurse rostering problems (2011)
- Maenhout, Broos; Vanhoucke, Mario: Branching strategies in a branch-and-price approach for a multiple objective nurse scheduling problem (2010)
- Vanhoucke, Mario; Maenhout, Broos: On the characterization and generation of nurse scheduling problem instances (2009)
- Maenhout, Broos; Vanhoucke, Mario: Comparison and hybridization of crossover operators for the nurse scheduling problem (2008)