Task Scheduling and Activity Assignment to Work Shifts with Schedule Flexibility and Employee Preference Satisfaction

La planification des horaires de personnel travaillant sur des quarts est importante dans le secteur des services, car elle influe directement sur les coûts et la qualité du service à la clientèle. Elle constitue également un problème d'optimisation combinatoire complexe, qui nécessite des outils sophistiqués pour le résoudre. Cette thèse de doctorat porte sur trois variantes du problème de planification des horaires de personnel. Après une brève introduction et une revue de la littérature dans les chapitres 1 et 2, les trois variantes sont étudiées dans les trois chapitres principaux. Les deux premiers chapitres principaux abordent le problème d'affecter des tâches et des activités aux quarts dans un environnement flexible (TSAASAF), i.e, avec la possibilité d'ajuster les heures des quarts de travail. Dans le secteur des services, les employés effectuent des quarts de travail et sont affectés à des activités interruptibles et à des tâches sans interruption au cours de leurs quarts de travail, à l'exclusion des temps de pause. Chaque employé ne peut effectuer plus d'une tâche ou d'une activité au même moment, et a droit à un seul bloc de pause au cours de son quart de travail. Une activité est un travail avec une demande continue, exprimée comme le nombre d'employés requis pour chaque période de l'horizon de planification. Selon les règles de travail, la durée d'une affectation à une activité doit être dans un intervalle donné. Chaque tâche a une durée fixe et doit être exécutée une seule fois par un seul employé qualifié, dans une fenêtre de temps spécifiée. Les quarts de travail des employés réguliers sont souvent construits quelques semaines avant le début des opérations, lorsque les demandes des activités et des tâches sont incertaines. Quelques jours avant les opérations, lorsque des précisions sur les demandes sont obtenues, les horaires planifiés peuvent être légèrement modifiés, et afin de satisfaire la demande, des employés temporaires peuvent être programmés. Les modifications possibles pour les quarts de travail sont les prolongations des quarts et les déplacements des pauses-repas. Dans le chapitre 3, nous nous intéressons à une version simple du problème TSAASAF. Le problème d'affecter des activités dans les quarts de travail flexibles (AAFF) consiste à attribuer uniquement les activités aux quarts de travail réguliers, alors qu'aucun employé temporaire n'est considéré. Une procédure de génération de colonnes heuristique, incorporée dans une procédure d'horizon fuyant, détermine les quarts de travail finaux, et leur attribue des activités. Les résultats obtenus sur des instances générées aléatoirement sont rapportés pour évaluer la validité de la méthode de résolution proposée. Les instances générées sont regroupées dans deux classes de petite taille et une troisième de taille moyenne. La comparaison du nombre de sous-couvertures obtenues (la partie principale de la fonction objectif), avec et sans flexibilité, montre des améliorations de la couverture qui peuvent être obtenues en utilisant les options de flexibilité: le nombre de sous-couvertures est réduit, en moyenne, de 68%, 96%, et 70% dans les première, deuxième et troisième classes, respectivement. Bien que les temps de calcul sont beaucoup plus élevés avec la méthode proposée, nous démontrons dans le chapitre 4 qu'en supprimant délibérément à l'avance les options jugées inutiles pour les extensions des quarts de travail, il est possible de réduire la complexité du problème AAFF, dans l'espoir d'obtenir un meilleur temps de calcul. D'autre part, une version complète du problème TSAASAF est introduite dans le chapitre 4. Celle-ci permet de résoudre le problème d'affecter des tâches et des activités aux travailleurs temporaires et aux quarts de travail flexibles des employés réguliers à temps plein (ATTFF). Afin de produire des solutions de bonne qualité en des temps de calcul rapides pour les instances de grande taille, nous développons une méthode heuristique en deux phases. Dans la première phase, un modèle approximatif de programmation en nombres entiers mixte est utilisé pour suggérer des quarts de travail temporaires et des extensions de quarts de travail réguliers, et pour planifier et affecter les tâches. Dans la deuxième phase, une procédure de génération de colonnes heuristique intégrée dans une procédure d'horizon fuyant décide les prolongations et les heures de pause des quarts de travail réguliers, sélectionne les quarts de travail temporaires et leur assigne des activités. Cette heuristique a été testée sur des instances de moyenne à grande taille générées aléatoirement, pour comparer les différentes variantes de flexibilité. Les résultats montrent que les flexibilités additionnelles peuvent réduire considérablement le nombre de sous-couvertures des demandes d'activités et que les solutions peuvent être calculées en temps raisonnables. Afin d'évaluer la qualité des solutions, nous avons ajouté une variante qui considère toutes les flexibilités sauf le repositionnement des pauses. Sachant que le repositionnement des pauses n'est pas considéré dans le modèle approximatif de la première phase, pour cette variante, la valeur de la solution de la première phase sert de borne inférieure pour la solution finale de la deuxième phase. Dans le chapitre 5, le problème d'affecter des activités aux quarts de travail basé sur les préférences des employés (BPAA) est introduit. Nous supposons que chaque employé fournit ses préférences sur les activités pour lesquelles il est qualifié. Nous cherchons un outil de résolution du problème PBAA qui, en premier lieu, vise le coût minimum de sous-couverture et, en second lieu, assure la satisfaction maximale des employés à l'égard de leurs préférences individuelles. Ce second objectif n'est pas moins important que de simplement fournir les ressources suffisantes pour répondre efficacement aux besoins des clients. En effet, un employé satisfait est plus efficace qu'un autre qui ne l'est pas. Ainsi, la qualité du service a une grande importance de même que le nombre d'employés disponibles pour offrir le service dans les entreprises pour lesquelles conserver ses clients est un facteur clé pour la prospérité de l'entreprise. Pour une meilleure rentabilité, les entreprises ont besoin de satisfaire leurs clients et pour réaliser cet objectif, ils doivent satisfaire leurs propres employés. Tout d'abord, une mesure de taux de satisfaction est définie pour quantifier la satisfaction des employés, ensuite le deuxième objectif est défini comme la maximisation de la moyenne des taux de satisfaction pour les employés. Les solutions qui violent le coût minimum par un petit pourcentage, mais comprennent des affectations plus satisfaisantes pour les employés sont également intéressantes en ce qui concerne les propriétés de dominance des solutions dans le cas d'un problème avec plusieurs objectifs conflictuels. Une procédure de génération de colonnes heuristique en deux phases est proposée. Elle mémorise le nombre minimum de sous-couvertures dans la première phase, puis ré-optimise la solution avec la deuxième fonction objectif dans la deuxième phase, tout en laissant le décideur définir l'augmentation acceptable dans le nombre minimal de sous-couvertures. Dans les deux phases, la génération de colonnes est, à nouveau, incorporée dans une procédure d'horizon fuyant.La capacité de cette méthode à fournir un ensemble de solutions nondominées est comparée à une méthode de pondération qui transforme le problème en un problème mono-objectif avec une somme pondérée des différents objectifs. Les décideurs ont besoin d'un outil flexible qui soit assez efficace, en pratique pour obtenir des solutions dans une plage acceptable pour chaque objectif. Ainsi, ils seront en mesure de choisir la meilleure solution qui satisfait leurs besoins variables, alors qu'il leur est facile de modéliser leurs préférences dans les objectifs. En pratique, cette méthode est meilleure que la méthode de pondération. D'une part, il n'y a pas le difficulté de choisir les poids comme avec la méthode de pondération. D'autre part, elle donne au décideur plus de contrôle dans la recherche des solutions avec les sous-couvertures légèrement au-dessus du minimum, en contrepartie de mieux satisfaire les préférences des employés. Cependant, la résolution d'un problème prend plus de temps de calcul par cette méthode que par la méthode de pondération. Ainsi, certaines stratégies sont appliquées pour réduire les temps de calcul de la méthode proposée, mais sans succès. D'autre part, quand les coûts de sous-couverture varient d'une activité à l'autre, cette méthode s'avère meilleure. Étant donné qu'il n'y a pas de priorité entre les employés, la méthode en deux phases peut assurer un équilibre dans la satisfaction des employés en affectant des poids aux employés proportionnellement inverse à leur degré de satisfaction à ce jour, dans chaque tranche de temps de la procédure d'horizon fuyant. Les principales contributions de cette thèse sont d'abord l'étude de trois variantes du problème d'affectation des activités aux quarts de travail, soit les problèmes AAFF, ATTFF et BPAA, qui n'ont pas encore été abordés dans la littérature; et, deuxièmement, le développement d'heuristiques de programmation mathématique sophistiquées, qui fournissent des solutions de bonne qualité en des temps de calcul acceptables. Par conséquent, cette recherche fournit aux industries de services des outils efficaces pour faire face aux changements de dernière minute dans la demande en utilisant différentes flexibilités dans le processus de planification des horaires de personnel, réduisant les coûts d'opérations et les temps de planification. D'autre part, elle introduit une ligne directrice aux entreprises, leur permettant d'intégrer autant que possible les préférences des employés dans la construction d'horaires de travail satisfaisants, tout en gardant les coûts à des niveaux minimaux.

