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.