La théorie des graphes en gestion de projet

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Pourquoi un planning est un graphe

Tout plan de projet fait deux sortes d’affirmations. La première porte sur le travail : cette tâche dure neuf jours. La seconde porte sur l’ordre : cette tâche ne peut pas commencer avant que celle-là soit terminée. Écrivez-en cent de chaque sorte et vous n’aurez pas écrit une liste, vous aurez écrit un graphe. Les tâches sont les sommets, les contraintes d’ordre sont les arcs orientés et les durées sont les poids.

Ce n’est pas une façon de regarder les plans de projet. C’est ce qu’est un plan de projet, et le reconnaître change les questions que vous pouvez poser. Une liste de tâches vous dit combien de travail il y a. Seul le graphe vous dit combien de temps dure le projet, et c’est un autre nombre, généralement bien plus grand, parce que le travail qui ne peut pas se faire en parallèle doit se faire en séquence.

Les conséquences sont immédiates et un peu surprenantes. La durée d’un projet n’est pas la somme des durées de ses tâches, ni la plus grande d’entre elles. C’est la longueur du plus long chemin à travers le réseau. C’est pourquoi le projet de cet article contient soixante-douze jours de travail et se termine pourtant en trente-neuf. C’est aussi pourquoi ajouter des personnes n’aide pas automatiquement, pourquoi la tâche qui inquiète tout le monde n’est souvent pas celle qui compte, et pourquoi un plan peut être contradictoire d’une façon qu’aucun effort ne réparera.

Les techniques de cet article ont été inventées à un an d’intervalle, toutes deux sous pression commerciale et militaire, et toutes deux par des gens qui savaient résoudre un problème de graphes. En 1959, James Kelley chez Remington Rand et Morgan Walker chez DuPont publiaient la méthode du chemin critique, conçue pour planifier l’arrêt et le redémarrage d’usines chimiques, où chaque jour d’inactivité coûtait de l’argent réel. La même année, le Special Projects Office de la marine américaine publiait PERT, conçu pour piloter le programme de missiles Polaris, où le problème n’était pas le coût mais l’incertitude pure d’un travail que personne n’avait jamais fait. Les deux articles décrivent des réseaux d’activités, et les deux calculent le plus long chemin.

La suite construit explicitement un petit projet, treize activités aux durées réelles, et y répond à toutes les questions classiques d’ordonnancement : combien de temps, qu’est-ce qui est critique, qu’est-ce qui peut glisser, quelle confiance accorder à la date, ce que coûte d’aller plus vite et ce qui se passe quand il n’y a pas assez de monde. Chaque nombre a été calculé, et chaque résultat a été recalculé par une seconde méthode avant d’être écrit.

2. Activités, dépendances et les quatre types de liens

Il existe deux conventions pour dessiner un projet sous forme de graphe, et il vaut la peine de connaître les deux, car la plus ancienne apparaît encore dans les manuels.

Dans la représentation activités sur les nœuds (AoN, activity-on-node), chaque activité est un sommet et chaque flèche une dépendance. C’est ce qu’utilisent les logiciels modernes et ce qu’utilise cet article du début à la fin. Dans la représentation activités sur les flèches (AoA, activity-on-arrow), chaque activité est une flèche et les sommets sont des événements, les instants où un ensemble d’activités est terminé. AoA était la convention d’origine de PERT et de CPM, et elle a un vrai défaut : exprimer certains schémas de dépendance oblige à insérer des activités fictives de durée nulle, qui n’existent que pour que la logique tienne. AoN n’a besoin d’aucune activité fictive, et c’est l’une des raisons pour lesquelles elle a supplanté AoA dans la pratique.

La dépendance elle-même n’est pas toujours la plus simple. Quatre types de liens sont standard :

• Fin-début (FS) : B ne peut pas commencer avant que A soit terminée. Le type par défaut, et le seul utilisé dans cet article.
• Début-début (SS) : B ne peut pas commencer avant que A ait commencé. Utile pour un travail qui avance en parallèle, comme une documentation qui suit le développement à quelques jours d’écart.
• Fin-fin (FF) : B ne peut pas se terminer avant que A soit terminée.
• Début-fin (SF) : B ne peut pas se terminer avant que A ait commencé. Rare, et généralement le signe que le plan veut dire autre chose.

