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.