On the characterization and generation of nurse scheduling problem instances
Vanhoucke, Mario Maenhout, Broos
Vanhoucke, Mario
Maenhout, Broos
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2009
Journal
European Journal of Operational Research
Book
Publication Volume
196
Publication Issue
2
Publication Begin page
457
Publication End page
467
Publication NUmber of pages
Collections
Abstract
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.
Research Projects
Organizational Units
Journal Issue
Keywords
Programme & Portfolio Management