Les liens peuvent aussi porter un décalage (lag), un délai appliqué à la contrainte : le béton doit sécher trois jours avant qu’on construise dessus, donc l’arc porte un décalage de trois même si personne ne travaille. Les décalages sont des poids d’arcs, et tout ce qui suit fonctionne avec eux sans changement. Un décalage négatif, appelé avance, permet à une activité de commencer avant la fin de sa prédécesseure ; c’est permis, et c’est aussi une façon courante de construire un plan qui ne peut pas réellement être exécuté.

Une règle compte plus que tout cela : le graphe doit être acyclique. Si A attend B et que B attend A, aucun ordre n’existe, et la section 4 montre exactement à quoi cela ressemble quand un outil d’ordonnancement tombe dessus.

3. Le projet qui sert de fil conducteur

L’exemple est le lancement d’une application mobile : treize activités, seize dépendances, des durées en jours ouvrés. Il est assez petit pour être vérifié à la main et assez structuré pour montrer tout ce qui compte, en particulier plusieurs chemins de longueur presque égale, là où se trouve l’essentiel des comportements intéressants.

Lisez la structure plutôt que les libellés. Les exigences (A) ouvrent trois flux parallèles : le développement du produit via le schéma de base de données (C), le design (B) et le marketing (G). Le flux de développement se divise à nouveau après l’API backend (D) en frontend (E), paiements (F) et revue de sécurité (I), puis converge deux fois, d’abord aux tests d’intégration (H), ensuite au programme bêta (J). Le marketing ne rejoint l’ensemble qu’à la soumission (L).

C’est à ces points de convergence que la difficulté se concentre. Une activité à plusieurs prédécesseurs attend la plus lente d’entre eux, et la plus lente n’est pas connue d’avance quand les durées sont incertaines. Les sections 9 et 11 parlent toutes deux, au fond, de ce qui se passe à une convergence.

4. Le plan est-il seulement réalisable ?

Avant de demander combien de temps dure un projet, demandez-vous s’il peut être mené à bien. Un réseau de précédences ne décrit un plan valide que s’il s’agit d’un graphe orienté acyclique. Si les dépendances contiennent un cycle, il n’existe aucun ordre dans lequel le travail peut être fait, et le plan n’est pas en retard : il est impossible.

Le test est un tri topologique, et l’algorithme de Kahn en est la version à connaître, car sa façon d’échouer est très instructive. Prenez de manière répétée n’importe quelle activité sans prédécesseur inachevé, notez-la et retirez-la. Sur ce projet, on obtient l’ordre A, B, C, D, E, F, G, H, I, J, K, L, M, soit les treize activités : le plan est ordonnançable.

Supposons maintenant que quelqu’un ajoute une seule dépendance qui paraît raisonnable : le schéma de base de données (C) ne devrait pas être figé avant que les tests d’intégration (H) aient révélé les vrais schémas de requêtes. Ajoutez l’arc de H vers C et relancez. L’algorithme de Kahn produit quatre activités puis s’arrête : A, B, G et K, le seul travail qui n’est pas pris dans la boucle. Les neuf autres sont bloquées, chacune attendant une autre. L’algorithme ne se contente pas d’échouer : l’ensemble qu’il n’a pas pu produire est l’interblocage, et c’est précisément le diagnostic dont un planificateur a besoin.

Cela compte en pratique, car les vrais plans sont assemblés par de nombreuses personnes, chacune ajoutant des contraintes localement sensées, et personne n’a tout le graphe en tête. Les dépendances circulaires sont fréquentes, et le graphe les trouve en temps linéaire.

L’ordre topologique fait plus que valider le plan. Comme il garantit que chaque prédécesseur apparaît avant ses successeurs, il permet de calculer tout le planning en une seule passe sur les activités, sans itération ni recherche. C’est pourquoi la méthode du chemin critique était déjà utilisable sur le matériel de 1959, et pourquoi elle reste instantanée sur des projets de cent mille tâches.

5. Le chemin critique : deux passes sur le graphe

La méthode du chemin critique calcule quatre nombres pour chaque activité et en déduit tout le reste.

