"'O
0
c
:J
0
LI)
..--t
0
N
@
.......
..c
O'l
·;::::
>Q.
0
u
Chapitre 6 • Graphes et ordonnancement
180
Le chemin de durée minimale est (A,E,B,G) .
~~
A - - - D
4
-. B
4
-. G
0
4 3~76 7 10
E
3
5
4 ~ F
7
Figure 6.32
b) Le trajet le plus court est (A,E,F,G) de longueur 210 + 200 + 210 = 620 km.
@f4 Le chemin de longueur minimale est (A,C,E,H,l) de longueur 9 + 7 + 10
+ 13 = 39. Celui de longueur maximale est (A,C,D,G,H,l) de longueur 9 + 20 + 7
+ 12 + 13 = 61.
lftll:) a)S 0 ={A;B;C} , S, ={D;E} , S 2 ={F}, S 3 ={G}
b)
0 0
6
A
3
4
D
2
0
1
0 0
Début
B
-1l-6-F~'.- 6 -1-~ 3---+1-~ 1-9~i-9 ---+- l --+~11 t ~i~OI
3
5
4
E
0
1
6
c
Figure 6.33
c) Le chemin critique est (A ,F, G). La durée minimale de réalisation du projet est
10 jours .
d) La marge totale de E est MT( E) = T( E) - t( E) = 5 - 3 = 2 (jours). Cela veut dire
que l'on peut accepter au maximum deux jours de retard sur le départ de la tâche E
sans que cela ne retarde la date de fin du projet.
e) La marge libre de la tâche C est ML(C) = t(G)- t(C)-d(C) = 9- 0- 6 = 3 (jours).
C'est le retard maximum que l'on peut accepter sur la date de début de la tâche C
sans que cela ne retarde la date de début au plus tôt de chacune de la tâche G (la
seule tâche qui suit immédiatement C).