Utilisation de langages formels pour la modelisation et la resolution de problemes de planification de quarts de travail.

摘要

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. 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 differentiate two other classes of problems, the mono-activity and the multi-activity shift scheduling problems. 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.;To address both the growing size of the models and the symmetry issues arising from a context where employees are identical, our second contribution is an implicit model based on grammars allowing us to model and solve anonymous multi-activity shift scheduling problems efficiently. From a grammar encoding every restriction in the composition of shifts, we use the graph structure presented in the first article. Instead of using binary variables associated with allowed shifts for each employee, we use nonnegative integer variables to implicitly represent, in a single graph structure, every allowed shift for the problem. The optimal solution to the corresponding integer programming model gives the required number of shifts to cover the demands of the problem and the number of shifts assigned to each work-activity at each period. From these informations, a procedure extracts the optimal explicit solution from the implicit one. Experimental results show that this modeling approach gives easy-to-solve models and can address a wide variety of rules over shifts. We also prove that the models obtained with our technique yield the same integrality gap as well known models in the literature. To our knowledge, this is the first implicit method that can address the multi-activity shift scheduling cases.;Our last contribution is a column generation approach also based on grammars that allows us to successfully solve personalized multi-activity shift scheduling problems. The method uses a set covering formulation to model the problem and solves the linear relaxation with a column generation method based on a pricing subproblem using the graph generated from a grammar. A subproblem is defined for each available employee and represents the set of shifts that the given employee is allowed to perform given his individual characteristics. The subproblems are solved with a dynamic programming algorithm. An adapted branching procedure is proposed to find integer solutions and solve the problem exactly. Our method uses a new column generation subproblem and a new branching strategy for this class of problems. The modeling approach is very flexible and contrary to the few other approaches proposed in the literature, it can solve exactly different versions of the personalized multi-activity shift scheduling problem. (Abstract shortened by UMI.)