Planification d’horaires d’infirmières sous incertitudes par échantillonnage et génération de colonnes

Session : GC / Génération de colonnes
Vendredi 12 février 10:30 - 11:50 Salle : CI2-07
Jérémy Omer, Samuel Rosat et Antoine Legrain

Nous nous intéressons au problème de planification d'horaires d'infirmières sous incertitudes décrit dans le cadre de la compétition internationale INRC2 (http://mobiz.vives.be/inrc2/). Le problème consiste à déterminer les horaires d'un ensemble d'infirmières sur un horizon de quatre à huit semaine afin de satisfaire une demande donnée pour chaque quart de travail en minimisant les écarts aux contraintes reflétant les contrats de travail et les préférences des infirmières. Le problème est stochastique, car la demande n'est connue qu'au début de la semaine en cours. Ainsi, les horaires de chaque semaine doivent être déterminés séquentiellement sans information sur les demandes futures. Dans cette présentation, nous décrivons un algorithme gérant l'aspect stochastique selon une phase de génération et une phase d'évaluation. Ainsi, des scénarios créés aléatoirement par perturbation des demandes connues permettent de produire plusieurs horaires robustes et l'évaluation sur d'autres scénarios aléatoires permet de retenir le meilleur candidat. Tous les modèles intervenant dans cette procédure sont résolus par une méthode de génération de colonnes dans laquelle des successions de jours travaillés sont itérativement produits. Cet algorithme nous a permis d'être classés seconds avec un classement moyen de 1.86 (contre 1.76 pour le premier) sur un ensemble de 60 instances inconnues avant la soumission de notre code.

Mots clés : génération de colonnes, échantillonnage, planification, primal-dual, simulation