On the characterization and generation of nurse scheduling problem instances

Due to its complexity and relevance in practice, many different procedures have been proposed in the operations research literature to solve the well-known nurse scheduling problem (NSP). The NSP assigns nurses to shifts per day maximizing the overall quality of the roster while taking various constraints into account. The often highly case-specific workplace conditions in hospital departments have resulted in the development of dedicated (meta-)heuristics to find a workable schedule in an acceptable time limit. However, in spite of research community posing a growing need for benchmarking, these procedures lack any base for comparison. In this paper, we propose a range of complexity indicators which characterize nurse scheduling problem instances, and a problem generator in order to construct a comparative test framework for various solution procedures for the NSP. We show that the different complexity indicators for the NSP presented in this paper predict the computational effort of a particular NSP instance for a particular solution procedure. Moreover, the comparison of procedures and good predictions of their performance allow the a priori selection of the best solution procedure, based on the simple calculation of the indicators. Hence, with the developed NSP generator those indicators can facilitate the evaluation of existing and future research techniques. Tests on a simple IP model illustrate the use of the proposed indicators.