Calculateur de Chemin Critique

Pseudocode

Deux balayages du réseau d'activités en ordre topologique: vers l'avant pour le plus tôt où chaque tâche peut avoir lieu, vers l'arrière pour le plus tard sans retarder le projet.

CPM(activites, dependances):
    ordre = triTopologique(activites)

    // Balayage avant: debut et fin au plus tot
    pour chaque activite a dans ordre:
        DT[a] = max(FT[p] pour p predecesseur de a), sinon 0
        FT[a] = DT[a] + duree[a]
    T = max(FT[a] sur toutes les a)   // duree du projet

    // Balayage arriere: debut et fin au plus tard
    pour chaque activite a dans inverse(ordre):
        FTa[a] = min(DTa[s] pour s successeur de a), sinon T
        DTa[a] = FTa[a] - duree[a]

    marge[a] = DTa[a] - DT[a]
    chemin critique = activites de marge 0

Le chemin critique est le plus long chemin du réseau, non le plus court, ce qui en fait un problème de maximisation sur un DAG et non un problème de plus court chemin. Le réseau étant acyclique, les deux balayages ne sont que de la programmation dynamique en ordre topologique et aucune file de priorité n'est nécessaire. Une marge nulle signifie que l'activité n'a aucune latitude: retarde-la d'un jour et le projet entier glisse d'un jour.

Exemple détaillé, étape par étape

Planifie un projet de quatre activités où deux tâches peuvent s'exécuter en parallèle mais doivent toutes deux se terminer avant que la troisième ne débute.

Graphe d'exemple: Activités de durées A (3 jours), B (2 jours), C (4 jours) et D (2 jours). Dépendances: A et B doivent précéder C, et C précède D.

1. Balayage avant, A et B. Aucune n'a de prédécesseur, toutes deux démarrent donc à l'instant 0. A finit à 3, B finit à 2. Elles s'exécutent en parallèle.
2. Balayage avant, C. C attend les deux, son début au plus tôt est donc le maximum de 3 et 2, soit 3. Elle dure 4 jours et finit à 7. Note que B a terminé un jour plus tôt et attend simplement.
3. Balayage avant, D. D démarre à 7 et finit à 9. Rien ne la suit, la durée du projet est donc de 9 jours.
4. Balayage arrière. En remontant depuis 9: D doit démarrer au plus tard à 7, donc C doit finir à 7 et démarrer à 3. A et B doivent par conséquent finir à 3, ce qui donne à A un début au plus tard de 0 et à B un début au plus tard de 1.
5. Calculer la marge. A a un début au plus tard de 0 contre un début au plus tôt de 0, soit une marge de 0. B a 1 contre 0, soit une marge de 1. C et D ont toutes deux une marge de 0.

Le projet dure 9 jours et le chemin critique est A vers C vers D. B dispose d'un jour de marge, elle peut donc démarrer un jour en retard ou déborder d'un jour sans affecter la date de fin. C'est le bénéfice pratique: cela indique à un chef de projet exactement où concentrer son attention. Raccourcir B ne sert à rien, tandis que raccourcir A, C ou D raccourcit le projet entier, du moins jusqu'à ce que le chemin critique bascule et passe par B.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Un tri topologique coûte O(V + E), et chacun des deux balayages visite chaque activité une fois et chaque arête de dépendance une fois, ils sont donc aussi en O(V + E). L'espace tient à quatre nombres par activité, les débuts et fins au plus tôt et au plus tard, soit O(V). La méthode entière est linéaire, ce qui lui permet de passer à l'échelle sur des réseaux de projet comptant des centaines de milliers d'activités. Le réseau de dépendances doit être un graphe orienté acyclique: une dépendance circulaire n'a pas d'ordre topologique et, corrélativement, aucun calendrier valide, la détection de cycle est donc un véritable prérequis et non une formalité.

Quand utiliser Méthode du Chemin Critique (CPM), et quand l'éviter

CPM suppose des durées connues et des ressources illimitées. Relâcher l'une ou l'autre hypothèse change le problème.

Pièges fréquents

• Prendre le minimum au lieu du maximum dans le balayage avant. Une activité ne peut démarrer avant que tous ses prédécesseurs soient terminés, le début au plus tôt est donc le maximum sur les fins des prédécesseurs. Prendre le minimum produit un calendrier impossiblement court et silencieusement faux.
• Supposer que le chemin critique est unique. Plusieurs chemins peuvent être à égalité comme les plus longs, et alors toute activité de chacun d'eux a une marge nulle. En raccourcir un seul ne sert à rien, car l'autre chemin critique gouverne toujours la date de fin.
• Oublier que le chemin critique se déplace. Raccourcis suffisamment une activité critique et un autre chemin devient le plus long. La compression doit être réévaluée après chaque modification plutôt qu'appliquée d'un bloc à partir de l'analyse initiale.
• Ignorer les limites de ressources. CPM suppose que A et B peuvent réellement s'exécuter en même temps. Si toutes deux ont besoin de la même machine ou de la même personne, le calendrier est une fiction et il faut RCPSP à la place.
• L exécuter sur un réseau comportant un cycle. Une dépendance circulaire signifie qu'aucun ordre topologique n'existe et qu'aucun calendrier n'est valide. Détecte le cycle et signale-le plutôt que de produire des nombres à partir d'un ordre partiel.

Questions fréquentes

Quelle est la méthode du chemin critique?

CPM trouve le plus long chemin dans un réseau d'activités et de dépendances, ce qui détermine la durée minimale possible du projet. Les activités sur ce chemin ont une marge nulle, si bien que tout retard sur elles retarde le projet entier. Elle se calcule avec un balayage avant pour les dates au plus tôt et un balayage arrière pour les dates au plus tard.

Quest-ce que la marge dans CPM?

La marge est le temps dont une activité peut être retardée sans repousser la fin du projet, calculée comme début au plus tard moins début au plus tôt. Les activités de marge nulle sont critiques. Dans l'exemple ci-dessus, l'activité B dispose d'un jour de marge tandis que A, C et D n'en ont aucune.

Quelle est la complexité temporelle de la méthode du chemin critique?

O(V + E), où V est le nombre d'activités et E celui des dépendances. C'est un tri topologique suivi de deux balayages linéaires du réseau, elle passe donc sans peine à l'échelle sur de très grands plans de projet.

Quelle est la différence entre CPM et PERT?

CPM utilise une durée déterministe unique par activité et se concentre sur l'identification du chemin critique et des marges. PERT utilise trois estimations par activité, optimiste, la plus probable et pessimiste, pour calculer une durée espérée et une variance, ce qui permet d'énoncer la probabilité de terminer à une date donnée. L'analyse du réseau elle-même est identique.

Le chemin critique peut-il changer pendant un projet?

Oui, et c'est le principal piège pratique. Si une activité critique est raccourcie ou si une activité non critique consomme sa marge, un autre chemin peut devenir le plus long. L'analyse doit être refaite au fur et à mesure que les durées réelles se précisent, plutôt que traitée comme figée au moment de la planification.