Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
126
On modi fie le graphe MPM par des addi tions d’arcs et des rem pla ce ments de
nombres (figure 4.19). Noter que, lorsque l’on rem place une opé
ra tion par une opé
ra tion par tielle, dimi nuant ainsi la valuation d’un arc, il faut veiller à ce que les opé -
ra tions qui suivent l’achè ve ment total de cette opé ra tion ne com mencent pas avant
cet achè ve ment. Par exemple q ne peut com men cer que si n (durée totale 1) est ter -
mi née ; r et s que si ο est ache vée.
Les faci li tés évi dentes de la méthode des poten tiels la font pré fé rer par les
chercheurs opé ra tion nels, même si les résultats sont parfois “PERT-isés” pour
complaire à certains utilisateurs...
Le cal cul fait appa raître une notion très inté res sante ; certes on ne peut pas retar -
der l’exé cu tion des tâches cri tiques, sous peine de faire prendre un retard cor res pon -
dant à l’achè ve ment de l’ouvrage, mais il est bien clair qu’une opé ra tion non cri tique
peut au contraire soit débu ter après sa date au plus tôt, soit être ralen tie : nous allons
quan ti
fier cette notion (« marge ») au para graphe ci
dessous.
4.3.4 Cal culs pra tiques. Marges
Un des algo rithmes les plus employés pour la recherche du che min cri tique dans la
méthode PERT, comme dans la méthode MPM, est l’algo rithme de Bellmann : dans
l’un et l’autre cas, avec les contraintes potentielles utilisées jusqu’ici, le graphe asso -
cié ne com porte pas de cir cuit.
1
Dans la méthode PERT, u i désigne la date atten due (ou date au plus tôt) pour
l’évé ne ment i (c’est une inconnue), et d ij la durée de l’opé ra tion (i, j) (c’est une don -
née). Le cal cul de ces dates, même direc te ment sur le graphe pour notre exemple,
revient à appli quer la for mule :
u j 5 max
iPG
2 (j)
3u i 1 d ij 4.
La date au plus tard, notée u
*
i pour l’évé ne ment i, est égale, pour tout évé ne ment
(som met) i d’un che min cri
tique ζ, à la date au plus tôt : u
*
i 5 u i , si iPz .
En dehors d’un che min cri tique, les dates au plus tard se cal culent par la for mule :
u
*
i 5 min
jPG
1 (i)
3u
*
j 2 d ij 4.
Le cal cul fait appa raître une notion très inté res sante ; il est bien clair qu’une tâche
non cri tique (i, j) peut, au contraire, soit débu ter après la date u i mar quant son début
pos sible au plus tôt, soit être exé cu tée plus len te ment que prévu. Ainsi, la tâche (4,
10) peut com men cer à u 4 5 16, mais elle ne dure que 3. On peut donc, si on le désire,
soit ne la com men cer qu’à la date 20 (date limite, « au plus tard » de son début,
soit u
*
4 ), c’est- à-dire déca ler son début de 4, soit allon ger sa durée de 4 (puisque
u 4 1 3 1 4 5 u
*
10 ). Dans les deux cas, cette tâche devien drait alors cri tique.
1. Si l’on avait affaire à des contraintes telles que « la tâche B doit s’enchaî ner sans délai avec la
tâche A » ou « D com mence au plus tard 6 jours après la fin de C », le graphe com por te rait un cir
cuit et un (ou des) arc(s) de valeur négative. Il convien drait alors d’employer l’algo rithme de Ford.
L’ordon nan ce ment ne serait pos sible que si le graphe ne com por tait pas de cir cuit absor bant.
126
On modi fie le graphe MPM par des addi tions d’arcs et des rem pla ce ments de
nombres (figure 4.19). Noter que, lorsque l’on rem place une opé
ra tion par une opé
ra tion par tielle, dimi nuant ainsi la valuation d’un arc, il faut veiller à ce que les opé -
ra tions qui suivent l’achè ve ment total de cette opé ra tion ne com mencent pas avant
cet achè ve ment. Par exemple q ne peut com men cer que si n (durée totale 1) est ter -
mi née ; r et s que si ο est ache vée.
Les faci li tés évi dentes de la méthode des poten tiels la font pré fé rer par les
chercheurs opé ra tion nels, même si les résultats sont parfois “PERT-isés” pour
complaire à certains utilisateurs...
Le cal cul fait appa raître une notion très inté res sante ; certes on ne peut pas retar -
der l’exé cu tion des tâches cri tiques, sous peine de faire prendre un retard cor res pon -
dant à l’achè ve ment de l’ouvrage, mais il est bien clair qu’une opé ra tion non cri tique
peut au contraire soit débu ter après sa date au plus tôt, soit être ralen tie : nous allons
quan ti
fier cette notion (« marge ») au para graphe ci
dessous.
4.3.4 Cal culs pra tiques. Marges
Un des algo rithmes les plus employés pour la recherche du che min cri tique dans la
méthode PERT, comme dans la méthode MPM, est l’algo rithme de Bellmann : dans
l’un et l’autre cas, avec les contraintes potentielles utilisées jusqu’ici, le graphe asso -
cié ne com porte pas de cir cuit.
1
Dans la méthode PERT, u i désigne la date atten due (ou date au plus tôt) pour
l’évé ne ment i (c’est une inconnue), et d ij la durée de l’opé ra tion (i, j) (c’est une don -
née). Le cal cul de ces dates, même direc te ment sur le graphe pour notre exemple,
revient à appli quer la for mule :
u j 5 max
iPG
2 (j)
3u i 1 d ij 4.
La date au plus tard, notée u
*
i pour l’évé ne ment i, est égale, pour tout évé ne ment
(som met) i d’un che min cri
tique ζ, à la date au plus tôt : u
*
i 5 u i , si iPz .
En dehors d’un che min cri tique, les dates au plus tard se cal culent par la for mule :
u
*
i 5 min
jPG
1 (i)
3u
*
j 2 d ij 4.
Le cal cul fait appa raître une notion très inté res sante ; il est bien clair qu’une tâche
non cri tique (i, j) peut, au contraire, soit débu ter après la date u i mar quant son début
pos sible au plus tôt, soit être exé cu tée plus len te ment que prévu. Ainsi, la tâche (4,
10) peut com men cer à u 4 5 16, mais elle ne dure que 3. On peut donc, si on le désire,
soit ne la com men cer qu’à la date 20 (date limite, « au plus tard » de son début,
soit u
*
4 ), c’est- à-dire déca ler son début de 4, soit allon ger sa durée de 4 (puisque
u 4 1 3 1 4 5 u
*
10 ). Dans les deux cas, cette tâche devien drait alors cri tique.
1. Si l’on avait affaire à des contraintes telles que « la tâche B doit s’enchaî ner sans délai avec la
tâche A » ou « D com mence au plus tard 6 jours après la fin de C », le graphe com por te rait un cir
cuit et un (ou des) arc(s) de valeur négative. Il convien drait alors d’employer l’algo rithme de Ford.
L’ordon nan ce ment ne serait pos sible que si le graphe ne com por tait pas de cir cuit absor bant.