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.

Abstract

Personnel scheduling is a challenging problem for many organizations. In this thesis, we address different versions of the shift scheduling problem. The shift scheduling problem is to select a set of shifts to cover a planning horizon, typically from 1 to 7 days, divided into periods of equal length for which the required numbers of employees are given. A shift is defined by its starting time, its duration and its composition. Its composition is defined by the position of the breaks and work activities within the shift. We divide the shift scheduling problems into four main classes. First, we distinguish the problems where the employees are considered to be identical from the problems where each employee has individual characteristics that must be taken into account when assigning them to shifts. We call the first class the anonymous problems and the second one, the personalized problems. Then, we differenciate two other classes of problems, the mono-activity and the multi-activity shift scheduling problems. The former is a particular case of the latter and consists in specifying the work and rest periods to assign to the shifts. In the multi-activity case, we are also interested in a set of distinct work-activities to be performed. So, not only should we specify if the shift is assigned to a work-activity or not at a given period, but we must specify to which work-activity it is assigned. In this case, for each work-activity and each period, the required number of employees is given. In this thesis, we study each of these classes of shift scheduling problems with different approaches where constraints on shift construction are formulated with tools based on formal languages. In fact, using automata and grammars, we define languages composed of words that represent allowed shifts for our problem. More precisely, our first contribution presents how, from a finite automata or a context-free grammar defining the rules constraining the construction of shifts for a given problem, one can automatically generate an integer programming model based on binary assignment variables in a graph structure embedding every allowed shift for this problem. The transformation of an automaton or a grammar into a mathematical programming model is inspired by structures from constraint programming. Experiments on a multi-activity shift scheduling problem show that formal language based modeling is very powerful and allows us to address complex rules in the construction of multi-activity shifts. However, while the relevance of our modeling approach is clear, the experimental results reveal some limitations on the scalability of the formulation based on binary assignment variables and decomposed on employees. In fact, when the number of employees and the number of work-activities grow, the model is hard to solve directly.