La passe avant parcourt les activités dans l’ordre topologique et calcule le plus tôt possible pour chacune. Le début au plus tôt d’une activité est la plus tardive des fins au plus tôt de ses prédécesseurs, et sa fin au plus tôt est cette valeur plus sa durée. Les exigences commencent au jour 0 et finissent au jour 4. Le schéma de base de données commence alors à 4 et finit à 7. L’API backend commence à 7 et finit à 16. Le développement frontend attend à la fois l’API (qui finit à 16) et le design UI (qui finit à 14), donc il commence à 16, pas à 14. Après une passe, la plus grande fin au plus tôt est la durée du projet : 39 jours ouvrés.

La passe arrière parcourt le même ordre à l’envers et calcule le plus tard possible pour chaque activité sans repousser la date de fin. La fin au plus tard d’une activité est le plus précoce des débuts au plus tard de ses successeurs. Le lancement doit finir à 39, donc commencer à 38 ; la soumission doit finir à 38, donc elle commence à 36 ; et ainsi de suite jusqu’au début.

L’écart entre les deux est la marge totale, ce qu’une activité peut glisser avant que la fin du projet ne bouge. Les activités à marge nulle forment le chemin critique.

Le chemin critique est A → C → D → E → H → J → L → M, et sa longueur est exactement les 39 jours obtenus par la passe avant. Ce n’est pas une coïncidence mais un théorème : la durée du projet est égale à la longueur du plus long chemin, et les activités à marge nulle sont exactement celles qui se trouvent sur un plus long chemin. Quand deux chemins sont ex æquo pour le plus long, comme dans la section 10, les deux sont critiques.

Deux conséquences méritent d’être dites clairement. Premièrement, retarder une activité critique d’un jour retarde le projet d’un jour, sans exception et sans amortissement. Deuxièmement, accélérer une activité non critique ne change strictement rien à la date de fin. Le site marketing pourrait être fini en une seule journée, le lancement resterait au jour 39. L’effort consacré hors du chemin critique achète de la marge de sécurité, pas du temps.

Vous pouvez exécuter ces deux passes pas à pas sur un réseau que vous dessinez vous-même dans le visualiseur de la méthode du chemin critique. Il vaut la peine de voir ce qu’est CPM mathématiquement. Trouver un plus long chemin est NP-difficile dans un graphe quelconque, car on pourrait s’en servir pour résoudre le problème du chemin hamiltonien. Sur un graphe orienté acyclique le problème devient facile, linéaire en nombre d’activités et de dépendances, précisément parce qu’un ordre topologique existe. Toute la valeur pratique de CPM repose sur l’acyclicité que la section 4 a vérifiée.

6. La marge, et à qui elle appartient vraiment

La marge est le nombre le plus utile d’un planning et le plus constamment mal utilisé. La confusion vient de ce qu’il en existe deux sortes.

La marge totale est le temps dont une activité peut être retardée sans repousser la date de fin du projet. La marge libre est le temps dont elle peut être retardée sans repousser le début au plus tôt d’aucun de ses successeurs. Dans ce projet, la revue de sécurité (I) a 7 jours de marge totale et 7 jours de marge libre, car le programme bêta qu’elle alimente attend de toute façon les tests d’intégration. Les contenus (G) ont 22 jours de marge totale mais aucune marge libre : retardez-les d’un seul jour et le site marketing commence un jour plus tard.

Cette différence est exactement le piège. Les contenus et le site marketing affichent chacun 22 jours de marge totale, et un chef de projet qui lit le planning ligne par ligne voit 44 jours de mou apparent. Il y en a 22. La marge appartient au chemin A → G → K → L → M, qui dure 17 jours dans un projet de 39, et les deux activités se la partagent.

Le modèle rend cela concret. Consommez les 22 jours entiers sur les contenus : le projet finit toujours au jour 39, mais la marge totale du site marketing tombe de 22 à zéro : il est devenu critique. Retardez-le d’un jour de plus et le projet passe au jour 40. Rien n’a dépassé, rien ne s’est mal passé sur aucune tâche prise isolément, et pourtant la date a glissé, parce que le mou avait déjà été consommé en amont.

La règle pratique est que la marge totale est une propriété d’un chemin et la marge libre une propriété d’une activité. La marge libre est la part que personne d’autre ne peut revendiquer, et c’est le nombre à donner à une équipe comme véritable respiration. Dans ce projet, seules quatre activités en ont : B avec 2 jours, F avec 1, I avec 7 et K avec 22.

