On the characterization and generation of nurse scheduling problem instances

Mario Vanhoucke and Broos Maenhout

European Journal of Operational Research, 2009, vol. 196, issue 2, 457-467

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.

Keywords: Nurse; scheduling; Problem; characterization (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00345-7
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:196:y:2009:i:2:p:457-467

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().