Ré-optimisation de l'horaire de travail d'employés en surtemps

L'objectif principal de chaque entreprise est de maximiser ses profits ou d'offrir un service de qualité à moindre coût. L'entreprise cherche alors à générer des horaires de travail de ses employés qui couvrent la demande de sa clientèle tout en respectant les règlementations et les conventions collectives. L'entreprise cherche aussi à générer des horaires de travail qui couvrent la demande de sa clientèle tout en offrant un service de qualité. Ainsi, les problèmes de construction d'horaires de personnel ont été étudiés depuis plusieurs décennies en recherche opérationnelle. Suite à une perturbation de la demande, il est possible que l'horaire généré une semaine plus tôt avec une certaine prévision de demande ne soit plus valable pour la nouvelle demande observée le jour même. Par exemple, un changement climatique non prévu peut diminuer considérablement la demande. Dans le sens contraire, une demande plus élevée que celle prévue au début de la semaine nécessite plus de quarts de travail que ceux déjà planifiés pour la couvrir. Dans les deux cas, il faut mettre à jour l'horaire pour répondre au mieux à cette demande. Cette mise à jour est souvent effectuée en temps réel et peut faire en sorte que le quart d'un employé est allongé ce qui l'amène en surtemps, augmentant ainsi son salaire horaire pour le temps supplémentaire accumulé tout au long d'une semaine. En fin de journée, lorsque le gérant dispose de plus de temps pour revoir les horaires, une ré-optimisation des horaires peut être faite pour éviter le temps supplémentaire engendré en cours de journée. Ce projet de maîtrise répond à ce problème de ré-optimisation de l'horaire de personnel qui tombe en surtemps. Nous nous plaçons dans le domaine de vente au détail où l'horaire est non continu. Pour résoudre le problème, nous proposons une méthode exacte basée sur un modèle linéaire en nombres entiers et deux méthodes heuristiques en deux phases qui consistent à résoudre un programme linéaire en nombres entiers de taille réduite en limitant le nombre de quarts de travail que nous générons et ainsi accélérer le temps de résolution. Pour chaque méthode de résolution, nous introduisons deux approches. Chaque approche est basée sur la résolution d'un ou plusieurs programmes linéaires en nombres entiers. La première est une approche séquentielle dans laquelle les employés en surtemps sont traités l'un après l'autre et la deuxième est une approche simultanée où les employés en surtemps sont traités tous à la fois. Nous présentons ensuite différents types de transformations possibles pour les quarts. Avec ces transformations effectuées sur les quarts d'un horaire initial, nous générons des nouveaux quarts modifiés qu'on appelle quarts proposés. Enfin, nous définissons une structure de coût adaptée à la ré-optimisation. Cette structure pénalise toute modification de l'horaire. L'analyse des solutions obtenues après avoir effectué des tests sur des jeux de données réels montrent qu'on est arrivé à enlever le surtemps et améliorer les coûts des solutions initiales. En outre, l'utilisation des deux heuristiques accélère le temps de calcul mais dégrade légèrement la qualité de la solution.

Abstract

Each company is looking to generate work schedules that cover the demand of its customers while offering a service of quality and being sure to enforce the regulations and collective agreements. However, due to some unpredictable demand variation, it is possible that the schedule planned a week ahead with some demand forecast is no longer valid for the new demand observed the same day. For example, a higher demand than scheduled a week earlier requires more shifts than those already planned. In this case, the schedule needs to be updated to meet this request. This update is often done in real time by extending some employees' shifts which brings them into overtime, thus increasing their salary for additional time accumulated throughout a week. At the end of the day, a schedule re-optimization can be made to avoid the extra time generated during the day. This master's thesis is responding to this shift rescheduling problem. We deal with a noncontinuous retail environment. To solve the problem, we propose an exact method based on an integer programming model and two two-phase heuristic methods that consist in solving a reduced-sized integer linear program by limiting the number of generated shifts and thus reduce the computational time. For each solution method, we introduce two approaches. Each approach is based on solving one or more linear integer programs. The first is a sequential approach in which employees with overtime are treated one after other and the second is a simultaneous approach where these employees are treated all at once. We then present different types of possible shift transformations to generate new modified ones called proposed shifts. Finally, we define a cost structure adapted to the re-optimization. This structure penalizes every schedule modification. After performing tests on real datasets, we analyze the computed solutions to show that we have succeeded in removing overtime and improving the initial solutions costs. In addition, we observe that both heuristics speed up the computation time but slightly degrades the solution quality.