7. Le chemin critique n’est pas toujours critique

Le chemin critique invite à une conclusion confortable : surveillez ces huit activités et le projet est sous contrôle. La structure des chemins de ce projet montre pourquoi cela ne suffit pas.

Il y a cinq chemins. Le chemin critique dure 39 jours. Le suivant dure 38 jours, par les paiements au lieu du frontend. Le troisième dure 37 jours, par le design UI au lieu de la base de données et de l’API. Ces deux-là ne sont pas critiques, mais leur marge est d’un et deux jours, moins que l’erreur d’arrondi de la plupart des estimations.

Les praticiens appellent cela le problème du chemin quasi critique (near-critical path), et il a une conséquence nette : un plan peut avoir plusieurs chemins tous critiques en pratique, et un chef de projet qui ne surveille que le chemin officiel sera pris de court par un retard sur un chemin qui semblait sûr. Deux jours de marge sur une tâche de design de dix jours, ce n’est pas du mou, c’est du bruit.

La bonne discipline consiste à classer les chemins par marge plutôt qu’à les répartir entre critiques et non critiques. Dans ce projet, le classement 39, 38, 37, 32, 17 dit ce qu’un surlignage rouge ne peut pas dire : trois des cinq chemins demandent une gestion active, deux non. La section 9 chiffre exactement à quelle fréquence chacun finit par décider de la date.

8. PERT : mettre une probabilité sur la date

CPM suppose que toutes les durées sont connues. Les durées de personne ne sont connues. PERT, mis au point pour le programme Polaris en 1959, y répond en demandant trois estimations par activité au lieu d’une : une durée optimiste a, une durée la plus probable m et une durée pessimiste b.

À partir de là, il calcule une durée espérée et une variance pour chaque activité :

t_e = (a + 4m + b) / 6   et   σ² = ((b − a) / 6)²

Les poids viennent de l’approximation de la durée de chaque activité par une loi bêta, assez souple pour être asymétrique et bornée des deux côtés, contrairement à une loi normale qui autoriserait des durées négatives. Les formules sont des approximations, choisies en partie parce qu’elles se calculaient à la main en 1959.

En sommant le long du chemin critique, on obtient une durée de projet espérée de 39 jours avec une variance totale de 3,778, soit un écart type de 1,944 jour. On invoque alors le théorème central limite : une somme de plusieurs durées d’activités indépendantes est approximativement normale même si les activités individuelles ne le sont pas, ce qui permet de lire les probabilités directement sur la courbe.

Le résultat est bien plus utile qu’une date. Finir en 40 jours a une probabilité de 69,7 % ; en 41 jours, 84,8 % ; en 42 jours, 93,9 %. Dit autrement : s’engager sur 39 jours, c’est s’engager sur un pile ou face ; acheter trois jours de réserve porte la confiance à environ 94 %, et un quatrième jour à 98 %.

Le visualiseur PERT effectue ce calcul de façon interactive, y compris la probabilité d’achèvement pour n’importe quelle date cible. Ce changement de cadre est le véritable apport de PERT. Un planning qui produit une seule date invite à la question « y arriverons-nous ? », qui n’a pas de réponse honnête. Un planning qui produit une distribution invite à « quel niveau de confiance voulez-vous, et combien cela coûtera-t-il ? », qui en a une.

9. Le biais de fusion : pourquoi PERT est optimiste

PERT a un défaut. Il a été identifié quelques années après sa publication, et il est encore couramment ignoré. Le problème est que PERT calcule la distribution du chemin critique puis la traite comme la distribution du projet. Ce n’est pas la même chose.

Le projet n’attend pas le chemin critique. Il attend le chemin qui se révèle le plus long le jour venu. Quand plusieurs chemins convergent vers une activité, celle-ci commence quand arrive le plus lent d’entre eux, et l’espérance d’un maximum est supérieure au maximum des espérances. C’est l’inégalité de Jensen, et en ordonnancement de projet on l’appelle le biais de fusion. Van Slyke l’a mis en évidence par simulation de Monte-Carlo en 1963, et MacCrimmon et Ryavec ont analysé l’ampleur de l’erreur en 1964.

