Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
124
colonne à gauche de m ; 23 est la date la plus proche (“au plus tôt”) à laquelle peut
com men cer l’opé ra tion m.
En conti nuant ainsi, on arrive à mar quer la colonne F ; le nombre qui est indi qué
en tête de cette colonne indique la date au plus tôt d’achè ve ment de l’ensemble des
opé ra tions, c’est-à-dire la durée minimale du projet. Pour trou ver le che min cri tique,
il suf fit de reprendre dans le tableau, et en par tant de la fin, les opé ra tions enchaî nées
dont la ligne a fourni le nombre indi qué en tête de colonne. Ainsi, dans la colonne F,
c’est w ; dans la colonne w, c’est s ; dans la colonne s, c’est q ; etc.
Le graphe MPM illustre le problème de façon par faite, mais on se rend bien
compte qu’il n’est pas du tout néces saire de le tra cer pour résoudre le pro blème.
Remarque. Dans le cas où le graphe aurait un cir cuit (c’est- à-dire com por te rait
la contra dic tion signa lée plus haut), l’algo rithme s’arrê te rait de lui- même, car
on ne trou ve rait plus de colonne com plète, à un stade déter miné de son appli -
ca tion (voir l’exemple ci- dessous, tableau et graphe 4.17 ; ici k précède l qui
précède m ... qui précède k : k devrait être fini pour pouvoir commencer !).
12
k
n
m
m : 4
j : 5
k : 2
m : 4
: 3
Figure 4.17
4.3.3 Inter ven tion de modi fi ca tions : sou plesse de la
méthode MPM
Sup po sons main te nant que des modi fi ca tions inter viennent dans notre exemple :
– le tirage o peut com men cer lorsque la mise en pages n a été effec tuée seule ment à
moi tié ;
– le pliage q peut com men cer avec un déca lage d’une quin zaine seule ment sur le
début du tirage o, mais alors la durée de q est aug men tée de moi tié et passe donc
à 1
1
2 quin zaines. Cepen dant q est tou jours pré cé dée par n.
– on ne désire demander à l’auteur le prière d’insé rer et les listes d’envoi des exem
plaires de presse et des hom mages que lorsque le pliage est achevé : q pré cède
alors p.
– le bro chage r et la reliure s sont tou jours pré cé dés par o.
Si l’on entre prend de modi fier le graphe PERT,, on va devoir effa cer des arcs, en
créer de nou veaux et, en outre, intro duire de nou veaux évé ne ments. Nous ne repren -
drons ici le graphe qu’à par
tir de l’évé ne ment 11 (figure 4.18).
124
colonne à gauche de m ; 23 est la date la plus proche (“au plus tôt”) à laquelle peut
com men cer l’opé ra tion m.
En conti nuant ainsi, on arrive à mar quer la colonne F ; le nombre qui est indi qué
en tête de cette colonne indique la date au plus tôt d’achè ve ment de l’ensemble des
opé ra tions, c’est-à-dire la durée minimale du projet. Pour trou ver le che min cri tique,
il suf fit de reprendre dans le tableau, et en par tant de la fin, les opé ra tions enchaî nées
dont la ligne a fourni le nombre indi qué en tête de colonne. Ainsi, dans la colonne F,
c’est w ; dans la colonne w, c’est s ; dans la colonne s, c’est q ; etc.
Le graphe MPM illustre le problème de façon par faite, mais on se rend bien
compte qu’il n’est pas du tout néces saire de le tra cer pour résoudre le pro blème.
Remarque. Dans le cas où le graphe aurait un cir cuit (c’est- à-dire com por te rait
la contra dic tion signa lée plus haut), l’algo rithme s’arrê te rait de lui- même, car
on ne trou ve rait plus de colonne com plète, à un stade déter miné de son appli -
ca tion (voir l’exemple ci- dessous, tableau et graphe 4.17 ; ici k précède l qui
précède m ... qui précède k : k devrait être fini pour pouvoir commencer !).
12
k
n
m
m : 4
j : 5
k : 2
m : 4
: 3
Figure 4.17
4.3.3 Inter ven tion de modi fi ca tions : sou plesse de la
méthode MPM
Sup po sons main te nant que des modi fi ca tions inter viennent dans notre exemple :
– le tirage o peut com men cer lorsque la mise en pages n a été effec tuée seule ment à
moi tié ;
– le pliage q peut com men cer avec un déca lage d’une quin zaine seule ment sur le
début du tirage o, mais alors la durée de q est aug men tée de moi tié et passe donc
à 1
1
2 quin zaines. Cepen dant q est tou jours pré cé dée par n.
– on ne désire demander à l’auteur le prière d’insé rer et les listes d’envoi des exem
plaires de presse et des hom mages que lorsque le pliage est achevé : q pré cède
alors p.
– le bro chage r et la reliure s sont tou jours pré cé dés par o.
Si l’on entre prend de modi fier le graphe PERT,, on va devoir effa cer des arcs, en
créer de nou veaux et, en outre, intro duire de nou veaux évé ne ments. Nous ne repren -
drons ici le graphe qu’à par
tir de l’évé ne ment 11 (figure 4.18).