Optimization of heterogeneous employee scheduling problems

RÉSUMÉ: 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%. ABSTRACT: The employee scheduling problem consists of creating working schedules for an organization staff. The number of required employees per time unit, called employee requirement per period, is given for the full problem horizon. Different rules and constraints govern an employee scheduling problem, these rules depends on the organization needs, employees contracts and the collective labor agreement. A heterogeneous employee scheduling problem deals with employees having different working skills, usually within a multi-job or multi-department employee scheduling context, where one employee can be qualified for several of the organization activities, and can work for any activity he/she is qualified for. One working shift can be accomplished in a single department, or a department transfer can take place within a shift when the employee has the required skills. When a department transfer within a shift is allowed, the number of possible working shifts per employee becomes huge. Optimizing such heterogeneous employee scheduling problem is often essential for organizational success. However, solving such problems directly as a mixed integer linear program (MILP) is intractable for large instances. In the first part of this thesis, we propose a multi-phase decomposition heuristic (MP-DH) for the employee scheduling problem with inter-department transfers. In this problem, the concept of department of origin is introduced, where each employee is qualified to work in several departments, but he/she has exactly one department of origin, where the employee should work the majority of his/her time. The first phase starts by extracting from each department employee requirement, the uncoverable requirement parts by internal employees,i.e. if only the department internal employees can work. These extracted requirement parts are called critical intervals, because they need transferred employees from other departments to fulfill them. This is done by solving an anonymous employee scheduling problem modeled as a MILP for each department apart, before extracting the uncovered requirement parts that form the set of critical intervals. For each of the critical intervals, in the second phase, one department is chosen to assign it the responsibility of fulfilling this critical interval requirement, i.e. to transfer one of its employees to work during the critical interval. This is accomplished by solving a one-day anonymous employee scheduling problem with inter-department transfers for the critical intervals modeled as a MILP, for each of the problem horizon days. The day decomposition renders the problem size manageable in computer memory, especially for large instances (up to 25 departments). This phase ends by migrating any department d1 requirement covered by an employee from department d2, building a new employee transfer requirement from d2 to d1. The third phase solves, for each department, a mono-department employee scheduling problem with derived inter-department transfers as a MILP. The input to the third phase is the new final requirement resulting from the requirement migration of phase two. The MP-DH heuristic succeeds to decompose the multi-department employee scheduling problem into several mono-department employee scheduling problems to save substantial computational time. This allows to solve large instances while not deteriorating much the solution quality. Each phase of the MP-DH algorithm uses parallelism. In the first phase, all department MILPs and post-processing are accomplished in parallel. The second phase runs all singleday problems in parallel. Finally the third phase optimizes all department problems in parallel. At the end of each phase, all parallel problem solutions are merged to form the final solution. In the reported computational experiments, we observe that the first two phases are solved extremely fast compared to the third phase. The size of the solved MILPs in the first two phases is not proportional with the size of the optimized instance, while the third phase MILP size is. To overcome the computational issues of the third phase we present the hybrid heuristic in the second part of the thesis. The hybrid heuristic aims at greatly reducing the MP-DH third phase computational time, while maintaining the solution quality. The hybrid heuristic uses two models interchangeably in order to solve the third phase as accurate and as fast as possible. The first is the third phase MILP of the MP-DH algorithm, which we call the basic model. The second is a semi-anonymous employee scheduling problem with derived inter-department transfers modeled as a MILP that we call the semi-anonymous model. The semi-anonymous version reduces the number of employees for whom the schedules are optimized, and replaces the remaining employee shifts by a set of aggregated anonymous shifts. Once such a model is solved, the schedules of the selected employees are fixed and the algorithm moves on to solving another MILP where another set of employees must be scheduled. The hybrid heuristic starts by solving the basic model, then if, after a given time limit, the MILP optimality gap is higher than a given threshold, the resolution of the basic model is stopped and a semi-anonymous version is solved. This is done repeatedly until all employee schedules are optimized. The hybrid heuristic succeeded in reducing on average up to 87% of the third phase computational time while only loosing 4% in the solution quality. In the third part of the thesis, we tackle a different employee scheduling problem variant: the multi-job employee scheduling problem, where neither transfers nor under-coverage is allowed. Instead, anonymous shifts called open-shifts are used to cover any unavoidable under-coverage. The three main costs composing the objective function are: Over-coverage cost, open-shift usage cost, and minimum employees working hours violation penalty. A parallel large neighborhood search (LNS) metaheuristic for the multi-job employee scheduling problem is developed. Where a sub-scope denotes: a subset of the employees, a subset of the jobs and a continuous subset of the problem horizon. The LNS heuristic is defined by destroy and repair procedures. Our destroy procedure chooses sub-scopes coupled with a high cost in the objective function to be destroyed. When a solution sub-scope is destroyed, all shifts, occurring within the sub-scope horizon and worked by an employee belonging to the sub-scope, for one of the sub-scope jobs, are removed from the current solution schedule.Once the solution sub-scopes are destroyed, the repair operator tries to build an enhanced solution. Our proposed repair operator solves a MILP restricted to the destroyed sub-scopes. The parallel LNS destroy operator creates several disjoint sub-scopes, then each sub-scope is repaired in a different parallel thread. We compare the presented heuristic with the formal MILP solved within the commercial system WFC for Kronos Inc. Experimental results show that the parallel LNS algorithm can save up to an average of 80% in the computational time and 1.8% in the solution cost