Pour le mesurer, chaque activité de ce projet a été tirée 200 000 fois dans la loi bêta dont la moyenne est exactement sa durée espérée PERT, de sorte que toute différence dans le résultat relève du seul biais de fusion et non d’autres hypothèses. La durée moyenne simulée est de 39,34 jours contre 39,00 pour PERT. Plus utile encore, la probabilité de finir en 39 jours est de 43,8 %, et non les 50 % que suggère PERT.

Les statistiques par chemin expliquent d’où cela vient. Sur l’ensemble des simulations, le chemin critique nominal n’a été le plus long que dans 64,0 % des tirages. Le chemin des paiements l’a emporté dans 26,1 % des cas, et le chemin du design dans 9,9 %. Un projet sur trois finit en retard pour une raison que l’analyse du chemin critique n’a jamais mentionnée.

Un tiers de jour de biais semble négligeable, et sur ce projet il l’est. Il ne l’est pas en général, et il grandit précisément dans les situations qui caractérisent les grands programmes : beaucoup de chemins parallèles de longueur voisine, beaucoup de points de convergence et une forte variance. Un planning dont vingt chemins presque égaux convergent vers un jalon peut être biaisé de plusieurs semaines.

Deux réponses pratiques en découlent. D’abord, si le réseau présente un parallélisme important, simulez-le au lieu de propager la variance le long d’un seul chemin ; le calcul tient en quelques lignes et prend quelques secondes. Ensuite, annoncez un quantile, pas une moyenne. Le P80 de ce projet est de 41,1 jours et le P90 de 42,0. Ce sont des nombres sur lesquels une équipe peut s’engager. La moyenne est le nombre qu’elle manquera une fois sur deux, et un peu plus d’une fois sur deux une fois le biais de fusion pris en compte.

10. Compression : acheter du temps est une coupe minimale

Supposons que 39 jours soit trop long. Beaucoup d’activités peuvent être raccourcies en dépensant de l’argent : plus de personnes, des heures supplémentaires, un fournisseur plus rapide. En ordonnancement, cela s’appelle la compression (crashing), et chaque activité reçoit deux nombres de plus : le nombre maximal de jours dont elle peut être raccourcie et le coût par jour, sa pente de coût.

L’approche naïve consiste à compresser l’activité critique la moins chère. Cela marche exactement une fois. Le développement frontend a la pente la plus basse du chemin critique, 350 $ par jour, donc le raccourcir fait passer le projet de 39 à 38 jours pour 350 $. Le schéma de base de données vient ensuite, à 400 $, et l’amène à 37.

Puis la règle naïve casse. À 37 jours, deux chemins sont critiques en même temps : le chemin d’origine et celui des paiements, qui durent désormais 37 jours chacun. Raccourcir à nouveau le développement frontend ne fait rien gagner, car les paiements garderaient toute leur longueur et le projet durerait toujours 37 jours. Pour gagner un jour, il faut raccourcir tous les chemins critiques simultanément.

Voici la structure. Un ensemble d’activités dont le raccourcissement réduit chaque chemin critique est un ensemble qui touche chaque chemin du début à la fin du projet dans le sous-réseau critique. C’est la définition d’une coupe s-t. Donnez à chaque activité une capacité égale à son coût par jour, et la façon la moins chère d’acheter un jour est la coupe minimale de ce réseau. D’après le théorème flot maximal coupe minimale, elle se trouve en temps polynomial, observation que Fulkerson et Kelley ont tous deux publiée en 1961.

Si l’argument de flot ne vous est pas familier, le théorème flot maximal coupe minimale mérite d’être lu d’abord, car la compression est l’une de ses applications les plus nettes hors des réseaux. Comme les activités sont des sommets et non des arcs, chacune est scindée en une copie d’entrée et une copie de sortie reliées par un arc qui porte sa pente de coût, tandis que les vraies dépendances reçoivent une capacité infinie. La coupe minimale doit alors être composée d’activités, ce qui est bien ce qu’on peut acheter.

Appliqué au projet, cela donne la troisième étape : passer de 37 à 36 jours coûte 650 $, et exige de compresser le développement frontend et les paiements ensemble. Aucun des deux ne fait gagner un jour seul, donc aucune règle du type « prendre la tâche critique la moins chère » n’aurait jamais trouvé la paire. Les tests d’intégration fonctionnent seuls, puisqu’ils sont sur les deux chemins critiques, mais ils coûtent 800 $ contre 650 $ pour la paire.

