Exact and Heuristic Methods for Multi-Activity Tour Scheduling Problems
Méthodes exactes et heuristiques pour des problèmes de planification du personnel avec plusieurs activités
Résumé
Personnel scheduling problems encompass a large collection of optimization challenges thatseveral organizations need to face. One of the first classifications proposed divides theseproblems into: days-o_ scheduling, shift scheduling, and tour scheduling. The first concernsthe determination of working and rest days; the second defines the shifts to be assigned; thethird integrates days-o_ into shift scheduling. The current thesis addresses the tour scheduling problem with a multi-activity context arising in restaurant business, which was provided by the company Horizontal Software. As such, the main goal is to define the working days and the shifts, along with the specification of the activities in each time period. This problem is also characterized by a high degree of flexibility, mainly due to the introduction of a long pause (interruption), and heterogeneity, determined by conditions from employees (skills, availabilities, contract regulations, and pre-assignments). The problem is tackled by a Branch-and-Price algorithm, which is based on column generation. A dual ascent heuristic is implemented to speed up its convergence, and a constraint and dynamic programming based method is proposed for generating schedules. To address the large-scale instances, various heuristics are presented, based on column generation, large neighborhood search and tabu search. To assess the performance of the proposed method,computational experiments are conducted on instances from the literature and on real-worldinstances that were provided by Horizontal Software.
La planification du personnel constitue une vaste classe de problèmes d'optimisation rencontrées dans différentes organisations. L'une des premières classifications proposées divise ces problèmes en days-off scheduling, shift scheduling et tour scheduling. Le premier concerne la détermination des jours de travail et de repos, le deuxième définit les horaires de travail, et le troisième intègre les deux. Cette thèse découle de la volonté de la société Horizontal Software de résoudre l'un des problèmes difficiles rencontrés dans la restauration. Le problème relève de la catégorie du tour scheduling dans un contexte multi-activités, où l'objectif est la définition des jours et des horaires de travail, ainsi que la spécification des activités dans chaque période. Ce problème présente un degré élevé de flexibilité et d'hétérogénéité. La première est causée par l'introduction d'une longue pause (coupure), tandis que la deuxième est due aux compétences, aux disponibilités, aux contrats et aux pré-affectations des employés. Le problème est résolu par une méthode du type Branch-and-Price, dont l'élément clé est la génération de colonnes. Une heuristique dual ascent a été proposée pour accélérer sa convergence, et une méthode basée sur la programmation dynamique et par contraintes a été proposée pour générer des plannings individuels. Afin de traiter les instances de grande taille, différentes heuristiques ont été développées, basées sur la génération de colonnes, la recherche à voisinage large et tabou. Des tests expérimentaux sur des instances de la littérature et réelle ont été effectués afin d'évaluer les performances des méthodes proposées.
Domaines
Ordinateur et société [cs.CY]
Origine : Version validée par le jury (STAR)
Loading...