Une heuristique en deux phases pour la confection d'horaires de personnel avec transferts inter-départementaux d'employés

L'un des problèmes classiques de la recherche opérationnelle est la confection des horaires de travail personnalisés. L'optimisation des horaires de travail vise à spécifier, pour chaque jour de l'horizon de planification, la séquence des jours de travail et de repos de chaque employé, à construire des quarts de travail ainsi qu'à affecter ces quarts aux employées. Dans un contexte multi-activités, cela inclura de générer également les séquences d'activités exécutées dans chaque quart de travail. La plupart des grandes entreprises sont divisées en départements. La gestion de la main-d'oeuvre se fait en rattachant un ensemble d'employés à chacun de ces départements. De plus, en tenant compte de l'évolution professionnelle des employés, la plupart se retrouvent rattachés à plus d'un département et acquièrent ainsi de l'expérience dans plusieurs d'entre eux tout au long de leur carrière. Les employés se retrouvent donc qualifiés à travailler dans plusieurs départements au sein d'une même entreprise. Dans ce mémoire de maîtrise, nous nous intéressons à la confection d'horaires de travail personnalisés en tenant compte de la possibilité de transférer des employés entre les départements. Cela se présente notamment dans les magasins à grande surface où un employé peut passer d'un département à un autre durant son quart de travail. Il s'agit donc d'un contexte multi-départements où chaque département est mono-activité, c'est-à-dire que nous considérons une seule activité par département. De plus, chaque employé peut travailler au plus dans deux départements par quart. Quand il doit travailler dans deux départements, l'un d'eux doit nécessairement être son département d'origine. Chaque employé est qualifié pour un ensemble donné de départements en dehors du département auquel il est rattaché à l'origine. Par ailleurs, les courbes de demandes pour chaque département ainsi que les qualifications des employés sont connus à l'avance. Aussi, les règles de la convention collective relativement aux horaires ainsi que d'autres règles entreront en jeu pour générer des horaires réalisables. L'objectif principal du problème est de minimiser la somme pondérée des coûts totaux. Ces derniers sont principalement composés de quatre types de coûts différents : (1) le coût associé aux heures travaillées, (2) des pénalités pour le transfert de personnel entre départements, (3) le coût total des périodes en sous-couverture et (4) le coût total des périodes en sur-couverture. Le coût de travail est calculé pour chaque employé en fonction de la durée de son quart de travail. Le coût de transfert, quant à lui, est calculé en fonction de la durée du transfert. Pour une période de transfert donnée, ce coût s'ajoute ainsi au coût de travail de la même période. Par ailleurs, la satisfaction de la demande en main-d'oeuvre n'est pas toujours possible notamment dans le cas où la demande excède le nombre total d'employés disponibles. Pour cela, on permet la sous-couverture et la sur-couverture de la demande moyennant des pénalités sous forme de coûts : il s'agit des coûts de sous et sur-couverture. Alors que les coûts de travail et de transfert dépendent de l'employé effectuant le quart et de la durée des périodes considérées, les coûts de sous et sur-couverture dépendent quant à elles du département au sein duquel on fait face à la sous-couverture ou à la sur-couverture. L'objectif principal de ce projet de recherche est donc de proposer une méthodologie de confection d'horaires de travail personnalisés afin de résoudre efficacement ce problème. Des jeux de données réels de grande taille seront utilisés pour tester et valider les différents modèles et algorithmes proposés. En pratique, les transferts sont planifiés séquentiellement à la main après avoir fait l'affectation par département. Nous commençons d'abord par automatiser ce processus en développant un algorithme glouton. Nous proposons ensuite une amélioration qui consiste à remplacer l'algorithme glouton par un modèle global résolu directement par Xpress-MP qui permet de traiter le problème au complet comme un problème mixte en nombres entiers en ayant une vue globale pour le calcul des transferts. La résolution du modèle global permet d'assigner à chaque employé, durant l'horizon de planification, un ensemble de quarts personnalisés admissibles. Pour cela, nous fournissons une énumération explicite des quarts de travail notamment l'heure de début, la durée du quart de travail, la durée de transfert et le placement du transfert pour chaque quart. Par conséquent, on se retrouve avec un très grand nombre de possibilités ce qui augmente la complexité du modèle et le temps d'exécution. Par la suite, nous proposons une approche à deux phases pour résoudre le problème de confection d'horaires avec transferts entre les départements pour lequel la résolution d'un modèle mathématique global échoue sur les instances de grande taille. En effet, formuler explicitement tous les quarts de travail en portant une certaine exibilité sur la définition des heures de début, des durées ou du placement des périodes de transferts produit un très grand nombre de possibilités et augmente la complexité du modèle. Dans l'approche à deux phases, un modèle séquentiel département par département est utilisé dans la première phase sans permettre les transferts. La solution obtenue est alors ré-optimisée dans la seconde phase en permettant les transferts entre les départements. Nous présentons les résultats pour les différents modèles proposées dans la deuxième phase. Le modèle séquentiel département par département vise à assigner à chaque employé un quart de travail dans son département d'origine. Un modèle mathématique en nombres entiers résolu par Xpress-MP est alors utilisé. Différentes approches de résolution sont proposées pour la seconde phase de réoptimisation incluant un algorithme glouton et des modèles linéaires en nombres entiers aussi résolus par Xpress-MP. Les expérimentations numériques réalisées sur différents jeux de données de grande taille montrent que les temps de calcul sont nettement moindres avec la méthode en deux phases. De plus, l'heuristique assure une couverture de la demande totale à plus de 99.8%. Elle améliore aussi les résultats par rapport à la pratique, soit l'algorithme glouton. Par contre, la qualité des solutions est grandement détériorée (d'environ 30%) pour les instances de petite taille. Par ailleurs, des tests montrent que l'heuristique pourrait s'améliorer encore plus en permettant de remettre en cause les quarts internes. Pour les instances de grande taille rencontrées en pratique, l'heuristique permet d'obtenir des solutions en des temps plus qu'acceptables, soit moins de 2 minutes pour des instances avec 8 départements et 191 employés.