Optimisation stochastique d'horaires de personnel

La recherche opérationnelle peut intervenir à différentes phases de l'optimisation d'horaires : construction des jours de travail et de repos, construction des quarts de travail, allocation des quarts et des tâches aux employés. Lorsque l'information sur la demande en employés est imparfaite, on effectue ces étapes en différé : construction des jours de travail et de repos avec une demande très grossière quelques mois à l'avance, construction des quarts quelques semaines à l'avance avec une demande prévisionnelle plus fine, allocation des quarts et « recours » (c'est-à-dire emploi de temps partiels, modification des pauses et heures supplémentaires) le jour « J », une fois que l'on dispose de la demande précise. Dans cette maîtrise, nous nous intéressons à une méthode différente de construction des quarts. Au lieu de prendre en compte seulement une demande prévisionnelle, on prendra en compte dans l'optimisation la distribution de cette demande aléatoire. L'objectif sera alors de minimiser l'espérance du coût total, i.e. du coût des quarts réguliers et du recours. Au prix d'un alourdissement du problème, on arrivera à une solution meilleure en pratique. Après avoir formulé le problème, nous développons une heuristique basée sur une méthode célèbre en programmation stochastique : la méthode L-shaped. Notre heuristique est efficace : les pertes d'optimalité sont faibles, et le temps de résolution est raisonnable : moins de 15 minutes en général pour 500 scénarios (10 millions de variables), à comparer aux presque 5 heures nécessaires à CPLEX pour résoudre simplement la relaxation linéaire du problème. Nous étudions alors sur différents jeux de données le gain apporté par cette approche stochastique par rapport à l'approche déterministe. Nous constatons que, dans les cas où la variance des jeux de données est raisonnable, les gains sont de 1 à 2 % du coût total. Lorsque la variance est faible, aucun gain n'est à constater. Pour des cas de très grande variance, le gain peut aller jusqu'à 15%. Nous en concluons que notre approche présente un intérêt certain, mais que ce dernier dépend grandement du type de demande en employés présentée.