<  Retour au portail Polytechnique Montréal

Optimisation stochastique d'horaires de personnel

Rémi Pacqueau

Mémoire de maîtrise (2011)

Document en libre accès dans PolyPublie
[img]
Affichage préliminaire
Libre accès au plein texte de ce document
Conditions d'utilisation: Tous droits réservés
Télécharger (3MB)
Afficher le résumé
Cacher le résumé

Résumé

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.

Abstract

There are different steps in workforce planning where operations research can be helpful : building days in/off schedules, building work shifts, and allocating shifts and tasks to employees. When the employee demand is not known precisely in advance, those steps have to be done at different moments : building days in/off schedules several months in advance with a draft forecast demand, building shifts several weeks in advance with a more precise but still forecast demand, and finally allocating shifts and taking a “recourse” (hiring part-time employees, asking some employees to do over-time, building the pause schedule) on “D-day”, once the exact demand is known. In this master's thesis we study a different way of building shifts. Instead of making the shift construction based only on a forecast demand, we use the complete probability distribution of the demand. Thus, the goal becomes to minimize the expected value of the total cost, i.e. the cost of the regular shifts and the cost of the recourse. By increasing the problem's size, we compute a better solution than the one we would have using the classical, deterministic method. After having formulated the problem, we develop a heuristic based on a well-known stochastic programming algorithm : the L-shaped method. Our heuristic turns out to be very efficient : optimality losses are small, and the computational times are reasonable : most of the time less than 15 minutes for a 500-scenario problem (10 million variables), where CPLEX takes a little less than 5 hours only to solve the linear relaxation of the problem. We then study on different data sets the savings we manage to get compared to a deterministic approach. In cases where the variance of the demand is reasonable, savings from 1 to 2 % of the overall cost can be obtained. When the variance is small, no significant savings can be expected. For cases with important variances, savings can be up to 15 %. We conclude that our approach is worth of interest, but that savings dramatically depend on the kind of employee demand we are dealing with.

Département: Département de mathématiques et de génie industriel
Programme: Mathématiques appliquées
Directeurs ou directrices: François Soumis
URL de PolyPublie: https://publications.polymtl.ca/595/
Université/École: École Polytechnique de Montréal
Date du dépôt: 25 oct. 2011 10:08
Dernière modification: 08 nov. 2022 18:07
Citer en APA 7: Pacqueau, R. (2011). Optimisation stochastique d'horaires de personnel [Mémoire de maîtrise, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/595/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel

Afficher document Afficher document