A Pareto-based search methodology for multi-objective nurse scheduling

Citation

Burke E, Li J & Qu R (2012) A Pareto-based search methodology for multi-objective nurse scheduling. Annals of Operations Research, 196 (1), pp. 91-109. https://doi.org/10.1007/s10479-009-0590-8

Abstract
In this paper, we propose a search technique for nurse scheduling, which deals with it as a multi-objective problem. For each nurse, we first randomly generate a set of legal shift patterns which satisfy all shift-related hard constraints. We then employ an adaptive heuristic to quickly find a solution with the least number of violations on the coverage-related hard constraint by assigning one of the available shift patterns of each nurse. Next, we apply a coverage repairing procedure to make the resulting solution feasible, by adding/removing any under-covered/over-covered shifts. Finally, to satisfy the soft constraints (or preferences), we present a simulated annealing based search method with the following two options: one with a weighted-sum evaluation function which encourages moves towards users' predefined preferences, and another one with a domination-based evaluation function which encourages moves towards a more diversified approximated Pareto set. Computational results demonstrate that the proposed technique is applicable to modern hospital environments.

Keywords
Multi-objective optimization; Integer programming; Meta-heuristic search; Nurse scheduling

Journal
Annals of Operations Research: Volume 196, Issue 1