En poursuivant jusqu’à la limite, on obtient la courbe coût-délai complète : 27 jours est la durée la plus courte atteignable, pour un coût total de compression de 11 950 $. La courbe est convexe, c’est-à-dire que chaque jour supplémentaire coûte au moins autant que le précédent ; c’est une propriété générale de cette construction et un contrôle de cohérence utile pour toute analyse de compression qu’on vous présente.

Le livrable est la courbe, pas le point final. Elle transforme un débat sur la capacité de l’équipe à « aller plus vite » en liste de prix : trois jours pour 1 400 $, six jours pour 3 650 $, douze jours pour 11 950 $. Savoir si l’un d’eux vaut la dépense est une question métier, mais c’est désormais une question chiffrée.

11. Ressources : là où la théorie ne suffit plus

Tout ce qui précède suppose que si deux activités peuvent se dérouler en parallèle, elles le font. Cela suppose un effectif illimité, et aucun projet n’a un effectif illimité. Décider quelles personnes travaillent sur quelles plages, plutôt que quelles tâches se déroulent quand, est le problème voisin des tableaux de service traité dans la planification des horaires du personnel.

Attribuez à chaque activité un besoin en personnel et regardez de nouveau le planning CPM. Si tout commence au plus tôt, la demande sur ce projet culmine à sept personnes du neuvième au quatorzième jour, quand l’API backend, le design UI et le site marketing tournent en même temps. Si l’équipe compte cinq personnes, le planning est une fiction.

Ajouter des limites de ressources transforme le graphe de précédence en problème d’ordonnancement de projet sous contraintes de ressources (RCPSP), et le changement de difficulté n’est pas progressif. CPM est en temps linéaire. Le RCPSP est NP-difficile, comme l’ont prouvé Blazewicz, Lenstra et Rinnooy Kan en 1983, et il est difficile en pratique autant qu’en théorie : des instances de 60 activités de la bibliothèque de référence PSPLIB sont restées non résolues pendant des années.

Les nombres méritent qu’on s’y attarde. Avec cinq personnes, le projet finit toujours en 39 jours : le pic de sept était un artefact de planification, et déplacer du travail dans la marge l’absorbe entièrement. Avec quatre, l’optimum est de 49 jours, un dépassement de 26 % qui n’apparaît nulle part dans l’analyse du réseau. Les deux chiffres ont été vérifiés par un branch and bound exhaustif sur tous les plannings actifs, ce qui n’est faisable que parce que le projet a treize activités.

Le visualiseur d’ordonnancement sous contraintes de ressources vous permet de fixer une capacité et de voir le planning s’étirer. Comme les solutions exactes ne passent pas à l’échelle, la pratique utilise des règles de priorité : ordonnancer à chaque fois l’activité éligible la mieux classée selon une règle donnée. Le choix de la règle compte plus qu’il n’y paraît. Avec une capacité de quatre, la marge totale minimale donne 49 jours, ce qui se trouve être optimal ici, tandis que le début au plus tard le plus tôt, la plus longue durée d’abord et le plus de successeurs d’abord donnent tous 53. Même projet, même contrainte, 8 % d’écart pour un choix de modélisation que la plupart des outils font en silence à votre place.

Le point plus profond est que, sous contraintes de ressources, le chemin critique perd son sens. Deux activités sans aucune dépendance entre elles peuvent tout de même ne pas pouvoir se dérouler ensemble, si bien que la chaîne qui fixe réellement la date de fin peut contenir des paires d’activités liées uniquement par une personne partagée. Les valeurs de marge classiques ne décrivent plus ce qui peut glisser.

12. La chaîne critique, en bref

Cette observation est le point de départ de la gestion de projet par chaîne critique, introduite par Eliyahu Goldratt en 1997. La chaîne critique est la plus longue séquence d’activités qui tient compte à la fois des précédences et des conflits de ressources, et c’est le bon objet à surveiller quand le personnel est rare.

