An Online Stochastic Algorithm for a Dynamic Nurse Scheduling Problem

International audienceIn this paper, we focus on the problem studied 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 up to eight weeks. We present the work that the authors submitted to this competition and which was awarded the second prize. At each stage, the dynamic algorithm is fed with the staffing demand and nurses preferences for the current week and computes an irrevocable schedule for all nurses without knowledge of future inputs. The challenge is to obtain a feasible and near-optimal schedule at the end of the horizon. The online stochastic algorithm described in this paper draws inspiration from the primal-dual algorithm for online optimization and the sample average approximation, and is built upon an existing static nurse scheduling software. The procedure generates a small set of candidate schedules, rank them according to their performance over a set of test scenarios, and keeps the best one. 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 available in a public repository