Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Recommandée par l'auteur Gestion d'entreprise Ingénierie logistique MS Project

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/

Cette page vous a-t-elle été utile ? Notez-la :
moyenne 5,0 sur 1 vote

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édescriptionprédécesseursambdurée espérée
Aspécificationsaucun2353.17
Bconception matérielleA46106.33
Cconception logicielleA58148.50
Dachat des composantsB3484.50
Eassemblage du prototypeD2353.17
Fessais du logicielC2464.00
GintégrationE, F3595.33
HcertificationG3474.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 t_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 :

    \[ ES_j = \max_{i \in \text{pred}(j)} EF_i \quad (ES = 0 \text{ without predecessors}),\qquad EF_j = ES_j + t_j \]

La durée du projet est T = \max_j EF_j.

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 T :

    \[ LF_j = \min_{k \in \text{succ}(j)} LS_k \quad (LF = T \text{ without successors}),\qquad LS_j = LF_j - t_j \]

La marge (marge totale) d’une activité est LS_j - ES_j : 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 : T \ge la longueur de chaque chemin, en particulier du plus long. Réciproquement, par récurrence sur l’ordre topologique, EF_j est exactement la longueur du plus long chemin qui finit en j : c’est vrai pour les activités initiales, et si c’est vrai pour tous les prédécesseurs de j, alors ES_j = \max EF_i est le plus long chemin qui arrive à j et EF_j celui qui finit avec j. Démarrer chaque activité à son ES_j satisfait toutes les contraintes et finit à \max EF_j : 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.

Le réseau du projet
Chaque case est une activité avec sa durée espérée ; la ligne du milieu contient le début et la fin au plus tôt, la ligne du bas le début et la fin au plus tard. Les activités en rouge, dont le début au plus tôt égale le début au plus tard, forment le chemin critique A, B, D, E, G, H ; celles en bleu, C et F, ont 1,5 semaine de marge.
Le diagramme de Gantt
Chaque barre est une activité dans le temps, placée à son début au plus tôt. Les barres rouges sont critiques et se suivent sans interruption jusqu’à 26,83 semaines ; après les barres bleues de C et F, le rectangle en pointillés est la marge.

PERT : des durées incertaines

Dans le PERT, chaque durée est une variable aléatoire décrite par trois estimations : optimiste a, la plus probable m, pessimiste b. On suppose qu’elle suit une loi bêta sur [a, b] de mode m, et l’on utilise les approximations classiques

    \[ t_e = \frac{a + 4m + b}{6},\qquad \sigma^2 = \left(\frac{b - a}{6}\right)^2 \]

(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, \sigma = 1.91 semaine, et la probabilité de finir en 26 semaines est

    \[ P(T \le 26) = \Phi\left(\frac{26 - 26.83}{1.91}\right) = 0.331 \]

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é.

Durée du projet : PERT et simulation
L’histogramme bleu est la durée du projet dans 200 000 simulations, de moyenne 27,23 semaines ; la courbe rouge est la normale du PERT, centrée sur 26,83. L’histogramme est décalé vers la droite et asymétrique : le PERT sous-estime la durée. La ligne verte est l’échéance de 26 semaines.

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 m, 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é, t_e = (a + 4m + b)/6 et \sigma = (b - a)/6, 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.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x