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

G-2016-78

An online stochastic algorithm for a dynamic nurse scheduling problem

, et

In this paper, we focus on the problem that has been described in the second international nurse rostering competition: a personalized nurse scheduling problem under uncertainty. The schedules must be computed week by week over a planning horizon of one or two months depending on the instances. We present the work that was submitted to this competition and which was awarded the second prize. At each week, a dynamic algorithm is fed with the staffing demand and nurse preferences for the week, and it computes an irrevocable weekly schedule for all nurses without knowledge on future inputs. The challenge is to obtain a feasible and near-optimal schedule at the end of the horizon. The proposed online stochastic algorithm draws inspiration from the primal-dual algorithm for online optimization and the sample average approximation, and it builds upon an existing static nurse scheduling software. The procedure generates a small set of candidate schedules, evaluates each of them on few scenarios, and keeps the one with the best evaluation. Numerical results show that this algorithm is very robust, since it has been able to produce feasible and near optimal solutions on most of the proposed instances ranging from 30 to 120 nurses over a horizon of 4 or 8 weeks. Finally, the code of our implementation is open source and shared on a public repository.

, 22 pages