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.

Abstract

One of the classic problems of operational research is building customized work schedules. The optimization of working hours is intended to specify, for each day of the planning horizon, the sequence of the days of work and rest for each employee, to build shifts and to assign these shifts to employees. In a multi-activity context, this will also include the generation of activity sequences carried out in each shift. Most large companies are divided into departments. The management of the labor is done by assigning a set of employees in each of these departments. In addition, taking into account the professional development of employees, most are found assigned to more than one department and thus gain experience in several of them throughout their careers. Employees are therefore qualied to work in several departments within the same company. In this master's project, we focus on the computation of customized work schedules taking into account the possibility of transferring employees between departments. This occurs especially in large retail stores where employees can move from one department to another during their shift. It is therefore a multi-department environment where each department is mono-activity, that is, we consider a single activity by department. In addition, each employee can work at least in two departments in a shift. When assigned to two departments in the same shift, one of them must be his origin department. Each employee is qualied for a given set of departments outside the department to which he is originally attached. Moreover, the demand curves for each department and the qualifications of employees are known in advance. Also, the rules of the collective agreement as well as other rules will come into play to generate easible schedules. The main goal of the problem is to minimize the weighted sum of the total costs. These are mainly composed of four types of costs: (1) the cost associated with worked hours, (2) penalties for the transfer of sta between departments, (3) the total cost of under-coverage periods and (4) the total cost of over-coverage periods. Labor cost is calculated for each employee on the basis of the duration of his shift. The cost of transfer, meanwhile, is calculated on the basis of the duration of the transfer. For a given transfer period, this cost adds to the cost of work for the same period. Moreover, the satisfaction of the demand for labor is not always possible, especially in cases where demand exceeds the total number of employees available. For this, we allow under-coverage and over-coverage subject to penalties in the form of costs: these are under and over-coverage costs. While working and transfer costs depend on the employee making the shift and the length of the relevant periods, the costs of under and over-coverage depend on the department in which the under-coverage or over-coverage occurs. The main objective of this research project is therefore to propose a methodology for customized work schedules in order to eectively solve this problem. Real data sets of large size will be used to test and validate the various models and algorithms proposed. In practice, transfers are scheduled sequentially by hand after assigning departments. First this process is automated using a greedy algorithm. Then we suggest an improvement by replacing the greedy algorithm by a global model solved using Xpress-MP that process the whole problem as a MIP while keeping a global view during transfers calculations. The resolution of the global model allows to assign to each employee during the planning horizon, a set of feasible shifts. To do this, we provide an explicit enumeration of shifts including the start time, the duration of the shift, the duration of transfer and lacement of transfer for each shift. As a result, we are left with a very large number of possibilities that increases the complexity of the model and the solution time. Subsequently, we propose a two-phase heuristic approach to solve the problem when the solution of the global model fails for large instances. Indeed, enumerating explicitly all shifts can produce a very large number of options given high exibility on the shift start times, duration, transfer period placement. In the two-phase approach, a sequential model department by department is used in the first phase without allowing transfers. The resulting solution is then re-optimized in the second phase by allowing transfers between departments. We present the results for different models in the second phase. The sequential model department by department aims to assign to each employee a shift in its original department. An integer mathematical model solved by Xpress-MP is used. Dierent approaches are proposed for the second phase of re-optimization including a greedy algorithm algorithm and integer linear models also solved by Xpress -MP. Numerical experiments performed on various large data sets show that the processing time is signicantly lowered with the two-phase heuristic approach. In addition, using this twophase heuristic approach, we are able to cover the total demand at 99.8%. It also improves the results compared to the greedy algorithm which reflects what is done in practice. However, the quality of solutions is greatly deteriorated (by about 30%) for smaller sets. Moreover, tests show that the heuristic could be even better if we question the internal shifts. For larger instances encountered in practical case, the two-phase heuristic approach provides solutions in very acceptable time, namely, less than 2 minutes for instances of 8 departments and 191 employees.