Optimization of heterogeneous employee scheduling problems

Le problème de planification d'horaires du personnel consiste à créer les horaires de travail des employés d'une organisation. Le nombre d'employés requis par unité de temps, appelé la demande en employés par période, est donné pour un horizon de planification. Différentes règles et contraintes régissent l'élaboration des horaires des employés. Ces règles dépendent des besoins de l'organisation, des contrats des employés et de la convention collective de travail. Le problème de planification est dit hétérogène quand il concerne des employés ayant des qualifications différentes, habituellement, dans le cadre d'un problème de planification d'employés multi-tâches ou multi-départements. Dans un contexte multi-départements avec transferts entre départements, un quart de travail peut être effectué dans son ensemble dans un département, ou un transfert de département peut avoir lieu au sein du quart de travail lorsque l'employé a les qualifications requises. Lorsque les transferts sont autorisés, le nombre de quarts de travail possibles par employé devient énorme. L'optimisation d'un tel problème est souvent essentielle pour le succès de l'organisation. Par contre, sa résolution directe comme un programme linéaire en nombres entiers s'avère impossible pour les grandes instances. Dans la première partie de cette thèse, nous proposons une heuristique de décomposition en plusieurs phases (MP-DH) pour le problème de planification des employés avec transferts. Dans ce problème, la sous-couverture et la sur-couverture sont acceptées mais pénalisés dans la fonction objectif. Un département d'origine est introduit pour chaque employé où l'employé doit travailler la majorité de son temps. En plus, il/elle peut être qualifié(e) pour travailler dans plusieurs autres départements. La première phase commence par déduire la demande en employés qui ne peut pas être couverte par les employés du département. Ces pièces de demandes extraites sont appelées intervalles critiques, car elles nécessitent des employés transférés d'autres départements pour y travailler. Cela se fait en résolvant un programme en nombres entiers de planification d'horaires de personnel anonyme pour chaque département séparément, puis en extrayant la demande non-couverte qui définit un ensemble d'intervalles critiques. Pour chacun des intervalles critiques, la deuxième phase choisit un département qui lui attribue la responsabilité de transférer un de ses employés pour travailler pendant cet intervalle critique. Ceci est accompli en résolvant un autre programme en nombres entiers de planification d'horaires de personnel anonyme avec transferts, pour un seul jour, pour chacun des jours de l'horizon. La décomposition journalière rend la taille du problème gérable spécialement pour les grandes instances. Cette phase se termine par la migration de toute demande d'un département d1 couverte par un employé d'un département d2, formant la demande de transfert d'employé de d2 vers d1. Finalement, pour chaque département, la troisième phase résout un programme en nombres entiers de planification d'horaires de personnel mono-départemental avec transfert. La demande utilisée est la nouvelle demande résultant de la migration de toutes les demandes de transfert pendant la deuxième phase. L'heuristique MP-DH a réussi à décomposer le problème de planification d'employés multidépartements en plusieurs, plus petits, problèmes de planification d'employés mono départementaux, ce qui a permis de réduire de beaucoup les temps de calcul et de transformer les grandes instances non résolubles en instances résolubles avec une légère baisse dans la qualité des solutions obtenues. Chacune des trois phases de MP-DH utilise le parallélisme. Dans la première phase, les programmes en nombres entiers des départements s'optimisent en parallèle. La deuxième phase exécute chaque problème journalier en parallèle. Enfin, la troisième phase optimise chaque département en parallèle. À la fin de chaque phase, tous les résultats des problèmes parallèles sont fusionnés pour former la solution finale. Dans les tests réalisés pour l'heuristique MP-DH, les deux premières phases sont extrêmement rapides, tandis que la troisième phase peut atteindre deux heures de temps de résolution pour les grandes instances. Pour pallier à cet inconvénient, nous présentons une heuristique hybride dans la deuxième partie de la thèse, visant à réduire fortement le temps d'exécution de la troisième phase tout en conservant la qualité de la solution. L'heuristique hybride utilise deux modèles de manière interchangeable afin de résoudre la troisième phase le plus précisément et rapidement possible. Le premier modèle est celui déjà presenté pour la troisième phase du MP-DH que nous appelons le modèle de base. Le second est un problème de planification d'horaires du personnel mono-département avec transfert semi-anonyme que nous appelons le modèle semi-anonyme. La version semi-anonyme réduit le nombre d'employés pour lesquels les horaires sont optimisés et remplace les quarts des employés restants par un ensemble de quarts anonymes agrégés, puis résout le problème pour les employés restants par la suite. L'heuristique hybride commence par résoudre le modèle de base. Si après un délai donné, l'écart d'optimalité est supérieur à un seuil donné, la résolution de modèle de base est annulé et une version semi-anonyme est résolue. Cette opération est répétée jusqu'à ce que tous les horaires des employés soient optimisés. L'heuristique hybride a réussi à réduire le temps d'exécution de la troisième phase jusqu'à 87% en moyenne, tout en perdant seulement 4 % dans le coût de la solution en moyenne. Dans la troisième partie de la thèse, nous abordons une version différente du problème de planification d'horaires de personnel, soit le problème de planification d'horaires de personnel multi-tâches, où ni les transferts ni la sous-couverture ne sont autorisés. À la place de la sous-couverture, des quarts anonymes appelés open-shifts sont utilisés pour couvrir la demande incouvrable par aucun employé. Nous développons une métaheuristique parallèle de recherche à grands voisinage (LNS) pour ce problème. Le concept de sub-scope est utilisé comme unité de décomposition dans l'algorithme LNS. Un sub-scope est défini comme: un sous-ensemble d'employés, un sous-ensemble de tâches et un sous-ensemble continu de l'horizon du problème. L'heuristique LNS est définie par des procédures de destruction et de réparation. Notre procédure de destruction choisit des sub-scopes, entraînant un coût élevé, à détruire. Lorsqu'un sub-scope d'une solution est détruit, tous les quarts travaillés pendant l'horizon du sub-scope par un employé appartenant au sub-scope, pour l'une des tâches du sub-scope, sont supprimés de la solution. Les coûts principaux affectant la fonction objectif sont les suivants: le coût de la surcouverture, le coût d'utilisation des open-shifts et la pénalité pour la violation des heures de travail minimales des employés. La procédure de destruction se concentre donc sur la destruction des sub-scopes entraînant de tels coûts dans une solution donnée. Après la destruction des sub-scopes d'une solution, la procédure de réparation reconstruit une nouvelle solution améliorée. La procédure de réparation que nous proposons résout un programme en nombres entiers de planification d'horaires de personnel multi-tâches pour les sub-scopes déjà détruits. Les procédures de destruction et de réparation sont répétées séquentiellement jusqu'à ce que la condition d'arrêt soit atteinte. La procédure de destruction parallèle détruit plusieurs sub-scopes disjoints, puis chaque subscope est réparé dans un fil (thread) parallèle différent. Nous comparons l'heuristique présentée avec le modèle exact résolu dans le système commercial WFC par Kronos Inc. Les résultats expérimentaux montrent qu'en moyenne, l'algorithme LNS parallèle peut réduire les temps d'exécution jusqu'à 80% et améliorer les coûts des solutions jusqu'à 1, 8%.