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

Les problèmes d'horaires de personnel visent à déterminer les horaires de travail les moins coûteux pour couvrir la demande d'une ou de plusieurs tâches à chaque période d'un horizon donné. Ces problèmes font de plus en plus l'objet d'études traitées par la recherche opérationnelle. Cela est dû, d'une part, aux besoins économiques, qui révèlent jour après jour de nouveaux défis, et, d'autre part, à la complexité qui caractérise de tels problèmes. Parmi les grands défis, on retrouve la gestion de l'incertitude en temps réel. En effet, durant l'opération, plusieurs perturbations, difficilement contrôlables, peuvent survenir à tout moment, comme les retards des employés, la variation de la demande, etc. Ces perturbations doivent être traitées intelligemment et très rapidement par la mise à jour des horaires de certains employés. Dans cette thèse, on s'intéresse principalement à cette problématique dans un contexte très peu abordé dans la littérature, à savoir la vente au détail, où les employés peuvent être affectés à une grande variété de quarts de travail selon leurs qualifications et leurs disponibilités. Nous proposons, en premier lieu, une méthode de ré-optimisation en temps réel qui se base principalement sur l'information duale, trouvée lors de l'optimisation initiale, et sur un ensemble de types de décision recommandés par notre partenaire industriel. La méthode détermine, pour chaque type de décision, la meilleure adaptation de l'horaire en estimant un coût ajouté pour chaque adaptation candidate. Les adaptations concernent seulement le jour où la perturbation a eu lieu et visent à palier la perturbation tout en gardant une solution globale quasi-optimale. Nous proposons également une procédure, exploitant une méthode de régression, pour mettre à jour les valeurs duales après la correction de chaque perturbation lorsque plusieurs d'entre elles surviennent durant l'horizon. Les tests menés sur un ensemble contenant 1050 instances de problèmes réels allant jusqu'à 191 employés ont montré l'efficacité de la méthode proposée. Celle-ci arrive à trouver la solution optimale pour plus de 95% de ces instances, et ce, en une seconde en moyenne. En second lieu, nous proposons une méthode de ré-optimisation en temps réel plus générale que la première : elle ne requiert pas l'information duale et ne se restreint pas seulement au jour où la perturbation a eu lieu, mais s'applique également au reste de l'horizon. La méthode cherche des adaptations qui permettent de corriger la perturbation sans trop s'éloigner de l'horaire planifié en termes du nombre de modifications engendrées par ces adaptations. Le coût ajouté dû à ces modifications doit être le moins élevé possible. À l'aide de certaines décisions de base qui permettent de générer tous les horaires possibles, la méthode cherche les bonnes séquences, appelées politiques, qui conduisent à des solutions de bonne qualité, appelées solutions non-dominées, obtenues après une optimisation multi-objectif. La méthode fait appel à un réseau qui schématise une région prometteuse de l'enveloppe convexe des solutions réalisables. La construction du réseau se fait d'une manière dynamique au cours de la résolution en se basant sur quelques résultats théoriques. Les tests menés sur des instances dérivées de données réelles impliquant jusqu'à 95 employés démontrent l'efficacité de l'heuristique. En moins d'une seconde en moyenne, elle peut calculer des solutions Paretooptimales pour plus de 98% des scénarios testés. L'efficacité et la rapidité de cette dernière méthode de ré-optimisation nous a poussé à être plus ambitieux pour l'adapter afin de faire une optimisation globale. Ceci a abouti à la naissance d'une nouvelle approche intégrée, qui génère et affecte les quarts simultanément et qui vise à optimiser un problème d'horaires de personnel. L'approche se base sur la stimulation/ correction itérative d'un ensemble de perturbations bien ciblées selon certaines mesures probabilistes. Ces dernières indiquent la probabilité que la correction de chacune de ces perturbations améliore significativement la solution courante. Deux procédures de groupage sont utilisées afin de générer un ensemble de sous-problèmes qui seront traités parallèlement. Chacun de ces sous-problèmes représente un terrain riche de perturbations visées pour les stimuler, ce qui rend la recherche plus efficace et rapide. Pour chaque sous-problème, nous stimulons une perturbation qui nous mène, généralement, à l'espace irréalisable. Ainsi, nous définissons un voisinage de recherche, sur ce sous-problème, afin de trouver une politique qui nous mène à l'espace réalisable. Nous combinons à chaque itération, de façon optimale, toutes les politiques qui sont compatibles (i.e., leur combinaison produit une solution réalisable) parmi celles trouvées parallèlement dans les sous-problèmes considérés afin de passer à une solution meilleure. L'heuristique proposée a été testée sur des instances réelles du problème impliquant jusqu'à 94 employés et 10 tâches. Notre méthode a alors permis de trouver des solutions de bonne qualité 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.