142
Recherche opérationnelle
Pour l'exemple considéré, le début de ce tableau donne :
A
B
C
D
E
F
G
H
I
J
0 Y : 0 A : 6 A : 6 C : 5 D : 4 B : 4 D : 4
F : 7
K : 7
L : 7
G : 8 G : 8
N : 7
A : 6
Lorsqu'une opération n'est précédée d'aucune autre (comme A) on la fait précéder par
l'opération fictive Y, de durée nulle.
Sur ce tableau, on va calculer facilement les dates au plus tôt et déterminer le chemin
critique. On notera les dates au plus tôt, d'une part devant le sigle de chaque tâche, en
tête de colonne, d'autre part devant les tâches des sous-colonnes.
On commence par affecter 0 à Y comme date au plus tôt. Lorsque la sous-colonne des
dates au plus tôt d'une colonne donnée est entièrement remplie, on prendra pour date de
début au plus tôt de la tâche associée à la colonne le nombre calculé de la façon suivante:
pour chaque tâche antécédente (donc figurant à droite) on ajoute sa date au plus tôt
(figurant à gauche) et sa durée.
On prend le plus grand des nombres ainsi calculés, et le nombre obtenu constitue la date
au plus tôt de la tâche correspondant à la colonne examinée. Il est évident que cette
opération correspond exactement à celle que l'on pourrait faire sur le graphe :
si
désigne les tâches antécédentes à la tâche , si désigne la date au plus tôt de
la tâche , si
représente la valuation de l'arc reliant à (durée de la tâche ) la date
au plus tôt est égale à :
Le tableau complètement rempli donne :
0
A
6 B
6 C
11 D
15 E
10 F
17 G
25 H
28 I
6 J
0
Y : 0 0 A:6 0 A:6
6 C:5 11D:4 6 B:4 11 D:4
10 F:7
8 K:7
10 L :7
17 G:8
17 G:8
21 N:7
0 A:6