Groupe d’études et de recherche en analyse des décisions

Nurse scheduling problem with soft constraints

Antoine Legrain Professeur adjoint, Département de mathématiques et de génie industriel, Polytechnique Montréal, Canada

Antoine Legrain

Présentation sur 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.