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

Quand on me contredit, on éveille mon attention, mais non ma colère : je m'avance vers celui qui me contredit, qui m'instruit.La cause de la vérité devrait être la cause commune de l'un et de l'autre.»MONTAIGNE (1572de l'un et de l'autre.»MONTAIGNE ( -1592)).Essais, III.v REMERCIEMENTS Je tiens tout d'abord à remercier mes deux directeurs de recherche : Issmail El Hallaoui et Guy Desaulniers.Ils m'ont accueilli au sein de leur équipe de recherche et ont su, malgré leurs responsabilités, me donner de leur temps et de leur patience.Ils m'ont aussi beaucoup aidé lors de la rédaction de cette thèse et de ces articles de recherche.C'est grâce à leurs consignes, recommandations, conseils et encouragements que j'ai pu finir cette thèse à temps.Je me considère très chanceux d'avoir été encadré par eux.J'exprime également ma reconnaissance et ma considération envers François Soumis avec qui j'ai échangé à plusieurs reprises durant le déroulement de ma thèse.Je remercie les membres du jury, Michel Gendreau, Antoine Legrain et Djamal Rebaïne, qui m'ont fait l'honneur de juger ce travail doctoral.Je remercie également le CRSNG et KRONOS Inc. qui ont participé au financement de mon projet.J'ai eu l'opportunité de côtoyer pendant ces quatre années des femmes et des hommes qui, en plus d'être très compétents, sont particulièrement humains et serviables.Je les remercie pour leur contribution au bon déroulement de cette thèse.Un remerciement spécial à Adil, Chahid, Safae, Bani, Ilyas, Omar, Mayssoun, Tayeb, Salah, Issoufou, Fillipo, Dalia et Hélène.Merci à certains professeurs que j'ai croisés au cours de ma scolarité, qui m'ont marqué sur les plans personnel et professionnel.Je pense plus particulièrement à Ahmed Akrkouz, Abdelwahed Samid et Hassan Elidrissi.Merci aussi à mes plus anciens amis : les deux Mehdis, Amine, Mkireb, Yves, Ivan, Victoria, Awatif, Hamza et Anouar.Merci plus particulièrement à Mounia pour son aide inestimable, son soutien permanent et pour m'avoir remonté le moral dans les périodes les plus difficiles, quand le doute s'installait.Un énorme merci à mes frères et sœurs : Fatima, Mohammed, Hind, Atif et Hasna, qui ont contribué à leur façon pour me soutenir.Une mention toute particulière à Fatima, qui a bien jouée le rôle d'une grande sage sœur, et parfois, le rôle d'une mère et d'un père pour des bonnes périodes de ma vie : c'est grâce à elle que j'ai pu mener un tel parcours scolaire.Finalement, je souhaite finir par le remerciement le plus grand pour mon épouse Hanae, mon père M'Hammed et ma mère Khadija.Ma chère Hanae, un grand merci pour ton soutien, ton encouragement et ton amour.Merci d'avoir été à mes côtés dans toutes les phases de ces quatre années : des hauts, des bas et souvent des entre-deux.Merci infiniment, mes chers vi parents, pour tout ce que vous avez fait pour moi.Merci d'avoir toujours pensé en priorité à ma réussite scolaire et d'avoir toujours œuvré pour que je ne manque de rien.vii RÉSUMÉ 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 viii 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.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.