Utilisation de langages formels pour la modélisation et la résolution de problèmes de planification de quarts de travail

La planification d'horaires de personnel représente un défi pour plusieurs organisations. Dans cette thèse, nous étudions différentes variantes du problème de planification des quarts de travail. La planification des quarts de travail représente la sélection d'un ensemble de quarts couvrant une période de temps, typiquement une journée à une semaine, divisée en périodes de durées égales pour lesquelles un nombre d'employés requis est donné. Un quart est défini par son heure de début, sa durée et par sa composition en termes d'affectation de pauses et d'activités de travail. Nous divisons les problèmes de planification de quarts en quatre classes. Premièrement, les problèmes où les employés sont considérés comme identiques et les problèmes où les employés ont des caractéristiques individuelles qui les distinguent et qui doivent être prises en compte dans la sélection des quarts. Nous référons à la première classe de problèmes comme étant des problèmes anonymes et à la seconde, comme étant des problèmes personnalisés. Ensuite, nous différencions les problèmes de planification de quarts mono-activité et multi-activités. La première classe de problèmes est en fait un cas particulier de la deuxième. Elle détermine quelles périodes du quart sont affectées à des activités de travail et quelles périodes sont affectées à des activités de repos (repos, pause, repas), alors que les problèmes de planification de quarts multi-activités définissent pour chaque période de travail du quart quelle activité de travail, parmi un ensemble d'activités de travail pouvant être effectuées, lui est affectée. Dans ce cas, pour chaque activité de travail et pour chaque période de temps sur lequel s'étend l'horaire, le nombre d'employés requis est donné. Dans cette thèse, nous abordons chacune des classes de problèmes de planification de quarts à l'aide de différentes approches, toutes basées sur la formulation des contraintes restreignant la formation des quarts par des outils issus de la théorie des langages formels. En effet, à l'aide d'automates et de grammaires, nous pouvons définir des langages qui sont composés d'un ensemble de mots représentant des quarts respectant les contraintes de notre problème. Les automates et les grammaires sont des outils très expressifs qui permettent de formuler plusieurs concepts relatifs à notre contexte de manière relativement naturelle. Plus précisément, notre première contribution présente comment, à partir d'un automate ou d'une grammaire définissant les règles régissant la composition des quarts pour un problème, nous pouvons générer automatiquement un modèle linéaire en nombres entiers basé sur des variables d'affectation binaires dans une structure de graphe qui encode tous les quarts permis par ce problème. La transformation d'un automate ou d'une grammaire en modèle de programmation mathématique est inspirée de structures de la programmation par contraintes. Un exemple experimental de problème de planification de quarts multi-activités montre la puissance de la modélisation utilisant les langages formels. En effet, cette nouvelle approche de modélisation permet d'aborder des règles très complexes en ce qui concerne la composition des quarts multi-activités. Malgré que l'intérêt de ce type de modèles dans le contexte de problèmes de planification de quarts soit indéniable, les résultats expérimentaux soulèvent les limites de la formulation décomposée par employés et définie avec des variables d'affectation binaires. En effet, avec le nombre d'employés et le nombre d'activités de travail qui augmentent, le modèle devient difficile à résoudre directement.