Nurse rostering: models and algorithms for theory, practice and integration with other problems

Nurse rostering is a personnel scheduling problem in health care in which shifts are assigned to nurses, subject to a large variety of constraints regarding personal preferences, organisational guidelines, and labour legislation. The present dissertation discusses models and algorithms for nurse rostering, treating three aspects: theory, practice and integration with other problems. This research contributes significantly to scientific, social and industrial aspects in the state of the art of nurse rostering. By studying simplified nurse rostering problems, a basic understanding of the problem's complexity is established. These new insights identify a boundary between easy and hard problems, which strongly influences computational search approaches to the problem. Furthermore, issues regarding consistent constraint evaluation for long term rostering are exposed, and policies to address these issues are proposed. Computational experiments illustrate the importance of a consistent evaluation procedure and are employed to evaluate the presented policies. Despite the many academic contributions, few results find their way intonbsp;The present dissertation therefore attempts to bridge this gap by offering two contributions that aim at facilitating the implementation of academic results. First, a general model for nurse rostering problems is introduced, which is capable of representing a large variety of personal, organisational and legislative constraints. Second, an approach is introduced to automatically order constraints according to their priority extracted from historical data. For practitioners, this is a complex and unintuitive task, which nevertheless strongly influences the outcome of any algorithm for nurse rostering. These two contributions are currently implemented in a commercial software package for personnel rostering, used in hospitals and other organisations in Europe. Finally, the scope of decision making is extended to include characteristics of related hard combinatorial optimisation problems.nbsp;focus lies on solving three different integrated task scheduling and personnel rostering problems: assigning tasks when shifts are predetermined and cannot be changed, assigning both tasks and shifts for a single isolated day, and assigning tasks and shifts for a longer scheduling period. Optimal and approximating decomposition algorithms are proposed which combine exact techniques and heuristic search. Computational experiments illustrate the effectiveness and versatility of the proposed approaches on a large variety of benchmark instances.status: publishe