6.4 · Méthode MPM d'ordonnancement d'un graphe
Pour chaque tâche, on va rajouter les dates au plus tôt et au plus tard en présentant chaque tâche par un rectangle :
Tableau 6.8
t(x)
1
T(xj)
Par exemple, pour
7
9
xj
la tâche E :
E
0
0
~
4
7
9
A
E
0
0
Début
12
12
3
~
G
n
0
1
3
3
8
8
B
D
F
Figure 6.14
Examinons la tâche C : on a t(C) = 3 et T(C) = 4 . Au plus tôt, on peut commencer à
3 jours et au plus tard à 4 jours . Pour cette tâche, on dispose donc d'une
« liberté » d'un jour. Ce n'est pas ainsi pour d'autres tâches (comme D par
exemple) pour lesquelles les dates au plus tôt et au plus tard sont les mêmes. Ces
tâches sont qualifiées de tâches critiques. Et l'enchaînement A-D-F-G-Fin, qui ne
contient que des tâches critiques, est qualifié de chemin critique.
Une tâche critique est une tâche dont les dates au plus tôt et au plus tard sont
égales. Donc xj est critique si et seulement si t(xj) = T(xj).
Un chemin critique est un chemin reliant le début à la fin et qui n' est constitué
que de tâches critiques.
6.4.2 Marges d'une tâche
"'O
g
La marge totale d' une tâche c'est le retard maximum que l'on peut accepter sur la
~
date de début de la tâche sans que cela ne retarde la date de fin du projet.
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
~ La marge totale d'une tâche xj se note MT(xj) et elle vaut MT(x) ~ T(x) - t(x).
Exemple (suite)
La tâche C n'est pas critique. On peut constater qu'on peut retarder le début de C
d'un jour sans retarder la date de fin du projet (et c'est le maximum).
En effet, si C commence à la date 4, cela n'empêcherait pas F de commencer à la
date 8, E pourrait commencer à la date 8 et n'empêcherait pas G de commencer à
la date 12.
Ce retard maximum s'appelle la marge totale de la tâche.
161