CORRIGE du TD N°4 : ORDONNANCEMENT DE PROJET

EXERCICE 1 : corrigé

a) Tracé du graphe potentiels-tâches associé au projet

Le graphe potentiels-tâches ou graphe MPM de la méthode dite MPM (méthode des

potentiels Métra) développée par le mathématicien Bernard ROY en France ou graphe AON
(Activities On Nodes) ou graphe d’ordonnancement est un graphe représentant
l’enchainement des tâches d’un projet.

Les tâches ou activités sont représentées par des sommets et les contraintes d’antériorité
entre les tâches sont représentées par des arcs (flèches).

Ainsi la contrainte consistant à dire que la tâche X doit s’éxécuter avant la tâche Y sera
représentée par le schéma :

X Y
D’autre part le graphe sera valué , c'est-à-dire que les arcs porteront une valeur numérique
correspondant aux durées des tâches.

On affectera à chaque arc la durée de la tâche située à l’extrémité initiale. Si la tâche X a

une durée , on représentera la contrainte : X précède Y par le schéma suivant :

𝑑
X Y
Après représentation des données du projets (tâches, contraintes d’antériorité et durées des
tâches selon la démarche ci-dessus), on introduira deux autres sommets fictifs dans le
graphe obtenu :

- Un sommet Début correspondant au lancement ou démarrage du projet auquel on

rattachera toutes les tâches n’ayant aucun prédécesseur.
- Un sommet Fin indiquant la fin du projet auquel on rattachera toutes les tâches
n’ayant aucun successeur.

Le graphe potentiels-tâches est un graphe sans circuit (sauf cas particuliers qui ne seront pas
traités ici).

1
Par conséquent et pour faciliter le tracé du graphe, on peut procéder au classement des
tâches par niveaux.

Le classement des tâches par niveau revient à identifier au fur et mesure de l’avancement du
projet les tâches n’ayant pas de prédécesseur ou ayant un prédécesseur d’un niveau plus
faible. Les tâches n’ayant aucun prédécesseur seront automatiquement de niveau 0.

Il existe un algorithme simple qui permet de déterminer le niveau des tâches d’un projet
comme suit :

- Etape 1 : à partir du dictionnaire des prédécesseurs du projet, tableau précisant les

prédécesseurs de chaque tâche, identifier les tâches n’ayant aucun prédécesseur. Ces tâches
sont de niveau 0. Rayer ces tâches du tableau.

- Etape 2 : Les tâches du nouveau niveau sont les tâches non rayées et n’ayant plus de
prédécesseurs, ces tâches sont rayées à leur tour.

- Etape 3 : S’il reste des tâches non rayées alors retour à l’étape 1, sinon le classement est
terminé.

Après ces petits rappels du cours, construisons le graphe potentiels-tâches associé au projet
de l’organisation d’une semaine de ski par les étudiants de l’exercice 1.

Pour cela, classons d’abord les tâches par niveaux croissants selon l’algorithme en haut à
partir du dictionnaire des prédécesseurs.

Tâches
Tâches N0 N1 N2 N3 N4 N5
antérieures
A C A
B C B
C - C
D A D
E D, J E
F E, G, I, H, B F
G J G
H D, E, J H
I J I
J A J
Le tracé du graphe potentiels-tâches se fait en plaçant les sommets dans l’ordre
croissant de leurs niveaux, en ajoutant des arcs pour chaque antériorité entre sommets

2
 et en introduisant deux sommets fictifs, un au début du graphe et un autre à la fin du
graphe. La figure 1 représente le graphe potentiels-tâches associé à notre cas.

D E 20
15

5 H
A
5 30
15 G 30
15
D J
0 5 F 15
E
C 5 I F
B
I
U
N
T
15
90
B

Figure 1: graphe potentiels-tâches

a) Calcul du calendrier au plus tôt

Il faut déterminer un planning d’activation des tâches permettant de réaliser le projet

en un temps minimal tout en respectant les contraintes. Cette durée minimale du
projet correspond au chemin le plus long dans le graphe. Cela peut paraître paradoxal
au premier abord, mais il faut avoir le temps d’effectuer toutes les tâches avec tous
les enchaînements possibles en particulier le plus long.

Pour chaque tâche, on va déterminer la date de début « au plus tôt » d’exécution.

Pour qu’une tâche puisse commencer, il est nécessaire que toutes les tâches qui la
relient à la tâche du début du projet soient réalisées. Il faut donc évaluer le plus long
chemin entre le sommet initial du graphe et le sommet correspondant à cette tâche.