Sa seconde idée porte sur l’endroit où l’on garde le temps de sécurité. Les estimations individuelles sont généralement gonflées, et ce matelas est consommé de toute façon, soit parce que le travail s’étend jusqu’à remplir le temps disponible, soit parce qu’une date de début confortable est prise. La chaîne critique retire le matelas des activités individuelles et le regroupe dans des tampons explicites : un tampon de projet à la fin de la chaîne, et des tampons d’alimentation là où les chemins non critiques la rejoignent. Le regroupement est statistiquement fondé, pour une raison différente du biais de fusion : l’écart type d’une somme de durées indépendantes croît comme la racine carrée de leur nombre, donc un tampon partagé peut être plus petit que les marges individuelles qu’il remplace tout en offrant la même protection.

La méthode est réellement contestée. Herroelen et Leus, entre autres, ont soutenu que ses promesses en matière d’ordonnancement sont plus faibles qu’annoncé et que des règles de dimensionnement des tampons comme « la moitié de la longueur de la chaîne » n’ont aucun fondement analytique. L’idée de regrouper les tampons est solide ; le cadre qui l’entoure est une méthode de management et non un théorème, et il vaut mieux garder les deux séparés.

13. Ce qui est facile, ce qui est difficile

L’ordonnancement de projet a une frontière de complexité exceptionnellement nette, et savoir où elle passe vous dit quelles promesses un outil peut tenir.

Facile, c’est-à-dire polynomial et instantané à toute taille réaliste. Détecter les cycles et produire un ordre topologique. Les passes avant et arrière, donc la durée du projet, le chemin critique et toutes les marges. Énumérer par marge les chemins qui comptent. La coupe minimale pour un jour de compression, et en la répétant, toute la courbe coût-délai. La simulation de Monte-Carlo de la distribution de la durée. Tout cela est linéaire ou presque, et un projet de cent mille activités ne pose aucun problème.

Difficile, c’est-à-dire NP-difficile, sans algorithme polynomial en vue. L’ordonnancement sous contraintes de ressources, dans pratiquement toutes ses variantes : capacité fixe, plusieurs types de ressources, préemption autorisée ou non. Le lissage des ressources, qui cherche le profil le plus régulier plutôt que le planning le plus court. Les arbitrages coût-délai avec des options discrètes par activité au lieu d’une pente continue, ce qui fait perdre la formulation en flots. L’énumération de tous les chemins, dont le nombre peut croître exponentiellement avec le nombre d’activités.

Le schéma est presque une règle empirique : demander un planning optimal en temps seulement est facile, et ajouter une ressource limitée et partagée le rend difficile. Les deux exceptions de la liste difficile confirment la règle au lieu de la briser, puisque aucune ne demande un optimum unique : l’énumération des chemins demande toutes les réponses, et l’arbitrage discret demande un choix sur un menu à chaque activité. Les contraintes de temps forment un ordre partiel, et les ordres partiels sont ce que les graphes orientés acycliques traitent bien. Une ressource partagée crée des contraintes entre des activités sans aucune dépendance entre elles, et la structure acyclique qui rendait tout traitable ne décrit plus le problème.

C’est pourquoi les logiciels de planification donnent un chemin critique exact et un plan lissé en ressources approximatif, généralement sans le dire. Le premier est un théorème ; le second est une heuristique dont personne ne rapporte la qualité. Ce n’est qu’un coin d’un domaine bien plus vaste : la recherche opérationnelle couvre les méthodes d’optimisation dont la moitié difficile de cette liste a besoin.

14. Erreurs de modélisation et comment les éviter

Cinq erreurs expliquent la plupart des mauvais plannings, et aucune ne tient à une mauvaise estimation.

Traiter la marge comme une réserve qu’on possède. La marge totale est partagée le long d’un chemin. Deux équipes à qui l’on annonce chacune trois semaines de mou, sur le même chemin, en consommeront six à elles deux et s’étonneront que la date bouge. Communiquez la marge libre aux équipes et gardez la marge totale comme nombre de planification.

Ne surveiller que le chemin critique. Un chemin avec deux jours de marge n’est pas sûr, il est quasi critique, et dans ce projet le chemin critique nominal ne décide du résultat que deux fois sur trois. Classez les chemins par marge et pilotez tout ce qui se trouve à quelques jours de zéro.

Annoncer la moyenne comme date. La durée espérée est à peu près un pile ou face avant même le biais de fusion, et un peu pire après. Si une date entre dans un contrat, ce doit être un quantile, et il faut dire lequel.

