<  Back to the Polytechnique Montréal portal

Optimisation stochastique d’horaires de personnel

Rémi Pacqueau

Masters thesis (2011)

[img]
Preview
Download (3MB)
Cite this document: Pacqueau, R. (2011). Optimisation stochastique d’horaires de personnel (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/595/
Show abstract Hide abstract

Abstract

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.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: François Soumis
Date Deposited: 25 Oct 2011 10:08
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/595/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only