Pourquoi un PI Planning à cinq équipes ne se construit plus à la main

Il y a plus de façons de mélanger un jeu de tarot que d’atomes dans l’univers observable. Le mème ordre de grandeur s’applique à l’ordre de traitement de 78 tickets. Cette page explique pourquoi, ce que la théorie de la complexité établit exactement, et ce que cela change pour la préparation d’un PI.

1. Un ordre de grandeur

Un jeu de tarot compte 78 cartes. Le nombre de façons de les ordonner est 78 ! (factorielle de 78), soit environ 1,13 × 10¹¹⁵.

Le nombre d’atomes de l’univers observable est estimé de l’ordre de 10⁸⁰, avec des estimations allant de 10⁷⁸ à 10⁸². Mème à la borne haute, l’écart dépasse trente puissances de dix.

Remplacez les cartes par 78 tickets : le nombre d’ordres de traitement possibles est identique, avant d’avoir appliqué la moindre contrainte de capacité ou de dépendance. Les méthodes de recherche usuelles pour ce type de problème représentent d’ailleurs une solution par une liste ordonnée d’activités, décodée ensuite en planning (Kolisch & Hartmann, 2006).

Ce nombre donne l’échelle. Il ne démontre rien : un grand espace de recherche peut cacher un problème facile. La démonstration vient de la théorie de la complexité, section 3.

2. Un PI Planning est un RCPSP

Le RCPSP (Resource-Constrained Project Scheduling Problem) consiste à ordonnancer des activités soumises à des contraintes de précédence et de ressources, de façon à minimiser la durée totale (Hartmann & Briskorn, 2010). C’est le problème de référence de l’ordonnancement de projets.

3. Ce que « NP-difficile au sens fort » établit

Le RCPSP est NP-difficile au sens fort (Blazewicz, Lenstra & Rinnooy Kan, 1983). Deux notions :

• NP-difficile : aucun algorithme polynomial n’est connu, et il n’en existe pas sauf si P = NP, hypothèse que la communauté tient pour vraie sans l’avoir démontrée.
• Au sens fort : le problème reste difficile mème lorsque les valeurs numériques (durées, capacités) sont petites, bornées par un polynôme de la taille de l’instance. Il n’existe alors pas non plus d’algorithme pseudo-polynomial, sauf si P = NP (Garey & Johnson, 1979). Les durées et les capacités d’un PI sont précisément des petits entiers : l’astuce numérique n’aide pas.

4. Trois questions, trois niveaux de difficulté

Le tableur et le tableau blanc font le premier travail. Les deux autres sont des recherches.

5. Ce que cela change, et ce que la théorie n’établit pas

La théorie décrit le pire cas. Une instance petite ou peu contrainte se résout à la main, et l’expérience d’un RTE suffit souvent. Le seuil d’environ cinq équipes et cinq epics est notre seuil de qualification, pas un résultat de la théorie : c’est l’ordre de grandeur à partir duquel nous constatons qu’un plan construit à la main ne peut plus être situé parmi les alternatives.

Au-delà de ce seuil, un plan fait à la main respecte ou non les contraintes, et l’on ne sait pas mesurer son écart avec les autres plans possibles. Le point de comparaison utile n’est pas l’optimum théorique, que personne ne calcule à l’échelle d’un portefeuille réel, mais le plan que vous produisez aujourd’hui.

6. Notre approche

Konatus traite ce problème par un algorithme génétique, une recherche stochastique. C’est de l’IA classique, pas un modèle de langage. Les contraintes et le critère sont déclarés : ils sont lisibles et discutables, et rien n’est appris sur vos données.

• Le résultat est le meilleur ordonnancement sous vos contraintes. Ce n’est pas l’optimum mathématique.
• Le plan se vérifie : capacités, antériorités et priorités se contrôlent indépendamment du chemin qui l’a trouvé.
• Deux exécutions peuvent donner deux plans admissibles différents : ce sont les scénarios que l’on compare. Chaque exécution est archivée en version.
• Une simulation AlignIQ dure cinq minutes.

Références

• Blazewicz, J., Lenstra, J.K., Rinnooy Kan, A.H.G. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete Applied Mathematics 5(1), 11–24.
• Garey, M.R., Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman.
• Hartmann, S., 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.
• Kolisch, R., Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: an update. European Journal of Operational Research 174(1), 23–37.
• Artigues, C., Hartmann, S., Vanhoucke, M. (2026). Fifty years of research on resource-constrained project scheduling explored. European Journal of Operational Research 328(2).