4.3 Pro blèmes d’ordon nan ce ment en ges tion de pro jets
127
© Dunod – Toute reproduction non autorisée est un délit.
On dit que sur la tâche (opé
ra
tion) (4, 10), on béné
fi cie d’une marge libre de 4.
La marge libre m ij de l’opé ra tion (i, j) est définie par : m ij 5 u j 2 1 u i 1 d ij 2 .
Les marges libres jouent un grand rôle dans le para mé trage des ordon nan ce ments.
En effet, on peut vou loir ralen tir l’exé cu tion d’une opé ra
tion non cri tique, afin de
la rendre moins coû teuse, mais on ne peut pas allon ger la durée d’une opé ra tion
au delà de la marge libre sans modi fier les dates au plus tôt (et donc les marges
libres) des opé ra tions ulté rieures. On ne dis pose de la tota lité de la marge libre
m ij pour l’opé ra tion (i, j) que si les opé ra tions qui lui sont préa lables ont effec ti -
ve ment com mencé à leur date au plus tôt. Remar quons que la marge libre d’une
opé ra tion, si elle est nulle le long du che min cri tique, peut être nulle sans que pour
autant cette opé ra tion soit cri tique. Ainsi, pour l’opé ra tion p, notée (11, 17) dans
le graphe PERT de la figure 4.13, on a : m 11, 17 5 26 2 1 25 1 12 5 0. En effet, la
marge libre appa raît comme la « réserve de temps » dont on dis pose sur une tâche
qui per met – si elle est consom mée – de ne pas retar der les dates au plus tôt des
tâches ulté rieures : il s’agit donc d’une inter pré ta tion bien res tric tive de la notion de
marge ; c’est pour quoi les spé cia listes uti lisent aussi d’autres marges.
La marge totale de l’opé ra tion (i, j) est par défi ni tion : M ij 5 u
*
j 2 1 u i 1 d ij 2 : c’est
la réserve de temps sur l’opé ra tion (i, j) qui – si elle est consom mée – fait que (i, j) se
ter mi nera à sa date au plus tard, c’est- à-dire que l’opé ra tion devien dra cri tique lors
de l’exé cu tion du pro jet. L’opé ra tion (i, j) ne pourra béné fi cier effec
ti ve ment de la
marge totale M ij , que si les dates au plus tôt 1 u k 2 des évé ne ments préa lables à (i, j) ont
été res pec tées : les marges totales ne sont donc pas indé pen dantes. Par exemple, pour
l’opé ra tion non cri tique p 5 1 11, 172 , on a : M 11, 17 5 30,75 2 (25 1 1) 5 4,75 ;
de même pour t 5 1 17, 182 , on a : M 17, 18 5 31,25 2 (26 1 0, 5) 5 4,75. Si l’on
retarde, lors de l’exé cu tion, la tâche p de 4,75 (quin zaines), alors l’opé ra tion t n’a
plus de marge et devient cri tique !
Pas sons main te nant à la méthode MPM. Le cal cul des dates de début au plus
tôt (t i ), au plus tard (t
*
i ) et celui de la marge libre (m i ) et totale (M i ) pour l’opé ra tion
(ou tâche) i se pra tique de manière ana logue.
• Pour les dates au plus tôt : t j 5 max
iPG
2 (j)
3t i 1 v ij 4, où v ij est la valuation de l’arc (i, j) ;
le plus sou vent on a sim ple ment : v ij 5 d i (durée de la tâche i).
• Pour les dates au plus tard on a t
*
i 5 t i si la tâche i est cri tique, et t
*
i 5 min
jPG
1 (i)
3t
*
j 2 v ij 4
sinon,
la marge libre m i vaut : m i 5 c min
jPG
2 (i)
3t j 2 v ij d 2 t i
la marge totale m i vaut par défi
ni tion : m i 5 c min
jPG
1 (i)
(t
*
j 2 t i 2 v ij ) d ; on montre
aisément qu’elle vaut sim ple ment : M i 5 t
*
i 2 t i .
Dans l’exemple, pour la tâche p, on a obtenu t p 5 25.
Puisque p n’a qu’un seul suc ces seur : t, la marge libre de p vaut :
m p 5 t t 2 1 d p 1 t p 2 5 26 2 1 25 1 12 5 0.
127
© Dunod – Toute reproduction non autorisée est un délit.
On dit que sur la tâche (opé
ra
tion) (4, 10), on béné
fi cie d’une marge libre de 4.
La marge libre m ij de l’opé ra tion (i, j) est définie par : m ij 5 u j 2 1 u i 1 d ij 2 .
Les marges libres jouent un grand rôle dans le para mé trage des ordon nan ce ments.
En effet, on peut vou loir ralen tir l’exé cu tion d’une opé ra
tion non cri tique, afin de
la rendre moins coû teuse, mais on ne peut pas allon ger la durée d’une opé ra tion
au delà de la marge libre sans modi fier les dates au plus tôt (et donc les marges
libres) des opé ra tions ulté rieures. On ne dis pose de la tota lité de la marge libre
m ij pour l’opé ra tion (i, j) que si les opé ra tions qui lui sont préa lables ont effec ti -
ve ment com mencé à leur date au plus tôt. Remar quons que la marge libre d’une
opé ra tion, si elle est nulle le long du che min cri tique, peut être nulle sans que pour
autant cette opé ra tion soit cri tique. Ainsi, pour l’opé ra tion p, notée (11, 17) dans
le graphe PERT de la figure 4.13, on a : m 11, 17 5 26 2 1 25 1 12 5 0. En effet, la
marge libre appa raît comme la « réserve de temps » dont on dis pose sur une tâche
qui per met – si elle est consom mée – de ne pas retar der les dates au plus tôt des
tâches ulté rieures : il s’agit donc d’une inter pré ta tion bien res tric tive de la notion de
marge ; c’est pour quoi les spé cia listes uti lisent aussi d’autres marges.
La marge totale de l’opé ra tion (i, j) est par défi ni tion : M ij 5 u
*
j 2 1 u i 1 d ij 2 : c’est
la réserve de temps sur l’opé ra tion (i, j) qui – si elle est consom mée – fait que (i, j) se
ter mi nera à sa date au plus tard, c’est- à-dire que l’opé ra tion devien dra cri tique lors
de l’exé cu tion du pro jet. L’opé ra tion (i, j) ne pourra béné fi cier effec
ti ve ment de la
marge totale M ij , que si les dates au plus tôt 1 u k 2 des évé ne ments préa lables à (i, j) ont
été res pec tées : les marges totales ne sont donc pas indé pen dantes. Par exemple, pour
l’opé ra tion non cri tique p 5 1 11, 172 , on a : M 11, 17 5 30,75 2 (25 1 1) 5 4,75 ;
de même pour t 5 1 17, 182 , on a : M 17, 18 5 31,25 2 (26 1 0, 5) 5 4,75. Si l’on
retarde, lors de l’exé cu tion, la tâche p de 4,75 (quin zaines), alors l’opé ra tion t n’a
plus de marge et devient cri tique !
Pas sons main te nant à la méthode MPM. Le cal cul des dates de début au plus
tôt (t i ), au plus tard (t
*
i ) et celui de la marge libre (m i ) et totale (M i ) pour l’opé ra tion
(ou tâche) i se pra tique de manière ana logue.
• Pour les dates au plus tôt : t j 5 max
iPG
2 (j)
3t i 1 v ij 4, où v ij est la valuation de l’arc (i, j) ;
le plus sou vent on a sim ple ment : v ij 5 d i (durée de la tâche i).
• Pour les dates au plus tard on a t
*
i 5 t i si la tâche i est cri tique, et t
*
i 5 min
jPG
1 (i)
3t
*
j 2 v ij 4
sinon,
la marge libre m i vaut : m i 5 c min
jPG
2 (i)
3t j 2 v ij d 2 t i
la marge totale m i vaut par défi
ni tion : m i 5 c min
jPG
1 (i)
(t
*
j 2 t i 2 v ij ) d ; on montre
aisément qu’elle vaut sim ple ment : M i 5 t
*
i 2 t i .
Dans l’exemple, pour la tâche p, on a obtenu t p 5 25.
Puisque p n’a qu’un seul suc ces seur : t, la marge libre de p vaut :
m p 5 t t 2 1 d p 1 t p 2 5 26 2 1 25 1 12 5 0.