Méthodes heuristiques de planification et de ré-optimisation en temps réel pour les problèmes d’horaires de personnel

RESUME: Les problemes d’horaires de personnel visent a determiner les horaires de travail les moins couteux pour couvrir la demande d’une ou de plusieurs tâches a chaque periode d’un horizon donne. Ces problemes font de plus en plus l’objet d’etudes traitees par la recherche operationnelle. Cela est du, d’une part, aux besoins economiques, qui revelent jour apres jour de nouveaux defis, et, d’autre part, a la complexite qui caracterise de tels problemes. Parmi les grands defis, on retrouve la gestion de l’incertitude en temps reel. En effet, durant l’operation, plusieurs perturbations, difficilement controlables, peuvent survenir a tout moment, comme les retards des employes, la variation de la demande, etc. Ces perturbations doivent etre traitees intelligemment et tres rapidement par la mise a jour des horaires de certains employes. Dans cette these, on s’interesse principalement a cette problematique dans un contexte tres peu aborde dans la litterature, a savoir la vente au detail, ou les employes peuvent etre affectes a une grande variete de quarts de travail selon leurs qualifications et leurs disponibilites. Nous proposons, en premier lieu, une methode de re-optimisation en temps reel qui se base principalement sur l’information duale, trouvee lors de l’optimisation initiale, et sur un ensemble de types de decision recommandes par notre partenaire industriel. La methode determine, pour chaque type de decision, la meilleure adaptation de l’horaire en estimant un cout ajoute pour chaque adaptation candidate. Les adaptations concernent seulement le jour ou la perturbation a eu lieu et visent a palier la perturbation tout en gardant une solution globale quasi-optimale. Nous proposons egalement une procedure, exploitant une methode de regression, pour mettre a jour les valeurs duales apres la correction de chaque perturbation lorsque plusieurs d’entre elles surviennent durant l’horizon. Les tests menes sur un ensemble contenant 1050 instances de problemes reels allant jusqu’a 191 employes ont montre l’efficacite de la methode proposee. Celle-ci arrive a trouver la solution optimale pour plus de 95% de ces instances, et ce, en une seconde en moyenne. En second lieu, nous proposons une methode de re-optimisation en temps reel plus generale que la premiere : elle ne requiert pas l’information duale et ne se restreint pas seulement au jour ou la perturbation a eu lieu, mais s’applique egalement au reste de l’horizon. La methode cherche des adaptations qui permettent de corriger la perturbation sans trop s’eloigner de l’horaire planifie en termes du nombre de modifications engendrees par ces adaptations. Le cout ajoute du a ces modifications doit etre le moins eleve possible. A l’aide de certaines decisions de base qui permettent de generer tous les horaires possibles, la methode cherche les bonnes sequences, appelees politiques, qui conduisent a des solutions de bonne qualite, appelees solutions non-dominees, obtenues apres une optimisation multi-objectif. La methode fait appel a un reseau qui schematise une region prometteuse de l’enveloppe convexe des solutions realisables. La construction du reseau se fait d’une maniere dynamique au cours de la resolution en se basant sur quelques resultats theoriques. Les tests menes sur des instances derivees de donnees reelles impliquant jusqu’a 95 employes demontrent l’efficacite de l’heuristique. En moins d’une seconde en moyenne, elle peut calculer des solutions Paretooptimales pour plus de 98% des scenarios testes. L’efficacite et la rapidite de cette derniere methode de re-optimisation nous a pousse a etre plus ambitieux pour l’adapter afin de faire une optimisation globale. Ceci a abouti a la naissance d’une nouvelle approche integree, qui genere et affecte les quarts simultanement et qui vise a optimiser un probleme d’horaires de personnel. L’approche se base sur la stimulation/ correction iterative d’un ensemble de perturbations bien ciblees selon certaines mesures probabilistes. Ces dernieres indiquent la probabilite que la correction de chacune de ces perturbations ameliore significativement la solution courante. Deux procedures de groupage sont utilisees afin de generer un ensemble de sous-problemes qui seront traites parallelement. Chacun de ces sous-problemes represente un terrain riche de perturbations visees pour les stimuler, ce qui rend la recherche plus efficace et rapide. Pour chaque sous-probleme, nous stimulons une perturbation qui nous mene, generalement, a l’espace irrealisable. Ainsi, nous definissons un voisinage de recherche, sur ce sous-probleme, afin de trouver une politique qui nous mene a l’espace realisable. Nous combinons a chaque iteration, de facon optimale, toutes les politiques qui sont compatibles (i.e., leur combinaison produit une solution realisable) parmi celles trouvees parallelement dans les sous-problemes consideres afin de passer a une solution meilleure. L’heuristique proposee a ete testee sur des instances reelles du probleme impliquant jusqu’a 94 employes et 10 tâches. Notre methode a alors permis de trouver des solutions de bonne qualite en moins de 2 minutes, en moyenne, dans 97% des cas de test.----------ABSTRACT: Personnel scheduling aims at determining the cheapest work schedules to cover the demand for one or more tasks at each period of a given horizon. These problems are increasingly addressed in operations research. This is due, on the one hand, to the economic needs that reveal day by day new challenges, and on the other, the complexity that characterizes such problems. One of the biggest challenges is to manage uncertainty in real time. In fact, during the operation, several disruptions, difficult to control, can occur at any time such as employee delays, demand variation, etc. These disruptions must be handled intelligently and quickly by updating the schedules of certain employees. In this thesis, we are mainly interested in personnel scheduling in a context that is not tackled much in the literature where employees can be assigned to a large variety of shifts depending on their qualifications and availability. Firstly, we propose a real-time re-scheduling method based on the dual information found during the initial optimization and on a set of decision types provided by our industrial partner. This method determines for each type of decision the best adaptation of the schedule by estimating an additional cost for each possible adaptation. The adaptations are intended to cover the disruption, that occurs during the day, and to keep a quasi-optimal solution. We also propose a procedure using a regression method to update the dual values after the correction of each disruption when several of them occur during the horizon. Computational experiments conducted on a set of 1050 instances derived from real-life datasets involving up to 191 employees show the efficiency of the proposed re-scheduling heuristic: it can compute optimal solutions for more than 95% of these instances in less than one second on average. Secondly, we propose a real-time re-scheduling method which is more general than the first one. It does not require the dual information and is not limited to the day when the disruption takes place but covers all the rest of the horizon. The method looks for adaptations that enable to correct the disruption without deviating too much from the planned schedule in terms of the number of modifications caused by these adaptations. The additional cost caused by these changes must be as low as possible. Using some basic decisions that can generate all possible schedules, our method aims to find the right sequences, called policies, that lead to non-dominated solutions, obtained after a multi-objective optimization. The method uses a network that schematizes a promising region of the convex hull of the set of feasible solutions. The network’s construction is done dynamically during the solution process based on some theoretical results. Computational experiments conducted on a set of instances derived from real-life datasets involving up to 95 employees showed the usefulness of the fundamental study as well as the efficiency of the proposed heuristic. It can find all the exact solutions that achieve a good compromise cost/modifications, in a search zone set by the employer, in less than one second on average for more than 97% of the scenarios generated. The efficiency and the speed of the last re-scheduling method encouraged us to integrate it into a global optimization algorithm. As a result, a new integrated approach has been developed which generates and assigns shifts simultaneously and optimizes the personnel scheduling problem. The approach is based on the iterative stimulation/correction of a set of well-targeted disruptions according to certain probabilistic measures. These indicate the probability that the correction of each of these disruptions significantly improves the current solution. Two clustering procedures are used to generate a set of subproblems that are processed in parallel. Each of these subproblems represents a rich area of disruptions intended to stimulate them and what makes the search more efficient and faster. For each subproblem, we stimulate a disruption that generally leads us to the infeasible region. So, we define a search neighborhood in order to find a policy that leads to the feasible region. At each iteration we combine all policies that are compatible (i.e. their combination leads to a feasible solution) among those found in parallel by the subproblems. The proposed heuristic has been tested on real instances of the problem involving up to 94 employees and 10 tasks. The method then made it possible to find good quality solutions in less than 2 minutes, on average, in 97% of the test cases.