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.