PERT et CPM : réseau d'activités, chemin critique démontré, probabilité de finir à temps et compression au moindre coût
L'ordonnancement de projet avec PERT et CPM sur un exemple complet : parcours aller et retour, marge et chemin critique avec démonstration, trois estimations et probabilité de respecter l'échéance, vérification par Monte Carlo de l'optimisme de PERT, compression au moindre coût, code Python.
https://www.electronics-engineering.com/fr/pert-cpm-chemin-critique-ordonnancement-de-projet-monte-carlo-compression/
Un projet (développer un produit, construire une installation, organiser un événement) est fait d’activités reliées par des contraintes d’antériorité : on ne peut pas commencer à assembler le prototype avant que les composants arrivent. Les méthodes PERT (Program Evaluation and Review Technique) et CPM (Critical Path Method), nées toutes deux à la fin des années 1950, répondent à trois questions : combien de temps dure le projet, quelles activités ne peuvent pas être retardées sans tout retarder, et quelle est la probabilité de finir à une date donnée. Le CPM, mis au point par DuPont pour la maintenance d’usines chimiques, utilise des durées fixes et considère aussi les coûts ; le PERT, conçu pour le programme de missiles Polaris de la marine américaine, traite les durées comme des variables aléatoires. Cette leçon les déduit pas à pas sur un exemple, vérifie le PERT avec une simulation et montre comment raccourcir un projet au moindre coût.
L’idée en mots simples
Pensez à un dîner : les pâtes cuisent pendant que vous préparez la sauce, mais vous ne pouvez les égoutter que lorsque les deux sont prêtes. Le temps total n’est pas la somme de tout, mais la plus longue suite de choses qui doivent se produire l’une après l’autre : le chemin critique. Les activités de ce chemin sont celles qui, si elles sont en retard, retardent le dîner ; les autres ont une certaine marge (la sauce peut attendre). Le PERT et le CPM mènent systématiquement ce raisonnement pour des projets de dizaines ou de milliers d’activités.
Le réseau d’activités
Chaque activité a une durée et une liste de prédécesseurs. Le projet se représente comme un graphe orienté acyclique : les nœuds sont les activités, les flèches les contraintes « doit finir avant ». (Il existe aussi la représentation avec les activités sur les flèches des manuels classiques de PERT ; les activités sur les nœuds sont aujourd’hui les plus utilisées.)
L’exemple de cette leçon est le développement d’un petit produit électronique, avec des durées en semaines :
| activité | description | prédécesseurs | a | m | b | durée espérée |
|---|---|---|---|---|---|---|
| A | spécifications | aucun | 2 | 3 | 5 | 3.17 |
| B | conception matérielle | A | 4 | 6 | 10 | 6.33 |
| C | conception logicielle | A | 5 | 8 | 14 | 8.50 |
| D | achat des composants | B | 3 | 4 | 8 | 4.50 |
| E | assemblage du prototype | D | 2 | 3 | 5 | 3.17 |
| F | essais du logiciel | C | 2 | 4 | 6 | 4.00 |
| G | intégration | E, F | 3 | 5 | 9 | 5.33 |
| H | certification | G | 3 | 4 | 7 | 4.33 |
Les trois colonnes a, m, b sont les estimations PERT optimiste, la plus probable et pessimiste ; pour l’instant la durée espérée
suffit, et on en reparle plus loin.
Les deux parcours et le chemin critique
Parcours aller. En suivant le graphe depuis le début, chaque activité peut commencer au plus tôt quand tous ses prédécesseurs ont fini :
![]()
La durée du projet est
.
Parcours retour. En partant de la fin, chaque activité doit finir au plus tard quand la première de ses successeurs doit commencer, sans déplacer la date de fin
:
![]()
La marge (marge totale) d’une activité est
: de combien elle peut glisser sans retarder le projet. Les activités de marge nulle forment le chemin critique.
Théorème. La durée minimale du projet est la longueur du plus long chemin du début à la fin du graphe, et le parcours aller la calcule.
Démonstration. Le long de tout chemin, les activités doivent se dérouler l’une après l’autre, donc le projet ne peut pas durer moins que la somme de leurs durées :
la longueur de chaque chemin, en particulier du plus long. Réciproquement, par récurrence sur l’ordre topologique,
est exactement la longueur du plus long chemin qui finit en
: c’est vrai pour les activités initiales, et si c’est vrai pour tous les prédécesseurs de
, alors
est le plus long chemin qui arrive à
et
celui qui finit avec
. Démarrer chaque activité à son
satisfait toutes les contraintes et finit à
: la durée minimale est atteinte. ∎
Dans l’exemple, avec les durées espérées : le projet dure 26,83 semaines et le chemin critique est A-B-D-E-G-H (conception matérielle, achats, assemblage, intégration, certification). La branche logicielle, C-F, a une marge de 1,5 semaine : elle peut glisser jusqu’à une semaine et demie sans conséquence.


