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.