Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
120
date atten due de l’évé ne ment 9 : le che min cri tique a donc deux branches. Ses arcs
sont figurés par un trait double dans la Fig. 4.13.
Nous devrions ici reve nir sur la signi fi ca tion pra tique de la notion de che min
cri tique ; nous ver rions alors que, dans le pro blème pro posé, il existe des che mins
« presque cri tiques », sur tout vers la fin de l’ensemble des opé
ra tions ; nous consta
te rions pro ba ble ment que le décou page en tâches que nous avons réa lisé doit être
revu : comme nous l’avions annoncé pré cé dem ment, nous avons sim ple ment consi -
déré la liste de toutes les opé ra tions « élé men taires » ; cette méthode peut conduire à
des dif fi cul tés si l’on a des tâches de durée très inégale (exemple : 12 et 1/8, c’est
àdire dans un rap port de 1 à 100) ; pour cette rai son, il convient sou vent, en pra tique,
de regrou per cer taines tâches, de façon à obte nir des durées du même ordre.
L’une des dif fi
cul tés, déjà signalée plus haut, du tracé du graphe PERT réside
dans le fait que l’on peut être amené à y intro duire des tâches fic tives, pour tra duire
cor rec te ment les contraintes, sans intro duire de contraintes étran gères au pro blème
et donc ris quant de le faus ser. Ainsi, pour l’exemple ci- dessous :
Tâches
(opérations)
Contraintes
Durée
(en jours)
A
peut débuter au moins 5 jours après l’origine
16
B
peut débuter dès l’origine
14
C
peut débuter au moins 3 jours après l’origine
20
D
A, B finis
8
E
B fini
18
F
B, C finis
25
G
D, E, F finis
15
H
E fini ; C à moitié fini
17
I
D, E, F finis
10
La dif fi culté vient ici du fait que la tâche B est préa lable à la fois à D, Ε et F, mais
pas en com pa gnie des mêmes tâches : B et A pré cèdent D ; B seule pré cède Ε ; mais B et
C pré cèdent F ; il convient alors de ne pas réunir l’évé ne ment « fin de B » avec d’autres
évé ne ments, et de figu rer un arc du som met « fin de B » vers le som met « début de
D » (tracé en poin tillés ci dessous) ; de même, on a figuré un arc du som met « fin de
B » vers le som met « début de F » ; tout se passe comme si l’on avait une tâche fic tive,
notée w 3 , de durée nulle, pou vant com men cer lorsque B est finie, et préa lable au début
de D (et une tâche fic
tive w 4 préa lable à F).
De même, dans la liste des contraintes, si l’on remarque que D et F sont préa -
lables au démar rage des tâches G et I, il convient de remar quer que la tâche Ε pose
le même type de pro blème que la tâche B ci- dessus : elle inter vient, certes, conjoin -
te ment avec D et F, comme préa lable à G et I ; mais Ε inter vient avec la fin de la l
ère
moi tié de C, comme préa lable à H : pour évi ter l’intro duc tion de contraintes étran -
gères au pro
blème, il convient de lais ser l’évé ne ment « fin de C » libre, c’est- à-dire
de ne pas le fusion ner avec d’autres évé ne ments.
120
date atten due de l’évé ne ment 9 : le che min cri tique a donc deux branches. Ses arcs
sont figurés par un trait double dans la Fig. 4.13.
Nous devrions ici reve nir sur la signi fi ca tion pra tique de la notion de che min
cri tique ; nous ver rions alors que, dans le pro blème pro posé, il existe des che mins
« presque cri tiques », sur tout vers la fin de l’ensemble des opé
ra tions ; nous consta
te rions pro ba ble ment que le décou page en tâches que nous avons réa lisé doit être
revu : comme nous l’avions annoncé pré cé dem ment, nous avons sim ple ment consi -
déré la liste de toutes les opé ra tions « élé men taires » ; cette méthode peut conduire à
des dif fi cul tés si l’on a des tâches de durée très inégale (exemple : 12 et 1/8, c’est
àdire dans un rap port de 1 à 100) ; pour cette rai son, il convient sou vent, en pra tique,
de regrou per cer taines tâches, de façon à obte nir des durées du même ordre.
L’une des dif fi
cul tés, déjà signalée plus haut, du tracé du graphe PERT réside
dans le fait que l’on peut être amené à y intro duire des tâches fic tives, pour tra duire
cor rec te ment les contraintes, sans intro duire de contraintes étran gères au pro blème
et donc ris quant de le faus ser. Ainsi, pour l’exemple ci- dessous :
Tâches
(opérations)
Contraintes
Durée
(en jours)
A
peut débuter au moins 5 jours après l’origine
16
B
peut débuter dès l’origine
14
C
peut débuter au moins 3 jours après l’origine
20
D
A, B finis
8
E
B fini
18
F
B, C finis
25
G
D, E, F finis
15
H
E fini ; C à moitié fini
17
I
D, E, F finis
10
La dif fi culté vient ici du fait que la tâche B est préa lable à la fois à D, Ε et F, mais
pas en com pa gnie des mêmes tâches : B et A pré cèdent D ; B seule pré cède Ε ; mais B et
C pré cèdent F ; il convient alors de ne pas réunir l’évé ne ment « fin de B » avec d’autres
évé ne ments, et de figu rer un arc du som met « fin de B » vers le som met « début de
D » (tracé en poin tillés ci dessous) ; de même, on a figuré un arc du som met « fin de
B » vers le som met « début de F » ; tout se passe comme si l’on avait une tâche fic tive,
notée w 3 , de durée nulle, pou vant com men cer lorsque B est finie, et préa lable au début
de D (et une tâche fic
tive w 4 préa lable à F).
De même, dans la liste des contraintes, si l’on remarque que D et F sont préa -
lables au démar rage des tâches G et I, il convient de remar quer que la tâche Ε pose
le même type de pro blème que la tâche B ci- dessus : elle inter vient, certes, conjoin -
te ment avec D et F, comme préa lable à G et I ; mais Ε inter vient avec la fin de la l
ère
moi tié de C, comme préa lable à H : pour évi ter l’intro duc tion de contraintes étran -
gères au pro
blème, il convient de lais ser l’évé ne ment « fin de C » libre, c’est- à-dire
de ne pas le fusion ner avec d’autres évé ne ments.