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.

Abstract

Problems involving staff schedules are becoming increasingly important in operational research. In recent decades, these problems have been widely studied in the literature and several methods have been described. They aim to build a work schedule for employees over a certain length of time that is called planning the horizon. A set of periods of equal duration cover the planning the horizon. A demand is defined according to these periods, representing the number of employees required for each period. Feasible shifts are assigned to employees to satisfy this given demand while respecting the collective agreements. Sometimes, it is not possible to meet the demand exactly. The number of employees assigned for a given period may be greater than the number of employees requested. We can say that we have an over-coverage of the demand at this period. Sometimes the number of employees assigned for a given period is less than the number of employees requested. In this case, there is demand under-coverage. We want to avoid creating undercoverage in order to ensure a good quality of service and creating over-coverage for paying unproductive working time. Different extensions of the classical personnel scheduling problem can be observed when specific real problems are considered. For example, if employees have multiple qualifications and can work on multiple jobs. In this case, it is important to know which employee is assigned to which job at a given time. In this project, we focus on building schedules for employees in large companies. Generally, large companies are divided into different departments and their workload peaks do not necessarily occur at the same time in all the departments. To avoid hiring new employees, these companies train employees to work in different departments. Each employee has a primary qualification and other qualifications. When an employee works outside the department of his primary qualification, we say that he/she is transferred. Certain rules such as limiting the number of transfers per day to one restrict the employee transfers. In practice, in the multi-department context, schedules are first made separately for each department. Then, employees who are not working in their original department and are qualified to work in other departments can be assigned to other departments to fill the gaps of the demand. However, it would be preferable to plan schedules in a global way. We started by developing a global model that allows to build a schedule for all departments in one step. But, this model is difficult to solve when the size of the problem increases, or even impossible in some cases. This paper presents a heuristic method for solving the problem of building staff schedules in a multi-department context with the possibility of sharing the workforce between the departments. More specifically, we are interested in transferring employees between departments. The proposed solution approach addresses the problem in two phases. Both phases are based on integer programming which is used to determine the assignment of each employee. The first phase solves a single-department problem for each department separately, without allowing the sharing of the workforce, i.e., without considering any transfer. Shifts are generated by department and we consider the employees that have this department as their original. This limits the number of shifts compared to the number of shifts for the global model. The second phase detects the under-coverage in each department and generates new potential shifts with transfers. It is a re-optimization of the solution obtained in the first phase with the addition of transfers. In this project, we begin by solving the problem in a global way by generating all types of possible shifts. The solution thus obtained is the optimal overall solution of the problem. Then for the second phase of the heuristic, three approaches are developed. In the first one, we don't allow the modification of the schedule resulting from the first phase. We add shifts with transfers without modifying the shifts of the first phase solution. This approach is very restrictive and it does not allow a great improvement of the solution obtained in the first phase. Then, in order to improve this solution, we can modify the initial solution of phase one by transforming the retained shifts into new shifts with transfers in a more flexible way. Transformations can be done by extending or reducing the shift length and adding some transfer periods. We obtain better results than those of the first approach but the optimal overall solution is only reached for a single test case. In order to achieve this solution, a third approach is proposed. For this approach, we add more flexibility to the shift generation method and we allow the modification of the first-phase solution by swapping employee shifts. We get good solutions in reasonable computing times. We consider that these solutions can be improved if we have better solutions of the first phase. Thus, towards the end of the thesis, special attention is paid to the improvement of the first phase. A new method to solve the first phase is proposed. The results obtained are improved and we manage to obtain solutions with less than 5% gap from the overall optimal solution in 75% of the test cases in reasonable computing times.