Problèmes de chemins
139
Ce chemin est appelé le chemin critique
4
. Le moindre retard dans l'exécution d'une
tâche de ce chemin entraîne une augmentation du délai minimal total des travaux.
Sur le graphe, on a indiqué en chaque sommet la valuation telle qu'elle ressort de
l'algorithme de Ford.
Le chemin critique, on le sait, est obtenu en partant du sommet sortie du graphe, et en
remontant vers l'entrée en sélectionnant à chaque fois l'arc tel que :
ij
i
j
t
=
si
est la valuation du sommet terminal de l'arc considéré
celle du sommet initial
la durée de la tâche correspondant
La valuation
indique donc que la tâche correspondant à l'arc ne pourra pas être
entreprise avant .
Les valuations données par l'algorithme de Ford sont alors les dates au plus tôt. Ces
dates au plus tôt sont attachées aux évènements représentés par les sommets du graphe,
et qui constituent les étapes successives de la réalisation du projet.
On définit aussi une date au plus tard pour chaque sommet : si l'évènement attaché à ce
sommet survient après cette date, la durée totale du projet augmente.
4 Il peut y avoir plusieurs chemins critiques.
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)
33
21
28
21
16
8
6
11
15
10
25
17