Méthode PERT

Contenus

Comme le diagramme de Gantt, la méthode PERT permet d’évaluer la durée de réalisation d’un projet complexe et de détecter les parties de ce projet ne supportant aucun retard.

Les informations sur les tâches sont résumé dans un échéancier comme l’exemple suivant :

tâche	précédence	durée
A	–	6
B	–	5
C	A	4
D	B	6
E	C	5
F	A, D	6
G	E, F	4

Étape 1 : construction du graphe à partir de l’échéancier

Méthode PERT – Détermination des niveaux des tâches :

On attribuera le niveau 0 aux tâches qui n’ont pas de tâche antérieure.

On attribuera le niveau 1 aux tâches dont les tâches antérieures sont de niveau 0.

On déterminera ainsi le niveau de chaque tâche : les tâches de niveau k+1 seront les tâches dont les tâches antérieures sont de niveau inférieur avec au moins une tâche de niveau k parmi elles.

On construira le graphe en traçant les tâches par ordre de niveau croissant.

Méthode PERT – Tâches commençantes, finissantes, convergentes :

Avant de se lancer dans la construction du graphe, il sera souvent utile de détecter les tâches dites commençantes, finissantes ou convergentes.

Les tâches commençantes sont les tâches sans tâche antérieure, elles partent du sommet 1 du graphe.

Les tâches finissantes sont les tâches qui ne sont pas tâche antérieure, elles arrivent au
sommet terminal du graphe.

Les tâches convergentes sont des tâches que l’on rencontre toujours ensemble (i.e. jamais l’une sans l’autre) dans la colonne tâches antérieures; dans le graphe, elles auront le même sommet terminal.

L’arête entre 2 et 5 est appelée tâche fictive et est toujours de degré nulle. Elle a pour but de modéliser le fait que la tâche A doit être terminée pour commencer la tâche F. L’arête entre 1 et 2 signifie que la tâche A commence en l’état 1 et se finit en l’état 2.

Il est important de placer les tâches par ordre d’exécution. La tâche F ne peut être placé qu’une fois la tâche A et D placées, et la tâche D ne peut être placé qu’après la tâche B. Cela explique l’arête fictive entre 2 et 5 (A et à la distance 1 alors que F est à la distance 3 du début).

Étape 2 : déterminer les dates et marges

Une fois le graphe construit, on va déterminer les dates au plus tôt et au plus tard pour les
différents sommets et les marges libres et totales pour les tâches.

Méthode PERT – Dates au plus tôt :
Pour un sommet, la date au plus tôt (notée : t) représente le temps minimum nécessaire pour atteindre ce sommet. Elle se déterminera de proche en proche, par ordre de sommet croissant, à partir de l’entrée du graphe, grâce à l’algorithme de Ford de recherche du chemin le plus long.

Ainsi :
t₁ = 0 et t_j = Max ( t_i + d_ij ) sur tous les i précédant j avec d_ij = durée entre le sommet i et j.
Dans l’exemple, t₁ = 0, t₂ = 0+6 = 6, t₃ = 0+5 = 5, t₄ = 6+4 = 10, t₅ = max ( 6+0 , 5+6 ) = 11, t₆ = max ( 11+6 , 10+5 ) = 17, t₇ = 17+4 = 21.

La date au plus tôt de la sortie du graphe représente la durée minimale réalisable pour
l’ensemble du projet ( dans l’exemple, t₇= 21, le projet durera donc au mieux 21 jours).

Méthode PERT – Dates au plus tard :
Pour un sommet, la date au plus tard (notée : T) représente concrètement la date à laquelle cet état doit obligatoirement être atteint si l’on ne veut pas augmenter la durée totale du projet. Elle se déterminera de manière analogue à t, mais par ordre de sommet décroissant, depuis la sortie du graphe vers l’entrée.

Ainsi :
T_n = t_n = Durée du projet et T_i = Min ( T_j – d_ij ) sur tous les j précédant i.
Dans l’exemple, T₇ = 21, T₆ = 21 – 4 = 17, T₅ = 17 – 6 = 11, T₄ = 17 – 5 = 12, T₃ = 11 – 6 = 5, T₂ = min ( 11-0 , 12-4 ) = 8, T₁ = min ( 8-6 , 5-5 ) = 0.
On aura toujours t₁ = T₁ = 0 et t inférieur ou égal à T pour tout sommet. On appelle T-t la
marge de flottement du sommet.

Méthode PERT – Marges des tâches :
La marge libre d’une tâche représente le retard maximal possible d’une tâche sans retarder le début des tâches suivantes, noter ML. La marge totale d’une tâche représente le retard maximal possible pour la réalisation d’une tâche sans retarder l’ensemble du projet, on la notera MT : ML_ij = t_j – t_i – d_ij et MT_ij = T_j – t_i – d_ij.

Compte tenu du mode calcul, les marges seront toujours positives ou nulles et la marge libre d’une tâche sera toujours inférieure ou égale à sa marge totale.

On qualifiera de critique, une tâche dont la marge totale est nulle. Une tâche critique ne doit pas prendre de retard si l’on ne veut pas augmenter la durée totale du projet.

Si la durée d’une tâche non critique augmente, une partie de cette augmentation sera absorbée par la marge de la tâche, seul le surplus se répercutera sur la durée du projet.

Aparté

Les sommets peuvent contenir plusieurs informations en même temps :