Note publique d'information : 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.
Note publique d'information : 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.
paprika.idref.fr
data.idref.fr
Documentation
