Problèmes de chemins
137
On voit que l'on a été obligé d'ajouter trois tâches fictives pour éviter d'introduire des
contraintes inexistantes; cette opération peut devenir complexe si le nombre de tâches
élémentaires est important.
Remarquons qu'un tel graphe est obligatoirement :
-
connexe, sinon l'on pourrait décomposer le projet en deux sous-projets
indépendants,
-
sans circuit, car cela impliquerait des contradictions dans les contraintes de
succession.
b) Dans la méthode des potentiels, le graphe que l'on dessine a pour sommets les tâches
et pour arcs les contraintes, ici, les contraintes de succession. Les arcs sont valués par le
délai qui doit s'écouler entre le début de la tâche correspondant à l'extrémité initiale et le
début de la tâche correspondant à l'extrémité finale; dans l'ensemble traité, ces valuations
sont simplement les durées des tâches associées aux extrémités initiales des arcs.
On introduit un sommet terminal indiquant la fin des opérations et un sommet initial,
début des opérations. Dans ces conditions, le graphe de la méthode des potentiels,
pour l'exemple étudié peut donc être tracé de la façon suivante :
A(6)
C(5)
D(4)
B(4)
F(7)
E(6)
O(3)
H(2)
I(5)
0
N(7)
M(5)
K(7)
J(2)
L(6)
0
0
G(8)