On utilise un algorithme de recherche de plus long chemin dans un graphe. Cet

algorithme utilise un principe très simple mais extrêmement puissant et utilisé pour
de nombreux problèmes : le principe d’optimalité de Bellman. Il dit simplement que
3
pour trouver le plus long chemin dans le graphe, à partir d’un sommet de départ,
jusqu’un sommet quelconque S du graphe, il suffit de prendre la plus grande parmi
toutes les longueurs maximales des chemins qui arrivent aux sommets prédécesseurs,
additionnée des longueurs des arcs reliant ces sommets à S.

Dans notre cas, il s’agit d’appliquer ce principe en partant du sommet début et de

proche en proche en évaluant le plus long chemin du début à chaque sommet,
évaluation correspondant à la date de début « au plus tôt » de la tâche associée à ce
sommet.

Le sommet début sera marqué de la valeur 0, valeur choisie pour la comodité des
calculs ici mais concrétement on utilisera une date calendaire correspondant à la date
de démarrage du projet. La figure 2 résume le calcul des date de début « au plus tôt »
des différentes tâches en utilisant le principe de Bellman ci-dessus et selon la légende
suivante : une tâche i sera représentée par le cadrant ci-après avec en haut sa date de
début au plus tôt notée EST(i) (EST pour Earliest Start Time) et en bas sa date de
début au plus tard notée LST(i) (LST pour Latest Start Time).

EST(i)
i
LST(i)

Ainsi par exemple la date de début au plus tôt de la tâche E est 35 car cette tâche à
deux antécédents la tâche D de date de début au plus tôt 30 et la tâche J de date de
début au plus tôt 30 aussi. La tâche E ne peut s’exécutée que si ces deux tâches sont
entièrement réalisées. Autrement dit la date de début au plus tôt de la tâche E est la
plus grande entre les deux dates de fin au plus tôt des tâches D et J qui sont 30+3=33
pour la tâche D et 30+5=35 pour la tâche J, soit EST(E) = 35.

4
 35
30 3
E
D 20
15
55
15
H 120
A 35
FIN
5 G
30
15
15 30 5 30
0 0 15
J 35 105
0 5
Début C I F
5

15
15 90
B

Figure 2: calendrier au plus tôt

a) Chemin critique et durée optimale du projet

Par définition le chemin critique est le plus long chemin entre le sommet début et le
sommet fin du graphe.
Dans notre cas, il s’agit du chemin constitué successivement des tâches C, B et F de
longueur 120. Les tâches C, B, F du chemin critique sont aussi appelées tâches
critiques.
Comme mentionné précédement, cette longueur correspond à la durée minimale de
réalisation de l’ensemble du projet, soit donc 120 jours.

b) Calcul des marges

La marge totale d’une tâche est le délai maximal par rapport à la date au plus tôt pour
le démarrage d’une tâche tel que la ddate d’achèvement du projet ne soit pas modifié.
Elle se calcule comme la différence entre sa date de début au plus tard et sa date de
début au plus tôt. La marge totale d’une tâche critique est nulle.
5
La marge libre d’une tâche est le délai maximal par rapport à la date au plus tôt pour
le démarrage d’une tâche tel que le calendrier des tâches qui suivent ne soit pas
modifié. Pour une tâche i qui a une date de début au plus tôt EST(i) et une durée di,
elle est égale à la différence entre la plus petite des dates de début au plus tôt des
tâches qui suivant et (EST(i) + di).
Pour pouvoir calculer les marges totales, il nous faut d’abord déterminer le calendrier
au plus tard. Il s’agit de calculer la date de début « au plus tard » d’exécution. Cette
fois-ci, il faut partir de la fin du graphe, donc du sommet final une fois qu’on lui a
affecté une date au plus tard qui sera prise identique à la date au plus tôt de ce
sommet lors du premier parcours du graphe pour le calcul du calendrier au plus tôt.
Pour trouver la date de début au plus tard d’une tâche i de durée di, il faut avoir déjà
calculé les dates de début au plu tard de toutes les tâches Si qui suivent la tâche i. la
date de début au plus tard de la tâche i sera égale à la plus petite valeur des
différences (LST(Si) – di ).
La figure 3 ci-dessous reprend le graphe précédent avec le calcul du calendrier au
plus tard.
Remarquons au passage que pour les tâches critiques C, B et F, le calendrier au plus
tôt est identique au caledrier au plus tard ce qui donne une marge totale nulle à ces
tâches.
Une marge totale nulle pour une tâche signifie que tout retard sur le démarrage de
cette tâche par rapport à sa date de début se répercutera automatiquement sur le projet
tout entier.

