"'O
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
158
6.3.3 Graphe pondéré (ou valué)
Sur certains graphes orientés, il peut être nécessaire d'attribuer une valeur à chacun
des arcs : on obtient alors un graphe pondéré ou valué.
La valeur d'un chemin est la somme des valeurs des arcs qui constituent le
chemin. Il est alors possible de chercher le chemjn de valeur minimale ou maximale
reliant un sommet à un autre.
Exemple
Sur le graphe pondéré de la fig. 6.1 2, pour relier B à C, il y a trois chemins
possibles :
- Le chemin (B,A,E,C) de valeur 4 + 3 + 5 = 12.
- Le chemin (B,D,E,C) de valeur 7 + 4 + 5 = 16.
- Le chemin (B,D,C) de valeur 7 + 8 = l 5.
Le chemin minimal est (B,A,E,C), le chemin maximal est (B,D,E,C).
B
Figure 6.12
Un algorithme de recherche de chemin minimal sera proposé en exercice
corrigé 6.16.
6.4 MÉTHODE MPM D'ORDONNANCEMENT
D'UN GRAPHE
La réalisation d'un projet passe par l'exécution de différentes tâches, de durées
souvent différentes. Si certaines tâches peuvent être réalisées simultanément,
d'autres nécessitent que certaines tâches aient été réalisées antérieurement.
Faire l'ordonnancement d'un projet consiste à organiser ce projet en respectant les contraintes d'antériorité des tâches tout en minimisant la durée totale de
réalisation .
La méthode MPM (Méthode des potentiels metra) permet l' ordonnancement de
projets, c'est la méthode que nous exposerons dans ce cours. Nous aurions pu choisir
la méthode PERT, mais elle est plus complexe à mettre en œuvre.
Exemple
Pour illustrer la méthode MPM, nous allons réaliser l'ordonnancement d'un projet
fictif, comprenant des tâches que nous noterons A, B, C, D, E, F, G. Les contraintes
d'antériorité et les durées de ces tâches sont consignées dans le tableau 6.6.
0
c
:J
0
li)
..--t
0
N
@
.......
J::
O'l
·;::::
>0.
0
u
Chapitre 6 • Graphes et ordonnancement
158
6.3.3 Graphe pondéré (ou valué)
Sur certains graphes orientés, il peut être nécessaire d'attribuer une valeur à chacun
des arcs : on obtient alors un graphe pondéré ou valué.
La valeur d'un chemin est la somme des valeurs des arcs qui constituent le
chemin. Il est alors possible de chercher le chemjn de valeur minimale ou maximale
reliant un sommet à un autre.
Exemple
Sur le graphe pondéré de la fig. 6.1 2, pour relier B à C, il y a trois chemins
possibles :
- Le chemin (B,A,E,C) de valeur 4 + 3 + 5 = 12.
- Le chemin (B,D,E,C) de valeur 7 + 4 + 5 = 16.
- Le chemin (B,D,C) de valeur 7 + 8 = l 5.
Le chemin minimal est (B,A,E,C), le chemin maximal est (B,D,E,C).
B
Figure 6.12
Un algorithme de recherche de chemin minimal sera proposé en exercice
corrigé 6.16.
6.4 MÉTHODE MPM D'ORDONNANCEMENT
D'UN GRAPHE
La réalisation d'un projet passe par l'exécution de différentes tâches, de durées
souvent différentes. Si certaines tâches peuvent être réalisées simultanément,
d'autres nécessitent que certaines tâches aient été réalisées antérieurement.
Faire l'ordonnancement d'un projet consiste à organiser ce projet en respectant les contraintes d'antériorité des tâches tout en minimisant la durée totale de
réalisation .
La méthode MPM (Méthode des potentiels metra) permet l' ordonnancement de
projets, c'est la méthode que nous exposerons dans ce cours. Nous aurions pu choisir
la méthode PERT, mais elle est plus complexe à mettre en œuvre.
Exemple
Pour illustrer la méthode MPM, nous allons réaliser l'ordonnancement d'un projet
fictif, comprenant des tâches que nous noterons A, B, C, D, E, F, G. Les contraintes
d'antériorité et les durées de ces tâches sont consignées dans le tableau 6.6.