PERT : des durées incertaines
Dans le PERT, chaque durée est une variable aléatoire décrite par trois estimations : optimiste
, la plus probable
, pessimiste
. On suppose qu’elle suit une loi bêta sur
de mode
, et l’on utilise les approximations classiques
![Rendered by QuickLaTeX.com \[ t_e = \frac{a + 4m + b}{6},\qquad \sigma^2 = \left(\frac{b - a}{6}\right)^2 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-07d5f0e997229ecc4da5ac0e34bd19a8_l3.png)
(la moyenne pèse quatre fois l’estimation la plus probable ; l’écart type est un sixième de l’étendue, comme pour une loi normale dans laquelle presque toutes les valeurs sont à moins de ±3σ).
Le PERT calcule ensuite le chemin critique avec les durées espérées et approche la durée du projet par la somme des durées des activités critiques, qui par le théorème central limite est à peu près normale, de moyenne la somme des moyennes et de variance la somme des variances (activités indépendantes). Dans l’exemple,
semaine, et la probabilité de finir en 26 semaines est
![]()
Le PERT est optimiste. La méthode regarde un seul chemin, mais le projet finit quand tous les chemins ont fini : si les activités logicielles s’allongent, la branche C-F peut devenir critique elle aussi. Le maximum de plusieurs variables aléatoires a une moyenne supérieure au maximum des moyennes (inégalité de Jensen appliquée au maximum, qui est une fonction convexe). Une simulation de Monte Carlo de 200 000 projets, chacun avec des durées tirées dans ses lois bêta, donne une durée moyenne de 27,23 semaines au lieu de 26,83 et une probabilité de finir en 26 semaines de 27,8 % au lieu de 33,1 %. C’est le « biais de fusion » (merge bias) : dans les projets à nombreuses branches parallèles presque critiques, l’erreur du PERT peut être bien plus grande, et la simulation est l’outil adapté.

CPM : raccourcir au moindre coût
Le CPM ajoute les coûts. Beaucoup d’activités peuvent être raccourcies (compression, crashing) en payant davantage : heures supplémentaires, expéditions express, plus de personnes. Pour chaque activité, on sait de combien on peut la réduire et ce que coûte chaque semaine gagnée. Le problème est : comment réduire la durée du projet d’une quantité donnée en dépensant le moins possible ?
Les règles qui en découlent :
- seules les activités critiques valent la peine d’être raccourcies : raccourcir une activité qui a de la marge ne change pas la durée ;
- parmi les critiques, on choisit celle de moindre coût par semaine ;
- quand un autre chemin devient critique, il faut raccourcir les deux, et les activités communes aux deux chemins deviennent intéressantes.
Dans l’exemple, avec les durées les plus probables
, le projet dure 25 semaines : le chemin A-B-D-E-G-H dure 25, le chemin A-C-F-G-H 24. Pour descendre à 23 semaines, il faut en retirer 2 au premier et 1 au second. La solution optimale, trouvée par le code en essayant toutes les combinaisons, est de raccourcir G (commune aux deux chemins, 2000 euros) et E (1500 euros) : 3500 euros. Raccourcir seulement des activités du premier chemin, par exemple E et B, ne suffirait pas : le second chemin resterait à 24 semaines. Les grands projets se résolvent par la programmation linéaire.
Résumé
- Le projet est un graphe d’activités avec des antériorités ; sa durée minimale est le plus long chemin.
- Le parcours aller donne les débuts au plus tôt, le parcours retour les débuts au plus tard ; la marge est la différence, et les activités sans marge forment le chemin critique.
- Le PERT utilise trois estimations par activité,
et
, et approche la durée par une loi normale sur le chemin critique. - Le PERT est optimiste quand plusieurs chemins sont presque critiques : la simulation de Monte Carlo donne la bonne estimation.
- Le CPM raccourcit les activités critiques les moins chères, en tenant compte des chemins qui deviennent critiques.
Les notes originales sur ce sujet, du cours de Recherche opérationnelle, se trouvent dans les archives du web : notes sur le PERT (PDF, en italien).
Le code
import itertools
import math
import numpy as np
# Project of a small electronic product: activities, precedences and three estimates (optimistic, most likely, pessimistic), in weeks
act = {
"A": ((2, 3, 5), []), # specifications
"B": ((4, 6, 10), ["A"]), # hardware design
"C": ((5, 8, 14), ["A"]), # software design
"D": ((3, 4, 8), ["B"]), # component purchasing
"E": ((2, 3, 5), ["D"]), # prototype assembly
"F": ((2, 4, 6), ["C"]), # software testing
"G": ((3, 5, 9), ["E", "F"]), # integration
"H": ((3, 4, 7), ["G"]), # certification
}
te = {k: (a + 4 * m + b) / 6 for k, ((a, m, b), _) in act.items()} # PERT expected duration
var = {k: ((b - a) / 6) ** 2 for k, ((a, m, b), _) in act.items()} # PERT variance
order = list(act) # already in topological order
def cpm(dur):
ES, EF = {}, {}
for k in order: # forward pass
ES[k] = max((EF[p] for p in act[k][1]), default=0.0)
EF[k] = ES[k] + dur[k]
T = max(EF.values())
LF, LS = {}, {}
for k in reversed(order): # backward pass
succ = [s for s in order if k in act[s][1]]
LF[k] = min((LS[s] for s in succ), default=T)
LS[k] = LF[k] - dur[k]
return T, ES, EF, LS, LF
T, ES, EF, LS, LF = cpm(te)
crit = [k for k in order if abs(LS[k] - ES[k]) < 1e-9]
print(f"expected project duration {T:.2f} weeks, critical path {'-'.join(crit)}")
for k in order:
print(f" {k}: te {te[k]:.2f} ES {ES[k]:5.2f} EF {EF[k]:5.2f} LS {LS[k]:5.2f} LF {LF[k]:5.2f} slack {LS[k] - ES[k]:.2f}")
# probability of finishing within 26 weeks according to PERT (sum of the variances on the critical path, normal distribution)
s = math.sqrt(sum(var[k] for k in crit))
Phi = lambda z: 0.5 * (1 + math.erf(z / math.sqrt(2)))
print(f"PERT: sigma {s:.2f} weeks, P(T <= 26) = {Phi((26 - T) / s):.3f}")
# Monte Carlo check with beta-PERT distributed durations
rng = np.random.default_rng(0)
N = 200_000
samp = {}
for k, ((a, m, b), _) in act.items():
al, be = 1 + 4 * (m - a) / (b - a), 1 + 4 * (b - m) / (b - a)
samp[k] = a + (b - a) * rng.beta(al, be, N)
EFs = {}
for k in order:
EFs[k] = np.max([EFs[p] for p in act[k][1]], axis=0) + samp[k] if act[k][1] else samp[k]
Tmc = EFs["H"]
print(f"Monte Carlo: mean duration {Tmc.mean():.2f}, P(T <= 26) = {np.mean(Tmc <= 26):.3f}")
# CPM: shorten the project by 2 weeks at minimum cost (maximum reduction and cost per week of each activity)
norm = {k: act[k][0][1] for k in order} # most likely durations m
crash = {"A": (1, 3000), "B": (2, 2500), "C": (2, 1800), "D": (1, 4000), "E": (1, 1500), "F": (1, 1200), "G": (2, 2000), "H": (1, 5000)}
T0 = cpm(norm)[0]
best = None
for red in itertools.product(*[range(crash[k][0] + 1) for k in order]):
dur = {k: norm[k] - r for k, r in zip(order, red)}
if cpm(dur)[0] <= T0 - 2:
cost = sum(r * crash[k][1] for k, r in zip(order, red))
if best is None or cost < best[0]:
best = (cost, {k: r for k, r in zip(order, red) if r})
print(f"duration with the most likely durations {T0:.0f} weeks; to reach {T0 - 2:.0f}: reductions {best[1]}, cost {best[0]} euros")En l’exécutant, on obtient la durée espérée de 26,83 semaines avec le chemin critique A-B-D-E-G-H et le tableau des deux parcours (marge 1,50 pour C et F), σ = 1,91 et probabilité 0,331 selon le PERT, durée moyenne 27,23 et probabilité 0,278 dans la simulation, et pour le CPM les réductions de E et G au coût de 3500 euros.






Ciao, sono l'autore di «PERT e CPM: reticolo delle attività, cammino critico dimostrato, probabilità di finire in tempo e accelerazione al costo minimo». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “PERT and CPM: activity network, critical path proved, probability of finishing on time and crashing at minimum cost”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.