Group for Research in Decision Analysis

Nurse scheduling problem with soft constraints

Antoine Legrain Assistant Professor, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Canada

Antoine Legrain

Presentation on YouTube

The Nurse scheduling problem is recognized to be very challenging as it must generally propose a personalized schedule for every nurse. The talk will focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition (INRC-II). One specificity of this version is that most constraints are soft, meaning that they can be violated at the price of a penalty. Classical branch-and-price algorithms underperform with soft constraints in the subproblems as they generally solve a classical resource-constrained shortest-path. In this talk, I will present a different approach to implement more aggressive domination functions for soft constraints. This new method allows solving efficiently at optimality many instances from the INRC-II involving up to 120 nurses and 4 shifts over a 4 to 8-weeks horizon. Different models and features will be presented, and many computational results will compare the different approaches.