"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
6.4 • Méthode MPM d'ordonnancement d'un graphe
Tableau 6.6
Tâche
Durée (en jours)
Tâches antérieures
A
3
aucune
B
2
aucune
c
4
A
D
5
A, B
E
3
c
F
4
c
G
3
E
La première chose à faire est de définir le niveau de chaque tâche. Il est simple de
voir que A et B sont de niveau 0, Cet 0 de niveau l, E et F de niveau 2 et G de
niveau 3.
Tableau 6.7
Niveaux
0
l
2
3
Sommets
A, B
C,D
E, F
G
Le graphe ordonné par niveaux est celui de la figure 6.1 3.
3
3
Début
Figure 6.13
On peut remarquer que l'on a rajouté deux tâches fictives : Début et Fin ; et que
l'on a pondéré le graphe en ajoutant les durées de chaque tâche.
~ Il est plutôt simple de calculer la durée minimale du projet (si vous ne la trouvez pas,
~ nous la calculerons un peu plus loin). Mais on peut se poser quelques questions :
2 • À quel moment peut-on commencer une tâche ?
c
· 5 • Est-ce qu' on peut retarder le moment de démarrer certaines tâches sans que cela
:::l
"[
ait d 'impact sur la durée minimale du projet?
~
Pour répondre à ces questions, nous allons définir, pour chaque tâche, les notions
:;
~ de date au plus tôt et de date au plus tard.
1
"8 c
:::l
0
QJ
159