Méthode PERT

Le problème du plus long chemin dans les digraphes sans circuits trouve une application dans l'ordonnancement et la planification des tâches composant un projet complexe, par exemple la construction d'une maison.
On fait correspondre à chaque tâche un arc d'un digraphe, sa durée d'exécution étant égale au poids de cet arc. Le digraphe reflète les précédences requises dans l'exécution du projet. Ainsi, la tâche correspondant à l'arc (i, j) ne peut commencer que si toutes les tâches correspondant à des arcs (k, i) ont été complétées. Le digraphe peut contenir des tâches fictives de durée nulle afin de forcer certaines précédences.
Les sommets du digraphe représentent des événements, début (fin) des activités correspondant aux arcs dont ils sont l'extrémité initiale (finale). Le fait que le digraphe est sans circuit est garant de la faisabilité du projet. En effet, l'existence d'un circuit impliquerait une contradiction dans les précédences : une tâche devant en même temps précéder et succéder une autre!
On supposera dorénavant que les sommets ont déjà été numérotés de 1 à n de manière compatible avec leurs rangs, c'est-à-dire que r(j)>r(i) implique j>i (voir l'algorithme de calcul du rang). En plus, si le digraphe possède plusieurs sommets sans prédécesseurs, on supposera avoir introduit un sommet 1 relié par un arc de durée nulle à chacun de ces sommets. Ce sommet indique le début du projet. De même, si le digraphe possède plusieurs sommets sans successeurs, ceux-ci seront reliés par un arc de durée nulle à un dernier sommet n (fin du projet). Enfin, on supposera éliminés les arcs parallèles par l'introduction de tâches fictives.

Algorithme du chemin critique

Données : Digraphe G = (V, E), sans circuits, des activités avec leur durée d_ik.
Résultat :

d_i début au plus tôt des activités correspondant aux arcs (i, k) partant de i,
j_i fin au plus tard des activités correspondant aux arcs (k, i) arrivant à i,
durée du chemin critique.

Début
   I. Calcul des dates de début au plus tôt (récurrence en avançant dans le projet)
      d₁ := 0
      Pour k := 2 à n faire d_k := max{d_j + d_jk | j

P(k)}
   II. Calcul des dates de fin au plus tard (récurrence en reculant dans le projet)
      j_n := d_n
      Pour k := n-1 à 1 faire j_k := min{j_j - d_kj | j

S(k)}
Fin.

Notations:
P(i) = {k V | (k, i) E}: c'est l'ensemble des sommets prédécesseurs de i.
S(i) = {k V | (i, k) E}: c'est l'ensemble des sommets successeurs de i.

Définitions

Un sommet i est critique si d_i = j_i.
Un arc (i, j) est critique si ses extrémités sont des sommets critiques et d_ij = d_j - d_i.
Un chemin critique est un chemin de 1 à n n'utilisant que des arcs critiques, c'est-à-dire des activités telles que tout retard dans leur exécution provoquerait un retard de la fin du projet.
La durée du chemin critique est donnée par d_n (ou par j_n, les deux valeurs étant toujours égales). Elle correspond à la durée minimale du projet étant données les durées des tâches le composant et les précédences respectives.

Exemple

Ci-contre le graphe des précédences obtenu avec l'algorithme du chemin critique. Les sommets et les arcs critiques sont en rouge.

Tâches

Précédences

Durée [jours]

A

-

3

B

-

9

C

-

5

D

A

8

E

B

4

F

B

7

G

B

20

H

C, F

6

I

D, E

5

Exercices

Exercice 1

Refaites le graphe des précédences de l'exemple en utilisant l'algorithme du chemin critique.

Exercice 2

La rénovation du séjour d'un appartement se décompose en plusieurs tâches décrites dans le tableau ci-dessous. Ce dernier donne également les précédences à respecter lors de la planification des travaux ainsi qu'une estimation de la durée de chacune des tâches.

Tâches		Précédences	Durée [jours]
A	Enlèvement des portes	-	1/2
B	Ponçage et peinture des portes	A	3
C	Pose des portes	B, J	1/2
D	Arrachage des papiers peints	-	1
E	Tirage des fils électriques	D	1
F	Pose des prises	E, H, I	1/2
G	Ragréage des murs	E, A	2
H	Peinture du plafond	G	2
I	Pose des papiers peints	G	3
J	Peinture des cadres	H, I	1
K	Arrachage de la moquette	H, I, J	1/2
L	Ponçage du parquet	K	1
M	Imprégnation et séchage du parquet	L, F	4
N	Peinture du balcon	-	2
O	Changement des protections solaires	N	1

Représentez le graphe des précédences de ces travaux de rénovation.
Déterminez une durée totale minimale de rénovation en exhibant un chemin critique dans le graphe précédent.

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!

Didier Müller, 17.4.03