Affectation d'activités et de tâches à des quarts de travail fixés

Pour les moyennes ou grandes entreprises, construire des horaires de travail réalisables à faible coût pour leurs employés n'est pas chose facile. Selon le type d'entreprises, trouver seulement un horaire réalisable peut relever du défi. Néanmoins, les techniques modernes de modélisation et d'optimisation permettent de proposer des méthodes efficaces pour plusieurs classes de problèmes d'horaires de personnel. Dans cette thèse, nous nous concentrons sur trois problèmes d'horaires de personnel dans lesquels les employés travaillent durant des quarts, par exemple dans des magasins à grande surface. Ces quarts doivent répondre à une demande en clients variable, à satisfaire le plus rapidement possible. Cette demande n'est pas exactement connue lorsque les quarts sont créés et a aussi un caractère périssable. Cela signifie que les compagnies peuvent perdre leurs clients immédiatement s'ils ne sont pas satisfaits du service offert. L'horaire d'un employé est composé de jours ouvrés et de jours vacants. Pour chaque jour ouvré, l'employé est affecté à un quart de travail défini par des temps de début et des temps de fin, et pouvant aussi contenir une ou plusieurs pauses. Dans notre cas d'étude, les temps de début et de fin, ainsi que le nombre idéal d'employés pour satisfaire la demande en clients, sont déterminés à l'avance par un module de prévision. Le travail d'un employé est catégorisé entre les tâches et les activités. Les activités correspondent au service des clients en temps réel, alors que les tâches n'impliquent pas un rapport direct avec les clients, bien que celles-ci soient en général cruciales. Dans les faits, une tâche est un travail non interruptible, tel que mettre en place une vitrine, tandis qu'une activité est facilement interruptible à tout moment, en remplaçant un employé par un autre, par exemple pour les caissiers. Les tâches ont une nature unique, isolée, sont effectuées par un employé qualifié avant une date limite, et requièrent éventuellement la complétion d'autres tâches avant leur temps de début. Les activités ont un caractère récurrent et continu. Leur contexte est le cas général d'activités multiples, dans lequel il est possible d'affecter plusieurs activités dans le quart d'un employé. Finalement, chaque quart de travail doit être rempli avec des activités ou des tâches à accomplir. Les conventions collectives restreignent, en général, la réalisabilité d'un horaire. De plus, les employés possèdent des qualifications et ne peuvent pas être affectés à des activités ou des tâches pour lesquelles ils ne sont pas qualifiés. Lors de la construction des horaires des employés, l'objectif principal de l'entreprise est de réduire ses coûts de personnel, tout en maintenant une satisfaction élevée chez sa clientèle. Un objectif secondaire est d'offrir à ses employés des horaires plaisants à travailler. Cette thèse traite en premier du problème d'affectation d'activités multiples, qui implique uniquement des activités. Trois modèles en nombres entiers et plusieurs méthodes de résolution sont proposées, mais la plus efficace reste une heuristique de type horizon fuyant basée sur un programme en nombres entiers. Le modèle sous-jacent est résolu par un algorithme de génération de colonnes encapsulé dans un schéma heuristique d'énumération implicite. Une comparaison avec les autres méthodes de résolution a été effectuée sur des instances générées aléatoirement, simulant des instances réalistes. Le deuxième sujet traité est le problème d'affectation de tâches et d'activités multiples. Le concept de tâche individuelle - qui est effectuée par un seul employé pendant une durée fixe - a été introduit dans la définition du problème précédent. Une décomposition en deux étapes est proposée pour s'attaquer aux instances de grande taille, sur lesquelles la résolution directe du modèle global proposé échoue. La première étape de la décomposition consiste à affecter les tâches a priori grâce à un modèle d'approximation, résolu heuristiquement. La deuxième étape produit alors une solution complète pour l'instance en affectant les activités, tout en s'autorisant à réaffecter les tâches. Des tests numériques ont montré que les quatre stratégies de réaffectation proposées sont surclassées par l'une d'entre elles. Ces tests valident également notre méthode et suggèrent que la réaffectation des tâches améliore la qualité des solutions obtenues au coût raisonnable d'un petit temps de calcul supplémentaire. Le dernier problème est une extension du précédent, par l'introduction des tâches en équipe, ce qui conduit au problème d'affectation de tâches en équipe et d'activités multiples. Le concept des tâches en équipe est une extension naturelle de celui des tâches individuelles et permet de considérer des pièces de travail non interruptibles, effectuées par plusieurs employés simultanément. Les relations entre le nombre d'employés contribuant à une tâche en équipe et le temps qu'ils y contribuent sont appelés patrons d'équipes. Inspirée de l'approche en deux étapes utilisée dans l'affectation de tâches individuelles, la méthode de résolution est basée sur deux modules d'affectation impliqués dans une descente à voisinages variables. Le premier module est un modèle d'approximation pour affecter les tâches en ne tenant que partiellement compte des activités. Le deuxième module consiste à affecter les activités en réaffectant les tâches. Des expérimentations numériques ont été réalisées et montrent que, premièrement, scinder les tâches peut améliorer la qualité des horaires, et deuxièmement, la méthode de résolution peut affecter des tâches en équipe, même si elles n'apparaissent pas dans la solution initiale de la descente. De plus, l'heuristique d'amélioration confirme l'efficacité de la décomposition en deux étapes pour l'affectation des tâches individuelles uniquement.

