4.3 Pro blèmes d’ordon nan ce ment en ges tion de pro jets
119
© Dunod – Toute reproduction non autorisée est un délit.
existe plu sieurs che mins entre deux sommets, la date atten due est évi dem ment celle
qui est obte nue en sui vant le (ou les) che min(s) de valeur la plus grande. Par exemple,
bien que l’impres sion des hors- texte puisse être ache vée à 16 1 3 5 19, l’évé ne -
ment 10 n’aura lieu que lorsque les secondes épreuves du texte auront été tirées, ainsi
que celles des des sins ; sa date atten due, notée u 10 , est donc :
u 10 5 max 316 1 3, 16 1 3 1 1 1 2 1 1, 16 1 4 1 1 1 24 5 23,
ce qui revient à appli quer l’algo rithme de Bellman trans posé au cas d’une maxi mi sa tion
1
.
L’exemple étant par
ti cu liè re ment simple, il n’y a aucune dif fi culté à obte nir la
date atten due (au plus tôt) de l’achè ve ment des opé ra tions qui est u 22 5 31,5. Pour
l’obte nir on a, en fait, déter miné les deux che mins de durée maximale du som met 0
(début du pro
jet) au som
met 22 (fin du pro jet).
On remar quera, sur le graphe, l’emploi d’arcs de valeur 0 entre les évé ne ments 15
et 19, 15 et 21, 16 et 19, 16 et 20, 18 et 20, 18 et 21. En effet, les évé ne ments 15 et 21
ne peuvent être confon dus : 15 repré sente la fin du bro chage, 21 le début de l’envoi
des exem plaires de presse, une fois ache vée l’impres sion du prière d’insé rer ; si l’on
confon dait 15 et 21, l’arc t abou ti rait à 15 et alors l’opé ra tion w, qui suit r et s, devrait
suivre éga le ment t, ce qui serait une contrainte étrangère au problème. Le lec teur exa -
mi nera pour quoi les autres som mets, où abou tissent des arcs de valeur 0, ne peuvent
pas être confon dus. Ces arcs ne cor res pondent à aucune des opé ra tions (on dit aussi :
« tâches ») du pro jet ; on dit qu’ils repré sentent des « opé ra tions fic tives » ou encore
des « tâches fic tives ». Nous détaillons plus bas la ques
tion des tâches fic
tives.
Le che min cri tique (ou les che mins cri tiques, car il n’est pas néces sai re ment unique)
comporte les tâches qui, si elles subissaient un retard, retarderaient d’autant la date
attendue de l’achèvement du projet (u 22 5 31,5). Il est jalonné par les évé ne ments (dits
cri tiques) dont la date atten due est égale à la dif fé rence entre la date atten due de l’évé -
ne ment sui vant, sur le che min cri tique, et la valeur de l’arc qui les relie. L’évé ne ment
« début des opé ra tions » et l’évé ne ment « fin des opé ra tions » marquent évi dem ment le
début et la fin du che min cri tique. Tout arc dont la sup pres sion ren drait le graphe PERT
non connexe fait nécessairement par tie du che min cri tique : par exemple, l’une quel -
conque des opé ra tions a à d, ou encore l’opé ra tion m.
L’évé ne ment 22 étant sur le che min cri tique, fai sons les dif fé rences 31,5 2 1/2,
31, 5 2 1/8, 31,5 2 1/4, afin de remon ter les arcs abou
tis sant à 21 ; seul l’évé ne ment
19 est tel que sa date atten due est égale à 31,5 2 1/2 5 31 ; il fait donc par tie du che -
min cri tique. Conti nuons, avec 31 2 0 (évé ne ment 15) et 31 2 0 (évé ne ment 16) ;
seul l’évé ne ment 16, tel que sa date atten due est égale à 31 2 0 5 31, fait par tie du
che min cri tique. On remonte ainsi, de proche en proche, jus qu’au pre mier som met du
graphe. Noter qu’en remon tant à par tir de l’évé ne ment 10, on doit cal cu ler 23 2 1,
23 2 3, 23 2 2, pour voir si les dates atten dues coïn cident avec celles des évé ne -
ments 7,4 et 9 : or, 23 2 1 5 22, date atten due de l’évé ne ment 7 et 23 2 2 5 21,
1. Le lec teur remar quera que pour déter mi ner un ordon nan ce ment de durée mini male, on cherche
dans le graphe un che min de durée maximale !
119
© Dunod – Toute reproduction non autorisée est un délit.
existe plu sieurs che mins entre deux sommets, la date atten due est évi dem ment celle
qui est obte nue en sui vant le (ou les) che min(s) de valeur la plus grande. Par exemple,
bien que l’impres sion des hors- texte puisse être ache vée à 16 1 3 5 19, l’évé ne -
ment 10 n’aura lieu que lorsque les secondes épreuves du texte auront été tirées, ainsi
que celles des des sins ; sa date atten due, notée u 10 , est donc :
u 10 5 max 316 1 3, 16 1 3 1 1 1 2 1 1, 16 1 4 1 1 1 24 5 23,
ce qui revient à appli quer l’algo rithme de Bellman trans posé au cas d’une maxi mi sa tion
1
.
L’exemple étant par
ti cu liè re ment simple, il n’y a aucune dif fi culté à obte nir la
date atten due (au plus tôt) de l’achè ve ment des opé ra tions qui est u 22 5 31,5. Pour
l’obte nir on a, en fait, déter miné les deux che mins de durée maximale du som met 0
(début du pro
jet) au som
met 22 (fin du pro jet).
On remar quera, sur le graphe, l’emploi d’arcs de valeur 0 entre les évé ne ments 15
et 19, 15 et 21, 16 et 19, 16 et 20, 18 et 20, 18 et 21. En effet, les évé ne ments 15 et 21
ne peuvent être confon dus : 15 repré sente la fin du bro chage, 21 le début de l’envoi
des exem plaires de presse, une fois ache vée l’impres sion du prière d’insé rer ; si l’on
confon dait 15 et 21, l’arc t abou ti rait à 15 et alors l’opé ra tion w, qui suit r et s, devrait
suivre éga le ment t, ce qui serait une contrainte étrangère au problème. Le lec teur exa -
mi nera pour quoi les autres som mets, où abou tissent des arcs de valeur 0, ne peuvent
pas être confon dus. Ces arcs ne cor res pondent à aucune des opé ra tions (on dit aussi :
« tâches ») du pro jet ; on dit qu’ils repré sentent des « opé ra tions fic tives » ou encore
des « tâches fic tives ». Nous détaillons plus bas la ques
tion des tâches fic
tives.
Le che min cri tique (ou les che mins cri tiques, car il n’est pas néces sai re ment unique)
comporte les tâches qui, si elles subissaient un retard, retarderaient d’autant la date
attendue de l’achèvement du projet (u 22 5 31,5). Il est jalonné par les évé ne ments (dits
cri tiques) dont la date atten due est égale à la dif fé rence entre la date atten due de l’évé -
ne ment sui vant, sur le che min cri tique, et la valeur de l’arc qui les relie. L’évé ne ment
« début des opé ra tions » et l’évé ne ment « fin des opé ra tions » marquent évi dem ment le
début et la fin du che min cri tique. Tout arc dont la sup pres sion ren drait le graphe PERT
non connexe fait nécessairement par tie du che min cri tique : par exemple, l’une quel -
conque des opé ra tions a à d, ou encore l’opé ra tion m.
L’évé ne ment 22 étant sur le che min cri tique, fai sons les dif fé rences 31,5 2 1/2,
31, 5 2 1/8, 31,5 2 1/4, afin de remon ter les arcs abou
tis sant à 21 ; seul l’évé ne ment
19 est tel que sa date atten due est égale à 31,5 2 1/2 5 31 ; il fait donc par tie du che -
min cri tique. Conti nuons, avec 31 2 0 (évé ne ment 15) et 31 2 0 (évé ne ment 16) ;
seul l’évé ne ment 16, tel que sa date atten due est égale à 31 2 0 5 31, fait par tie du
che min cri tique. On remonte ainsi, de proche en proche, jus qu’au pre mier som met du
graphe. Noter qu’en remon tant à par tir de l’évé ne ment 10, on doit cal cu ler 23 2 1,
23 2 3, 23 2 2, pour voir si les dates atten dues coïn cident avec celles des évé ne -
ments 7,4 et 9 : or, 23 2 1 5 22, date atten due de l’évé ne ment 7 et 23 2 2 5 21,
1. Le lec teur remar quera que pour déter mi ner un ordon nan ce ment de durée mini male, on cherche
dans le graphe un che min de durée maximale !