Abstract

Personnel scheduling is important in the service industry, as it impacts directly the costs and the customer service quality. It is also a complex combinatorial optimization problem, that requires sophisticated tools for solving it. This doctoral dissertation addresses three variants of personnel scheduling problem. After a brief introduction and a literature review in Chapters 1 and 2, these three variants are studied in three main chapters. The first two main chapters address the task scheduling and activity assignment with shift adjustments under a flexible working environment (TSAASAF). In the service industry, the employees perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts working time, excluding the break times. Each employee can not perform more than one task or activity at a time, and is assigned a single break during his/her work shift. An activity is a work with continuous demand expressed as the number of employees required for each period of the planning horizon. According to the labor rules, the duration of an assignment to any activity should be within a given interval. Each task has a fixed duration and should be performed by just one qualified employee within a specified time window. The work shifts of the regular employees are often constructed a few weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands unveil with more accuracy, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving their meal breaks are considered. In Chapter 3, we are interested in a simple version of the TSAASAF problem. The activity assignment problem with flexible full-time shifts (AAFF) involves assigning only activities to the scheduled work shifts while no temporary employee is considered. A column generation heuristic embedded into a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method. Generated instances are categorized in two small-sized and one medium-sized classes. Comparing the number of undercoverings obtained (the main part of the objective function) with and without flexibilities shows the coverage improvements that can be achieved by using flexibilities: the number of undercoverings is reduced, on average, by 68%, 96%, and 70% in the first, second and third classes, respectively. Although the computational times are much higher with the proposed method, we show in Chapter 4 that by removing the unhelpful options for shift extensions deliberately in advance, it is possible to reduce the complexity of AAFF problem, in hopes of getting better computational times. Besides, a complete version of the TSAASAF problem is introduced in Chapter 4. This version solves the task scheduling and activity assignment to temporary and flexible regular full-time shifts (ATTFF) problem. In order to produce good quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic method. In the first phase, an approximate mixed integer programming model is used to suggest temporary shifts and extensions to regular shifts, and to schedule and assign the tasks. In the second phase, a column generation heuristic embedded in a rolling horizon procedure decides about the regular shift extensions and break placements, selects the temporary shifts and assigns activities to them. This heuristic is tested on randomly generated medium to large-sized instances to compare different variants of flexibility. The computational results show that the additional flexibilities can yield substantial savings in the number of activity demand undercoverings and that the solutions can be computed in reasonable computational times. To assess the quality of final solutions, we added a variant which considers all flexibilities except break repositioning. Knowing that break movements are not considered in the first-phase approximation model, for this variant, the value of the first-phase solution serves as a lower bound for the final solution of the second phase. In Chapter 5, the preference-based activity assignment to work shifts (PBAA) problem is introduced. We suppose that each employee gives his/her preferences over the activities he/she is skilled for. We look for a tool to solve the PBAA problem, which in the first place, incurs the minimum undercovering cost, and in the second place, provides the maximum employee satisfaction with respect to their individual preferences. This latter objective is not less important than simply providing enough resources for responding efficiently to the customers needs. In fact, a satisfied employee is more efficient than an unsatisfied one. So, the quality of service has a great importance as well as the number of available employees to offer the service, in the companies for which keeping customers is a key factor to a successful business. For an improved profitability, companies need to satisfy their customers and to achieve this objective, they must satisfy their own employees. First, a satisfaction rate measure is defined to quantify the employee satisfaction, then the second objective is defined as the maximization of the average of satisfaction rates for employees. Solutions which violate the minimum cost by a small percentage, but include the more satisfactory assignments for employees are also interesting with respect to the dominance properties of the solutions for a problem with multiple conflicting objectives. A two-phase column generation heuristic is proposed, which memorizes the minimized number of under-coverings in the first phase, then re-optimizes the solution with the second objective function in the second phase while letting the decision maker define the acceptable increase in the minimum number of undercoverings. In both phases, column generation is again embedded into a rolling horizon procedure. The capacity of this method in providing a set of nondominated solutions is compared with a weighting method which transforms the problem to a single-objective one with a weighted sum of different objectives. The decision makers need a flexible tool which is efficient enough, in practice, to obtain solutions within the acceptable range for each objective. Thus, they will be able to select the best solution which fits their varying needs, while it is easy for them to interpret their preferences over the objectives. This method outperforms the weighting method, in terms of practicality. On the one hand, it does not have the weighting method's difficulty to set the weights. On the other hand, it gives the decision maker more control to find the solutions with the undercoverings slightly above the minimum, in return for better satisfying the employee preferences. However, it takes more computational time to solve a problem by this method than with the weighting method. Hence, some strategies are applied to reduce the computational time of the proposed method, which are not successful. Besides, when the undercovering costs vary from one activity to the other, this method proves to perform better. Given that there is no seniority ranking for employees, the two-phase method can provide a balance in satisfying the employees by giving weights to the employees with inverse relationship with their satisfaction so far, in each time slice of the rolling horizon procedure. The main contributions of this thesis are first the study of three variants of activity assignment to work shifts problem, as the AAFF, ATTFF and PBAA problems, not previously studied in the literature, and second the development of state-of-the-art mathematical programming heuristics that yield good quality solutions in acceptable computational times. Hence, this research provides the service industries with efficient tools to deal with the last-minute changes in demands using different flexibilities in the personnel scheduling process, reducing the operations costs and planning times. On the other hand, it introduces a guideline to companies to incorporate as much as possible the employees preferences in constructing satisfactory work schedules while keeping the costs at minimum levels.