6
 35
30 3
E
D 20
15 55
52
55
15
H 120
A 35
75 FIN
35 5 G
30 120
15 75
15 30 5 30
0 0 15
J 35 105
0 5
Début C 50 I F
5
0 100 105

15
15 90
B
15
Figure 3: calendriers au plus tôt et au plus tard

En utilisant les règles de calcul des marges citées précédement, on peut résumer les
marges totales et les marges libres des tâches non critiques dans le tableau suivant :
Tâche A D E G H I J
Marge totale (en jours) 20 22 20 40 20 65 20
Marge libre (en jours) 0 2 0 40 20 65 0

a) Graphe mis à jour

Le nouveau graphe est identique à celui de la question (a) avec l’ajout de la nouvelle
tâche notée K qui ne pourra commencer que sept jours après la tâche F et durera cinq
jours. La figure 4 représente la modification apportée au graphe.

7
 3
D E 20
15

5 H
A
5 30
15 G 30
15
D J
0 5 F 15
E
C 5 I F
B
I
U
5 N
T 7
15
90 K
B

Figure 4: graphe MPM modifé

8
EXERCICE 2 : corrigé

a) Tracé du graphe MPM et calcul des calendriers au plus tôt et au plus tard
Pour modéliser ce problème d’ordonnancement sous forme d’un graphe potentiels-
tâches, on procédera au classement des tâches en niveaux croissants pour faciliter le
tracé et obtenir une disposition des tâches permettant d’appliquer l’algorithme de
calcul des calendriers.
Le classement des tâches se fait à partir du tableau descriptif du projet en utilisant la
colonne des opérations et celle des opérations précédentes comme suit :
Opérations
Opérations N0 N1 N2 N3 N4 N5
précédentes
A - A
B A B
C B C
D B D
E B E
F B F
G C, D G
H E, F, G H
I H, J I
J E, F, G J
K H, J K
L H, J L
Dans le graphe potentiels-tâches, les tâches sont représentées par des sommets et les
arcs représentent les contraintes de précédence. Ainsi la contrainte i précède j est elle
symbolisée par un arc entre les sommets i et j et de longueur la durée de la tâche
associée au sommet i. La figure 1 représente le graphe potentiels-tâches associé au
projet.

9
 C 3

12 I
G 32 20
5 4 8
D D
32 H 20
E 0 32 F
A B 12 38
B 3 K I
U 20 N
T 12 E 3
13
12 6 42
13
6 L
F J
13

Figure 1: graphe MPM

Le calcul des calendriers au plus tôt et au plus tard peut se faire sur le graphe
potentiels-tâches selon la même démarche expliquée dans les exercices précédents.
Les calculs sont reportés sur le graphe MPM de la figure 2. Les date de début au plus
tôt et de début au plus tard sont placées respectivement au dessus et en dessous de
chaque sommet ou tâche.

10
 44
80 100
3
C 48 32 20 8I
H
0 45 G
20 134
2 80 9
A 48 8
44 8 13
20
0 12 4 9
0 2
D 80 142
32 32 100 38
44 2
FIN
J
0 B 12 2 3 K
3 87 142
Début 32 44 104
7
8
E 13 42
12 100
77 6
00
L

44 6 100
8
F
74

Figure 2: calendriers au plus tôt et au plus tard

a) Chemin critique et durée minimale de mise en exploitation du gisement

Le chemin critique est représentée en trait gras dans le graphe d’ordonnancement de

la figure précédente. C’est le chemin de longueur maximale du sommet début au
sommet fin.
Dans notre cas, il s’agit du chemin constitué successivement des tâches A, B, D, G,
H, L de longueur 142. La longueur du chemin critique correspond à la durée
minimale de réalisation de l’ensemble du projet, soit donc 142 semaines ou 35,5
mois.

11
 b) Calcul des marges

En utilisant les règles de calcul des marges citées précédement, on peut résumer les
marges totales et les marges libres des opérations non critiques dans le tableau
suivant :
Tâche C E F I J K
Marge totale (en semaines) 1 33 30 34 7 4
Marge libre (en semaines) 1 33 30 34 7 4

12