Abstract

For most medium- to large-sized companies, building a low-cost feasible working schedule for their employees is not an easy task. Depending on the business type, just finding a feasible schedule might even be a challenge. Nevertheless, modern modeling and optimization techniques allow to propose efficient solution methods for several personnel scheduling problems. In this thesis, we focus on three planning scheduling problems that arise in companies where the employees work shifts, such as retail stores. Those shifts should respond to a varying customer demand that must be fulfilled as soon as possible. The demand for each so-called activity is not exactly known when shifts are built and is also perishable. That means companies might lose clients immediately if they are not satisfied of the service. The schedule of an employee is composed of working days and days off. For each working day, the employee is assigned to a work shift that is defined by a start and an end time. It may also contain one or several specified break periods. For our concern, those start and end times are pre-determined by previous modules, as well as the ideal number of employees required to satisfy the customer demand, which is determined by a forecasting algorithm. The work of an employee is categorized between tasks and activities. Activities correspond to servicing customers in real-time, whereas tasks do not involve a direct contact with them, though they are crucial work. Actually, a task is an uninterruptible piece of work, such as setting up a display, whereas an activity can easily be interrupted at any time by replacing one employee with another, such as cashiers. The former has an isolated and unique nature and is performed by a skilled employee before a due date and may require the completion of some other tasks prior to its start. The latter has a continuous and recurrent nature. The context is the general multi-activity case, where it is possible to assign several activities to an employee shift. Finally, each work shift must be filled with activities or tasks to accomplish. Labor and collective agreement rules restrict the feasibility of a schedule. Furthermore, the employees possess skills and cannot be assigned to an activity or a task for which they are not qualified. When building the employee schedules, the primary objective of the company is to reduce personnel costs while maintaining customer satisfaction high. A secondary objective might be to offer as much as possible pleasant schedules to the employees. The thesis deals first with the multi-activity assignment problem, which implies only activities. Three integer models and several solution methods are proposed, but the best one is a rolling horizon heuristic based on an integer programming model. This model is solved by a column generation algorithm embedded in a heuristic branch-and-bound framework. Comparison with several other methods have been performed on randomly generated instances mimicing real-life instances. The next subject studied is the multi-activity and task assignment problem. Single tasks - which are performed each by only one employee during a fixed time length - are introduced in the definition of the previous problem. A two-stage decomposition is proposed to tackle large-sized instances on which the direct solving of the global model fails. This first stage of the decomposition consists of assigning tasks a priori thanks to an approximation model, solved by a heuristic, and then the second stage produces a complete solution by assigning activities with possible task reassignments. Numerical experiments show that the four proposed strategies for reassigning tasks are outclassed by one of them and validate our method. The results suggest also that reassigning tasks improve the solution quality a lot at the reasonable cost of a small extra computational time.