Nurse Scheduling

Exact and meta-heuristic algorithms for various personnel scheduling problems

Personnel scheduling problems are encountered in many application areas, such as public services, call centers, hospitals, and industry in general. For most of these organizations, the ability to have suitably qualified staff on duty at the right time is of critical importance when attempting to satisfy their customers' requirements and is frequently a large determinant of service organization efficiency. This explains the broad attention given in literature to a great variety of personnel rostering applications. In general, personnel scheduling is the process of constructing occupation timetables for staff to meet a time-dependent demand for different services while encountering specific workplace agreements and attempting to satisfy individual work preferences. The particular characteristics of different industries result in quite diverse rostering models which leads to the application of very different solution techniques to solve these models. Typically, personnel scheduling problems are highly constrained and complex optimization problems. 

The nurse scheduling problem 

The nurse scheduling problem is a well-known scheduling problem which assigns nurses to shifts per day taking both hard and soft constraints into account. The objective is to maximize the preferences of the nurses and to minimize the total penalty cost from violations of the soft constraints. In this research track, we present various novel meta-heuristic techniques based on the principles of Genetic Algorithmic search, Scatter Search principles, Electromagnetism, etc. Below, you can download the NSPLib benchmark instances, best known solutions, a problem generator as well as executables for various meta-heuristic procedures to solve the nurse scheduling problem.
All algorithms report solutions on the proposed benchmark dataset NSPLib generated by NSPGen. The executables, as well as information files, can be downloaded for each meta-heuristic procedure. The solution files can be downloaded from our website, and can be classified in two classes: 
 
Individual solutions: these solutions have been found by the meta-heuristic under a strict stop criterion of 1,000 or 5,000 evaluated solutions. These solutions can be used for comparison purposes with newly develop NSP procedures.
Best known solutions: These solutions are the currently best solutions found so far (no strict stop criterion is implied). We encourage researchers to send their improved best known solutions for the benchmark instances to us.
References:
  • Maenhout, B. and Vanhoucke, M., 2006, "New Computational Results for the Nurse Scheduling Problem: A Scatter Search Algorithm", Lecture Notes in Computer Science, 3906, 158-170.
  • Maenhout, B. and Vanhoucke, M., 2007, "An Electromagnetism meta-heuristic for the nurse scheduling problem", Journal of Heuristics, 13, 359-385.
  • Maenhout, B. and Vanhoucke, M., 2008, "Comparison and Hybridization of Crossover Operators for the Nurse Scheduling problem", Annals of Operations Research, 159, 333-353.
  • Vanhoucke, M., and Maenhout, B., 2007, "NSPLib – A nurse scheduling problem library: a tool to evaluate (meta-)heuristic procedures", in Brailsford, S., and Harper, P., (eds.), Operational Research for Health Policy: Making Better Decisions, Proceedings for the 31st Annual Meeting of the working group on Operations Research Applied to Health Services, 151-165.
  • Vanhoucke, M., and Maenhout, B., 2009, "On the Characterisation and Generation of Nurse Scheduling Problem Instances", European Journal of Operational Research, 196, 457-467.

The nurse rerostering problem 

The personnel scheduler constructs a deterministic personnel roster that determines the line-of-work for each personnel member. When unexpected events disrupt this roster, the feasibility needs to be restored by constructing a new workable roster. The scheduler must reassign the set of employees in order to cover the disrupted shift such that the staffing requirements and the time-related personnel constraints remain satisfied. In the paper "A Genetic Algorithm for the Nurse Rerostering Problem" we developed an evolutionary meta-heuristic to solve the nurse rerostering problem and validated on a new dataset.
 
References:
  • Maenhout, B., and Vanhoucke, M., 2011, "A Genetic Algorithm for the Nurse Rerostering Problem", Computers & Operations Research, 38, 1400-1411

Integrated nurse staffing and scheduling

In this research, we allocate a given workforce over multiple departments based on the hospital's nurse staffing policies, each ward's shift scheduling policies and the nurses' characteristics. The model decides at the staff planning level on the number and which employees each ward should employ. In the paper "An integrated nurse staffing and scheduling approach for longer-term nursing staff allocation problems" we developed an solution methodology to solve this problem and we validated it on a set of generated instances.
 
References:
  • Maenhout, B., and Vanhoucke, M., 2008, "Integrating the Nurse Staffing Decision and the Shift Scheduling Decision: Case Study and Policy Analysis", working paper 08/497, Ghent University