Ré-optimisation d'horaires de personnel en ajoutant des transferts entre départements

Le problème de planification d'horaires du personnel prend de plus en plus de place dans les problèmes traités en recherche opérationnelle. La littérature sur ce problème présente une vaste collection de modèles et de méthodologies de résolution. Ce problème consiste à déterminer un horaire qui spécifie le début et la fin de chaque quart de travail, les durées et les positions de pauses durant un quart de travail sur un horizon de planification. En général, l'horizon de planification est discrétisé en un ensemble de périodes de durées égales et une demande est définie en fonction de ces périodes. La demande représente le nombre d'employés requis pour chaque période. Pour couvrir la demande, il faut affecter un nombre d'employés pour chacune des périodes de l'horizon de planification tout en respectant la réglementation de la convention collective. Il n'est pas toujours possible de faire coïncider l'horaire ainsi obtenu avec la demande. Il se peut que le nombre d'employés affectés pour une période donnée soit supérieur au nombre d'employés demandés, dans ce cas on dit qu'il y a sur-couverture de la demande. Parfois, le nombre d'employés affectés pour une période donnée est inférieur au nombre d'employés demandés, et dans ce cas, c'est une sous-couverture de la demande. Le but est d'éviter de créer de la sous-couverture pour pouvoir assurer une bonne qualité de service ou de créer de la sur-couverture pour éviter de payer des employés pour un temps de travail improductif. Plusieurs particularités peuvent être observées quand nous considérons des problèmes réels spécifiques. Par exemple, le fait que la structure d'entreprise se base sur un ensemble d'unités distinctes (des départements) et que pour chaque unité un certain nombre d'employés peut y être rattachés. De plus, de par leurs expériences, les employés peuvent travailler dans plusieurs départements. En pratique, dans le contexte multi-départements, les horaires sont d'abord faits séparément pour chaque département. Ensuite, les employés qui sont en surplus dans un département peuvent éventuellement être affectés à d'autres départements pour combler les manques du personnel s'ils sont qualifiés. Il serait toutefois préférable de planifier les horaires de façon globale. Nous avons commencé par développer un modèle global pour avoir un horaire centralisé pour tous les départements en une seule étape. Mais, ce modèle devient difficile à résoudre quand la taille augmente, voire même impossible dans certains cas. Ce mémoire présente une méthode heuristique de résolution du problème de planification d'horaires du personnel dans un contexte multi-départements avec la possibilité de partager la main-d'oeuvre qualifiée entre les départements. Nous considérons qu'une entreprise a un ensemble de départements et un ensemble d'employés et que chaque département se spécialise dans la production d'un bien ou l'offre d'un service. Un employé peut avoir plusieurs qualifications. Cependant, il est rattaché à un département appelé département d'origine. En plus, de par son expérience, un employé peut travailler occasionnellement dans d'autres départements secondaires. Chaque département est mono-activité, il a donc une seule courbe de demande qui représente le nombre d'employés requis pour chacune des périodes de l'horizon de planification. L'heuristique proposée se déroule en deux phases. La première phase est une résolution du problème mono-département pour chacun des départements sans permettre le partage de la main-d'oeuvre. La démarche classique est de générer l'ensemble global des quarts par département sans prise en compte des possibilités de transfert et de chercher à avoir la meilleure solution par département. Parfois les employés rattachés à chaque département ne suffisent pas pour répondre à la demande. La deuxième phase a une vue plus globale. C'est une ré-optimisation de la solution obtenue dans la première phase en ajoutant des transferts. Certaines règles de transfert sont à respecter comme par exemple la possibilité d'avoir au plus un transfert par jour par employé. Dans ce projet, nous avons commencé par résoudre le problème d'une façon globale en générant tous les types de quarts possibles. La solution ainsi obtenue est la solution optimale globale du problème. Ensuite pour la deuxième phase de l'heuristique, trois approches de génération de quarts avec transfert sont proposées. Dans la première approche, nous interdisons la modification de l'horaire issu de la première phase. Nous nous permettons d'ajouter des quarts avec transfert sans remettre en question les quarts retenus dans la solution de la première phase. Cette approche est très restrictive, elle ne permet pas une grande amélioration au niveau de la solution obtenue dans la première phase. Puis, dans le but d'améliorer cette solution, la modification de la solution initiale de la première phase est autorisée en transformant les quarts retenus en des nouveaux quarts avec transferts d'une façon plus flexible. La transformation peut se faire en allongeant ou en raccourcissant un quart avec l'ajout des périodes de transfert. Nous obtenons de meilleurs résultats que ceux de la première approche mais la solution globale optimale n'est atteinte que pour une seule instance de test. Dans le but d'atteindre cette solution, une troisième approche est proposée. Pour cette approche, nous nous donnons encore plus de liberté pour modifier la solution de première phase. Nous pouvons permuter les quarts des employés entre eux pour favoriser les transferts. Nous obtenons de bonnes solutions avec des temps de calcul raisonnables. Nous considérons que ces solutions peuvent être améliorées avec l'amélioration de la solution de la première phase. Vers la fin du mémoire, une attention particulière est portée sur l'amélioration de la première phase classique. Une nouvelle méthode pour résoudre la première phase est proposée. Elle permet de donner une meilleure solution de première phase plus adaptée à l'ajout des transferts. Les résultats obtenus sont nettement améliorés et nous avons réussi à obtenir des solutions avec moins de 5% d'écart avec la solution optimale globale dans 75% des instances de test en des temps de calcul raisonnables.