Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
116
des graphes. Ce sont la méthode amé ri caine CPM (Critical Path Method), avec sa
variante, incluant d’éven tuelles don nées aléa toires, PERT (Program Evaluation and
Review Tech nique ou Program Evaluation Research Task), d’une part, et la méthode
fran çaise des poten tiels (MPM), d’autre part. Désor mais, le sigle PERT a sup planté
celui de CPM, même en l’absence de don nées (durées) aléa toires.
Pre nant en compte seule ment les contraintes du type poten tiel ou se rame nant à
ce type, les méthodes PERT ou MPM per mettent :
– d’éta blir un ordon nan ce ment, dès lors qu’aucune contrainte n’est contra dic toire avec
une autre ; ce qui revient à calculer pour chaque tâche i sa date de début au plus tôt t i :
– de minimi ser le temps total néces saire à la réa li sa tion de l’objec tif : tel est le cri tère ;
– de déter mi ner les tâches cri tiques, c’est àdire celles dont l’exé cu tion ne peut être
ni retar dée ni ralen tie, sans que la fin de l’ensemble des tra vaux ne soit déca lée du
temps cor res pon dant.
– d’éva luer les marges des tâches non cri tiques.
Des méthodes ou algo rithmes annexes per mettent, en outre, cer tains para mé trages :
obten tion du coût le plus bas par amé na ge ment des tâches non cri tiques ; accé lé ra tion
du pro gramme ini tial au moindre coût par rac cour cis se ment du temps d’exé cu tion des
tâches cri tiques dont la com pres sion tem po relle revient rela ti ve ment le moins cher ; etc.
La méthode PERT est très répan due en pra tique, alors que la méthode des poten -
tiels est plus facile à mettre en œuvre.
Pour uti li ser la méthode PERT, on construit un graphe orienté, sans boucle, dont les
som mets consti tuent des évé ne ments (étapes de la réa li sa tion ou, si l’on veut, objec tifs
inter mé diaires, inconnus au départ) et les arcs repré sentent les opé ra tions (tâches élé -
men taires en les quelles on a décom posé le pro ces sus de réa li sa tion de l’objec tif final).
Les arcs étant valués par les durées d’exé cu tion, il sera aisé, une fois le graphe tracé, de
rechercher, au moyen d’un algo rithme approp rié, le che min de valeur maximale dans le
graphe et d’obte nir ainsi le (ou les) chemins(s) critique(s), comme nous le ver rons dans
l’exemple ci- dessous, d’autant que – le plus sou vent – il ne com porte pas de cir cuits.
Mais nous ver
rons que le tracé du graphe PERT peut com
por ter quelques dif
fi cul tés.
La méthode des poten tiels (MPM) repose sur un graphe dif fé rent, dont le tracé
est immé diat : les som mets repré sentent les opé ra tions et les arcs, les contraintes ;
tout arc est valué par un nombre indi quant la durée mini male devant s’écou ler entre
le début de la tâche associée à son extré mité ini tiale et celui de la tâche associée à son
extré mité ter mi nale. En pra tique, sou vent ce graphe n’est pas tracé, il est simplement
repré senté par une struc ture de don nées adap tée (liste des pré dé ces seurs). Contrai re -
ment au PERT, ici tous les som mets et arcs sont connus au départ.
Nous exa mi ne rons sur un même exemple l’une et l’autre des méthodes.
Exemple. Un édi teur veut pas ser com mande d’un ouvrage tech nique à un auteur
scien ti fique. Les étapes à suivre sont indi quées dans le tableau ci
après, avec leur
durée et la men tion des opé ra tions qui doivent pré cé der cha cune d’entre elles.
116
des graphes. Ce sont la méthode amé ri caine CPM (Critical Path Method), avec sa
variante, incluant d’éven tuelles don nées aléa toires, PERT (Program Evaluation and
Review Tech nique ou Program Evaluation Research Task), d’une part, et la méthode
fran çaise des poten tiels (MPM), d’autre part. Désor mais, le sigle PERT a sup planté
celui de CPM, même en l’absence de don nées (durées) aléa toires.
Pre nant en compte seule ment les contraintes du type poten tiel ou se rame nant à
ce type, les méthodes PERT ou MPM per mettent :
– d’éta blir un ordon nan ce ment, dès lors qu’aucune contrainte n’est contra dic toire avec
une autre ; ce qui revient à calculer pour chaque tâche i sa date de début au plus tôt t i :
– de minimi ser le temps total néces saire à la réa li sa tion de l’objec tif : tel est le cri tère ;
– de déter mi ner les tâches cri tiques, c’est àdire celles dont l’exé cu tion ne peut être
ni retar dée ni ralen tie, sans que la fin de l’ensemble des tra vaux ne soit déca lée du
temps cor res pon dant.
– d’éva luer les marges des tâches non cri tiques.
Des méthodes ou algo rithmes annexes per mettent, en outre, cer tains para mé trages :
obten tion du coût le plus bas par amé na ge ment des tâches non cri tiques ; accé lé ra tion
du pro gramme ini tial au moindre coût par rac cour cis se ment du temps d’exé cu tion des
tâches cri tiques dont la com pres sion tem po relle revient rela ti ve ment le moins cher ; etc.
La méthode PERT est très répan due en pra tique, alors que la méthode des poten -
tiels est plus facile à mettre en œuvre.
Pour uti li ser la méthode PERT, on construit un graphe orienté, sans boucle, dont les
som mets consti tuent des évé ne ments (étapes de la réa li sa tion ou, si l’on veut, objec tifs
inter mé diaires, inconnus au départ) et les arcs repré sentent les opé ra tions (tâches élé -
men taires en les quelles on a décom posé le pro ces sus de réa li sa tion de l’objec tif final).
Les arcs étant valués par les durées d’exé cu tion, il sera aisé, une fois le graphe tracé, de
rechercher, au moyen d’un algo rithme approp rié, le che min de valeur maximale dans le
graphe et d’obte nir ainsi le (ou les) chemins(s) critique(s), comme nous le ver rons dans
l’exemple ci- dessous, d’autant que – le plus sou vent – il ne com porte pas de cir cuits.
Mais nous ver
rons que le tracé du graphe PERT peut com
por ter quelques dif
fi cul tés.
La méthode des poten tiels (MPM) repose sur un graphe dif fé rent, dont le tracé
est immé diat : les som mets repré sentent les opé ra tions et les arcs, les contraintes ;
tout arc est valué par un nombre indi quant la durée mini male devant s’écou ler entre
le début de la tâche associée à son extré mité ini tiale et celui de la tâche associée à son
extré mité ter mi nale. En pra tique, sou vent ce graphe n’est pas tracé, il est simplement
repré senté par une struc ture de don nées adap tée (liste des pré dé ces seurs). Contrai re -
ment au PERT, ici tous les som mets et arcs sont connus au départ.
Nous exa mi ne rons sur un même exemple l’une et l’autre des méthodes.
Exemple. Un édi teur veut pas ser com mande d’un ouvrage tech nique à un auteur
scien ti fique. Les étapes à suivre sont indi quées dans le tableau ci
après, avec leur
durée et la men tion des opé ra tions qui doivent pré cé der cha cune d’entre elles.