Jean Damay
doctorant 2ème année LIMOS Clermont-Ferrand
 e-mail:  damay@isima.fr

Le Problème d'Ordonnancement de Projet avec Contraintes de Ressources
(RCPSP) consiste à planifier un ensemble d'activités contraintes par des
relations de précédence, et par des seuils de ressources. Chacune de ces
activités doit être exécutée pendant une durée donnée et nécessite pendant
son exécution une quantité de ressources donnée. Le but est de déterminer un
ordonnancement réalisable en minimisant le makespan.


Des bornes inférieures à la solution optimale de ce problème NP-difficile
ont été déterminées par Mingozzi et al en 1998, et Brucker et al en 2000, en
se basant sur une nouvelle formulation mathématique du problème : les
contraintes de préemption et de précédence sont relâchées, et on considère
alors des ensembles d'activités exécutables simultanément sur un intervalle
de temps à déterminer (des antichaînes du graphe de précédence qui ne
violent pas les contraintes de ressources). Ceci fait donc appel aux notions
de Propagation de Contraintes Temporelles, mais aussi et surtout de
Programmation Linéaire associée à cette formulation par antichaînes, à
laquelle on adjoint une méthode de Génération de Colonnes. Une colonne
correspond à une antichaîne dite valide.


Notre approche reprend cette modélisation et tente de donner, outre les
bornes inférieures évoquées, des bornes supérieures aux solutions des
problèmes respectivement préemptif et non-préemptif. Pour cela, on fait
appel à des algorithmes de tests couplés au programme linéaire, qui vont
déceler si les antichaînes que l'on propose pour rentrer en base courante
contiennent ou non un circuit, et/ou imposent ou non une préemption. On
utilise la théorie des graphes, ainsi qu'un algorithme spécifique de
détection d'intervalle-représentabilité de la famille des antichaînes en
base. Des résultats préliminaires seront présentés sur les jeux d'essai
classiques du RCPSP.