"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
~ CAes notions utilisant les durées des tâches, nous noterons d(x)
E:J tache xj"
la durée d'une
160
6.4.1 Date au plus tôt - Date au plus tard
La date au plus tôt d'une tâche est la date minimale à laquelle on peut commencer
la tâche, car toutes les tâches antérieures sont terminées.
Nous noterons t(x) la date au plus tôt d'une tâche xj. t(x) est le plus grand des
nombres t(x;) + d(x;) où X; est une des tâches qui précèdent immédiatement la
tâche xj.
Exemple
Calculons les dates au plus tôt des tâches du projet :
- t(A) = t(B) = 0
- t(C) = t(A) + d(A) = 0 + 3 = 3
- D a deux prédécesseurs : A et B. On calcule t(A) + d(A) = 0 + 3 = 3 et
t(B) + d(B) = 0 + 2 = 2. t(D) est le plus grand de ces deux nombres donc t(D) = 3.
- t( E) = t(C) + d(C) = 3 + 4 = 7
- F a deux prédécesseurs : C et D. On calcule t(C) + d(C) = 7 et t(D) + d(D)
= 3 + 5 = 8. Le plus grand de ces deux nombres est 8 donc t(F) = 8.
- Pour G, on calcule t(E) + d(E) = 7 + 3 = 10 et t(F) + d(F) = 8 + 4 = 12 donc
t(G) = 12.
- Et pour finir, t(Fin) = t(G) + d(G) = 12 + 3 = 15.
On a ainsi calculé la date au plus tôt de la fin du projet qui est de l 5 jours.
La date au plus tard d' une tâche est la date maximale à laquelle on peut
commencer la tâche sans que cela ne repousse la date de fin du projet.
Nous noterons T(x) la date au plus tard d'une tâche xj. T(x) est le plus petit des
nombres T(xk) - d(x) où xk est une des tâches qui suit immédiatement la tâche xj.
Exemple (suite)
Calculons les dates au plus tard des tâches du projet : on doit commencer par la
fin puisqu'à chaque fois, on doit considérer les successeurs.
- On a bien sûr T( Fin) = t(Fin) = l 5
- T(G) = T(Fin) - d(G) = l 5 -3 = 12
- T(F) = T(G) - d(F) = l 2 - 4 = 8
- T(E) = T(G) - d(E) = l 2 - 3 = 9
- T(D)= T(F)- d(D)=8-5=3
- Ca deux successeurs : E et F. On calcule T(E) - d(C) = 9 - 4 = 5 et T(F) - d(C)
= 8 - 4 = 4 . Le plus petit de ces deux nombres est 4, donc T(C) = 4 .
- T(B) = T(D) - d(B) = 3 - 2 = l
- A a deu x successeurs : Cet D. On calcule T(C) - d(A) = 4 - 3 = l et T(D) - d(A)
= 3 - 3 = O. Donc T(A) = O.
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
~ CAes notions utilisant les durées des tâches, nous noterons d(x)
E:J tache xj"
la durée d'une
160
6.4.1 Date au plus tôt - Date au plus tard
La date au plus tôt d'une tâche est la date minimale à laquelle on peut commencer
la tâche, car toutes les tâches antérieures sont terminées.
Nous noterons t(x) la date au plus tôt d'une tâche xj. t(x) est le plus grand des
nombres t(x;) + d(x;) où X; est une des tâches qui précèdent immédiatement la
tâche xj.
Exemple
Calculons les dates au plus tôt des tâches du projet :
- t(A) = t(B) = 0
- t(C) = t(A) + d(A) = 0 + 3 = 3
- D a deux prédécesseurs : A et B. On calcule t(A) + d(A) = 0 + 3 = 3 et
t(B) + d(B) = 0 + 2 = 2. t(D) est le plus grand de ces deux nombres donc t(D) = 3.
- t( E) = t(C) + d(C) = 3 + 4 = 7
- F a deux prédécesseurs : C et D. On calcule t(C) + d(C) = 7 et t(D) + d(D)
= 3 + 5 = 8. Le plus grand de ces deux nombres est 8 donc t(F) = 8.
- Pour G, on calcule t(E) + d(E) = 7 + 3 = 10 et t(F) + d(F) = 8 + 4 = 12 donc
t(G) = 12.
- Et pour finir, t(Fin) = t(G) + d(G) = 12 + 3 = 15.
On a ainsi calculé la date au plus tôt de la fin du projet qui est de l 5 jours.
La date au plus tard d' une tâche est la date maximale à laquelle on peut
commencer la tâche sans que cela ne repousse la date de fin du projet.
Nous noterons T(x) la date au plus tard d'une tâche xj. T(x) est le plus petit des
nombres T(xk) - d(x) où xk est une des tâches qui suit immédiatement la tâche xj.
Exemple (suite)
Calculons les dates au plus tard des tâches du projet : on doit commencer par la
fin puisqu'à chaque fois, on doit considérer les successeurs.
- On a bien sûr T( Fin) = t(Fin) = l 5
- T(G) = T(Fin) - d(G) = l 5 -3 = 12
- T(F) = T(G) - d(F) = l 2 - 4 = 8
- T(E) = T(G) - d(E) = l 2 - 3 = 9
- T(D)= T(F)- d(D)=8-5=3
- Ca deux successeurs : E et F. On calcule T(E) - d(C) = 9 - 4 = 5 et T(F) - d(C)
= 8 - 4 = 4 . Le plus petit de ces deux nombres est 4, donc T(C) = 4 .
- T(B) = T(D) - d(B) = 3 - 2 = l
- A a deu x successeurs : Cet D. On calcule T(C) - d(A) = 4 - 3 = l et T(D) - d(A)
= 3 - 3 = O. Donc T(A) = O.