Supposer l’indépendance. La somme des variances de PERT comme la simulation de la section 9 supposent que les durées des activités sont indépendantes. Elles ne le sont généralement pas : le même estimateur optimiste en a produit plusieurs, la même équipe en réalise plusieurs, et un mauvais fournisseur en touche plusieurs à la fois. La corrélation gonfle la variance du total bien au-delà de ce qu’indique l’une ou l’autre méthode, donc traitez la dispersion comme un plancher et non comme une estimation.

Planifier comme si l’effectif était illimité. Une date CPM calculée sans limites de ressources est une borne inférieure, pas un plan. Vérifiez le profil de ressources avant de publier la date ; sur ce projet, la différence entre vérifier et ne pas vérifier était de dix jours.

Une sixième mérite d’être citée parce qu’elle est invisible : une dépendance qui n’existe pas vraiment. Les plans accumulent des contraintes ajoutées par confort, des enchaînements qui reflètent l’organisation de l’équipe plutôt qu’une nécessité technique. Ajouter un arc ne peut qu’allonger le plus long chemin ou le laisser tel quel, jamais le raccourcir, donc chaque dépendance inutile est un pari à sens unique contre le planning. Auditer le chemin critique arc par arc, en demandant si chacun est une vraie contrainte, est souvent la compression de planning la moins chère disponible, et contrairement au crashing, elle ne coûte rien.

16. Références

Les articles à l’origine des méthodes de cet article, par ordre chronologique.

1. Clark, W. (1922). The Gantt Chart: A Working Tool of Management. Ronald Press.
2. Kelley, J. E. et Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
3. Malcolm, D. G., Roseboom, J. H., Clark, C. E. et Fazar, W. (1959). “Application of a technique for research and development program evaluation.” Operations Research, 7(5), 646–669.
4. Fulkerson, D. R. (1961). “A network flow computation for project cost curves.” Management Science, 7(2), 167–178.
5. Kelley, J. E. (1961). “Critical-path planning and scheduling: mathematical basis.” Operations Research, 9(3), 296–320.
6. Ford, L. R. et Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
7. Van Slyke, R. M. (1963). “Monte Carlo methods and the PERT problem.” Operations Research, 11(5), 839–860.
8. MacCrimmon, K. R. et Ryavec, C. A. (1964). “An analytical study of the PERT assumptions.” Operations Research, 12(1), 16–37.
9. Klingel, A. R. (1966). “Bias in PERT project completion time calculations for a real network.” Management Science, 13(4), B194–B201.
10. Wiest, J. D. (1967). “A heuristic model for scheduling large projects with limited resources.” Management Science, 13(6), B359–B377.
11. Elmaghraby, S. E. (1977). Activity Networks: Project Planning and Control by Network Models. Wiley.
12. Blazewicz, J., Lenstra, J. K. et Rinnooy Kan, A. H. G. (1983). “Scheduling subject to resource constraints: classification and complexity.” Discrete Applied Mathematics, 5(1), 11–24.
13. Kolisch, R. et Sprecher, A. (1997). “PSPLIB: a project scheduling problem library.” European Journal of Operational Research, 96(1), 205–216.
14. Goldratt, E. M. (1997). Critical Chain. North River Press.
15. Brucker, P., Drexl, A., Möhring, R., Neumann, K. et Pesch, E. (1999). “Resource-constrained project scheduling: notation, classification, models, and methods.” European Journal of Operational Research, 112(1), 3–41.
16. Herroelen, W. et Leus, R. (2001). “On the merits and pitfalls of critical chain scheduling.” Journal of Operations Management, 19(5), 559–577.
17. Demeulemeester, E. et Herroelen, W. (2002). Project Scheduling: A Research Handbook. Kluwer Academic Publishers.
18. Herroelen, W. et Leus, R. (2005). “Project scheduling under uncertainty: survey and research potentials.” European Journal of Operational Research, 165(2), 289–306.
19. Kolisch, R. et Hartmann, S. (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: an update.” European Journal of Operational Research, 174(1), 23–37.
20. Hartmann, S. et Briskorn, D. (2010). “A survey of variants and extensions of the resource-constrained project scheduling problem.” European Journal of Operational Research, 207(1), 1–14.
21. Trietsch, D. et Baker, K. R. (2012). “PERT 21: fitting PERT/CPM for use in the 21st century.” International Journal of Project Management, 30(4), 490–502.