Grammar-Based Decomposition Methods for Multi-Activity Tour Scheduling

Les problèmes de planification d'horaires du personnel consistent à sélectionner un ensemble de quarts de travail en respectant certaines règles, et à assigner un certain nombre d'employés à chaque quart de travail, de sorte à satisfaire la demande de personnel. Ces problèmes sont généralement classés en trois catégories: planification des quarts de travail, planification des jours de repos et planification des patrons de travail. La première catégorie a pour but d'assigner les périodes de travail et de repos aux quarts de travail, et à sélectionner un ensemble de ces quarts de travail pour satisfaire les besoins en personnel. En planification des quarts de travail, l'horizon de planification est en général d'une journée, divisée en périodes de longueurs égales. La deuxième catégorie vise à sélectionner les jours de repos de chaque employé sur un horizon de planification d'au moins une semaine. Cette sélection est généralement contrainte par les préférences des employés ou par des conventions collectives. La dernière catégorie comprend les problèmes qui découlent de l'intégration des problèmes de planification des quarts de travail et de planification des jours de repos. Dans la version continue du problème de planification des patrons de travail, les quarts de travail peuvent s'étendre sur deux jours. Par contre, dans la version discontinue les quarts de travail doivent couvrir une seule journée. Différentes extensions du problème de planification d'horaires du personnel apparaissent lorsque des applications réelles sont considérées. Par exemple, dans les problèmes de planification des quarts multi-activités (MASSP) ou planification des patrons de travail multi-activités (MATSP), en plus de la définition des périodes de travail et de repos, des activités de travail différentes doivent être attribuées aux quarts de travail. Dans un contexte de multi-activités, les caractéristiques spécifiques liées aux règles de travail, aux conventions collectives, aux compétences des employés et à leurs préférences définissent un ensemble de règles à respecter pour construire les horaires des employés. D'autre part, le MASSP et le MATSP peuvent être soit personnalisés soit anonymes. Dans le premier cas, les employés ont des compétences et des préférences différentes, alors qu'elles sont identiques dans le second. Le problème peut également être stochastique, dans ce cas les besoins en employés (la demande) est incertaine. Dans cette thèse, nous aborderons trois catégories de MATSP : 1) MATSP discontinu, personnalisé, avec demande déterministe; 2) MATSP discontinu, anonyme avec demande déterministe; 3) MATSP discontinu, anonyme, avec demande stochastique. Pour résoudre ces problèmes, nous proposons différentes techniques de modélisation et de résolution qui sont principalement basées sur les méthodes de décomposition et les langages formels. Notre première contribution réside dans la conception de deux méthodes de type branch-and-price (B&P) pour aborder l'intégration de deux problèmes : le MASSP personnalisé et le problème de planification des patrons de travail discontinu. Chaque algorithme B\&P repose sur une formulation mathématique différente. La première formulation (formulation basée sur les jours) est une extension naturelle du MASSP personnalisé, ou les colonnes correspondent aux quarts de travail multi-activités, et les patrons de travail sont assemblés dans le problème maitre en utilisant des contraintes supplémentaires. Dans la seconde formulation (formulation basée sur les patrons de travail), le sous problèmes consistent à construire les quarts de travail multi-activités ainsi qu'à choisir les jours de repos. Par conséquent, dans cette formulation, les colonnes correspondent aux patrons de travail multi-activités. Dans les deux formulations, l'utilisation de grammaires nous permet de modéliser toutes les règles de travail pour la composition des quarts de travail, et de déduire des structures de graphes spéciales permettant de trouver les quarts de travail avec un coût réduit négatif. Une comparaison expérimentale et théorique de la qualité des bornes obtenues par la relaxation linéaire de chacune des formulations est réalisée. Les résultats montrent que la formulation basée sur les patrons de travail est meilleure (relativement aux bornes obtenues par la relaxation linéaire) que la formulation basée sur les jours. De plus, nos expériences montrent d'une part que les approches de modélisation proposées peuvent traiter une grande variété de règles sur les quarts de travail et sur les patrons de travail, et d'autre part que les méthodes implémentées peuvent résoudre efficacement des versions réalistes du problème. Les approches proposées sont clairement pertinentes en pratique, cependant des problèmes liés à la taille du modèle apparaissent lorsque le nombre d'activités et d'employés augmentent. La seconde contribution est une approche qui combine la décomposition de Benders et la génération de colonnes pour résoudre le problème intégrant le MASSP anonyme et la planification des patrons de travail discontinue. Afin de résoudre les problèmes de croissance des modèles et de symétrie associés aux nombres d'activités et d'employés, une autre façon de modéliser le MATSP est présentée. Les quarts de travail multi-activités sont implicitement générés par un modèle de programmation en nombres entiers basé sur une grammaire, alors que les patrons de travail sont explicitement composés via la génération de colonnes. Comme les sous-problèmes de l'approche de Benders sont des MIP qui n'ont pas la propriété d'intégralité, nous présentons une stratégie qui combine la génération de coupes de Benders classiques avec des coupes de Benders entières afin de garantir la convergence de la méthode. Les résultats expérimentaux montrent : 1) la capacité de notre approche à résoudre des cas pratiques impliquant un grand nombre d'employés et d'activités de travail; 2) que l'approche combinant la décomposition de Benders et la génération de colonnes à de meilleures performances que la méthode B&P pour le MATSP discontinu anonyme. Notre dernière contribution présente une approche de programmation stochastique en deux étapes pour résoudre le MATSP stochastique, discontinu, et anonyme. Les décisions de la première étape correspondent à l'affectation des employés aux patrons de travail. Les décisions de la deuxième étape (actions de recours) sont associées à la répartition des activités de travail et des pauses dans les quarts de travail. Une heuristique de type multi-cut L-shaped est présentée. Les expériences montrent que les performances de la méthode dépendent du profil de la demande, et que l'utilisation du modèle stochastique permet de réduire les coûts, en comparaison avec l'espérance de la solution moyenne.