Characterisation and generation of nurse scheduling problem instances
Vanhoucke, Mario Maenhout, Broos
Vanhoucke, Mario
Maenhout, Broos
Citations
Altmetric:
Publication Type
Working paper
Editor
Supervisor
Publication Year
2005
Journal
Book
Publication Volume
Publication Issue
29
Publication Begin page
Publication End page
Publication NUmber of pages
41
Collections
Abstract
In this paper, we propose 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, the operations research literature has been overwhelmed by different procedures to solve the problem. The complexity has resulted in the development of several (meta-)heuristic procedures, able to solve a NSP instance heuristically in an acceptable time limit. The practical relevance has resulted in a never-ending amount of different NSP versions, taking practical, case-specific constraints into account. The contribution of this paper is threefold. First, we describe our complexity indicators to characterize a nurse scheduling problem instance. Secondly, we develop a NSP generator to generate benchmark instances to facilitate the evaluation of existing and future research techniques. Finally, we perform some preliminary tests on a simple IP model to illustrate that the proposed indicators can be used as predictors of problem complexity. Keywords: Nurse scheduling, Benchmark instances, Problem classification
Research Projects
Organizational Units
Journal Issue
Keywords
Programme & Portfolio Management, Healthcare Management