Titre : Solving the stochastic nurse rosering problem by sampling and column generation

Speaker: Jérémy Omer – INSA Rennes , France 

We consider the nurse rostering problem under uncertainties on demands, as described in the international competition INRC2. It consists in determining the weekly schedules of a set of nurses with different skills over a four to eight weeks horizon. The schedules must satisfy minimum demands on the four shifts of each day while minimizing the gap with work rules and nurses' preferences. The problem  is stochastic, because the demand is known only at the beginning of the current week. Therefore, the weekly schedules must be computed sequentially without information on future demands. The first part of the presentation will focus on the deterministic case, which we solve using a column generation approach coupled with a large neighborhood search. We will then see how we manage uncertainties in two phases corresponding to the generation and evaluation of scenarios. In the first phase, several scenarios are randomly generated by introducing perturbations in past demands. Several weekly schedules are then computed by considering different scenarios of future demands. The best candidate solution is then identified by evaluating these solutions on a new set of scenarios. Fifteen academic and industrial teams submitted a functional code to the competition. The algorithms of the seven finalists were compared on 60 instances unknown before submission. On each instance, a grade from 1 to 7 was assigned to each team according to the results of their algorithms (1 for the best, 7 for the worst). Our algorithm ranked second with an average 1.86 grade against 1.76 for the winner.

---

Free entrance.
Welcome to everyone!