Méthodes de résolution pour un problème de gestion de projet multi-compétence
Institution:
ToursDisciplines:
Directors:
Abstract EN:
Ce document porte sur le problème de gestion de projet multi-compétence: il s'agit d'ordonnancer un projet dont on cherche à minimiser la durée, sous contraintes de ressources maîtrisant différentes compétences requises par les activités du projet. Nous présentons la définition du problème ainsi qu'un modèle linéaire pour celui-ci. L'étude des spécificités de ce problème nous amène à proposer des méthodes de résolution adaptées. Nous introduisons d’abord des bornes inférieures, puis différentes méthodes heuristiques : méthodes de placement série ou parallèle, basées sur une liste de priorité, puis une méthode utilisant le modèle linéaire. Par la suite, nous introduisons des méthodes de résolution de type méta-heuristique : méthode tabou, algorithmes génétiques. Enfin, nous présentons une procédure par séparation et évaluation, dont le schéma de branchement est basé sur les fenêtres d'exécution des activités que l'on réduit au cours de l'arborescence. A chaque feuille obtenue, il est alors nécessaire de résoudre un problème à dates de début fixées, pour lequel nous avons établit plusieurs méthodes de résolution exactes qui sont également présentées.
Abstract FR:
This document deals with the multi-skill project scheduling problem: a project has to be scheduled in order to minimize the makespan. The resources may master several skills among all those needed by activities. First of all, we introduce the problem by a formal definition, and a linear program. Then, according to differences with other classical project scheduling problems, we develop specific methods. Several lower bounds are introduced. Then, we define some heuristic methods based on: serial schedule scheme or parallel schedule scheme, which use a priority list. Those methods are followed by a linear programming formulation, and some meta-heuristic method: a tabu search and two genetic algorithms. Finally, we introduce a branch-and-bound procedure to build optimal solutions. The branching scheme is based on time-windows of activities. So, each time a leaf node is reached, a fixed job scheduling problem with multiple skills has to be solved. We use some methods to optimally solve this problem, which are detailed in this document.