NSPLib: a Nurse Scheduling Problem Library: a tool to evaluate (meta-)heuristic procedures

In this paper, we propose a large set of problem 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 overall quality of the nurse roster by taking nurses' preferences and the penalty costs of violating the soft constraints into account. 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 published effort to benchmark them. 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