Le choix d’une métaheuristique contre une méthode exacte n’est pas une préférence d’ingénieur, c’est une conséquence de la taille des instances. Sur un ordonnancement de quelques dizaines d’activités, la programmation linéaire en nombres entiers et la programmation par contraintes font mieux qu’un algorithme génétique : elles rendent une solution et la preuve qu’aucune meilleure n’existe. Sur un portefeuille de plusieurs centaines de milliers d’éléments de travail, elles ne rendent rien dans le temps dont dispose un comité. La thèse de cet article est que cette bascule justifie l’emploi d’une métaheuristique, à condition d’en assumer la contrepartie.
Ce que prouve une méthode exacte, et ce que cela coûte
Une méthode exacte explore l’espace des solutions de façon exhaustive, mais intelligemment : elle élague les branches dont elle peut démontrer qu’elles ne contiennent pas de meilleure solution que celle déjà trouvée. La séparation-évaluation appliquée au RCPSP suit ce principe, et la littérature compte des procédures de ce type depuis des décennies (Brucker, Drexl, Möhring, Neumann et Pesch, European Journal of Operational Research 112(1), 1999).
La garantie obtenue est forte : à l’arrêt, le solveur rend une solution et un écart certifié avec la borne. Le coût est que l’élagage ne suffit pas toujours. Le RCPSP est NP-difficile au sens fort (Blazewicz, Lenstra et Rinnooy Kan, Discrete Applied Mathematics 5(1), 1983) : au sens fort signifie que la difficulté persiste même lorsque les durées et les capacités sont de petits entiers, ce qui est précisément le régime d’un portefeuille réel, où les durées se comptent en jours et les capacités en personnes. Il n’existe alors pas non plus d’algorithme pseudo-polynomial, sauf si P = NP.
Les instances de référence utilisées par la communauté donnent la mesure de l’écart entre la théorie et la pratique. La bibliothèque PSPLIB (Kolisch et Sprecher, European Journal of Operational Research 96(1), 1997) sert d’étalon depuis près de trente ans, et une partie de ses instances restait ouverte vingt ans après sa publication : Araujo et ses coauteurs en dénombraient deux cent quinze pour lesquelles l’optimalité n’était pas démontrée, et leur travail sur les coupes et le prétraitement a permis d’en clore sept cent cinquante-quatre, toutes variantes confondues (Computers & Operations Research 113, 2020). Les plus grandes de ces instances comptent cent vingt activités, soit moins qu’un seul projet d’un portefeuille industriel.
Ce que rend une métaheuristique
Une métaheuristique renonce à la preuve et garde l’échelle. Elle explore l’espace des plans admissibles, retient le meilleur rencontré, et s’arrête sur un budget de temps fixé. Ce qu’elle rend est un plan qui respecte les contraintes, pas une démonstration qu’il n’en existe pas de meilleur.
L’algorithme génétique est l’une de ces méthodes. Il maintient une population de solutions, les combine entre elles et introduit des variations, en conservant à chaque génération celles qui se comportent le mieux selon le critère retenu. Appliqué au RCPSP, il se compare favorablement aux autres approches de la même famille (Hartmann, Naval Research Logistics 45(7), 1998), et les évaluations comparatives menées sur PSPLIB documentent depuis longtemps le comportement respectif de ces méthodes (Kolisch et Hartmann, European Journal of Operational Research 174(1), 2006).
Le point important est que ce renoncement à la preuve n’est pas un renoncement à la vérification. Un plan produit par une métaheuristique se contrôle exactement comme un plan produit par un solveur exact : les capacités sont respectées ou non, les antériorités sont respectées ou non, les jalons tiennent ou non. Cette vérification est un calcul rapide, indépendant de la méthode qui a produit le plan. Ce qui n’est pas vérifiable, c’est la distance au meilleur plan possible.
Le codage par liste d’activités, et pourquoi il importe
La façon dont une solution est représentée conditionne le comportement de la recherche. La représentation la plus courante pour le RCPSP est la liste d’activités : une solution est un ordre de passage des activités, compatible avec les contraintes de précédence, c’est-à-dire une liste dans laquelle aucune activité n’apparaît avant celles dont elle dépend.
Cette liste n’est pas un planning. Elle est transformée en planning par un décodage, appelé schedule generation scheme, qui parcourt la liste et place chaque activité à la première date où les ressources nécessaires sont disponibles. Deux schémas classiques existent, l’un qui avance activité par activité, l’autre qui avance par instant de décision ; le choix du schéma a un effet mesurable sur la qualité des plans produits, et cet effet est documenté dans la littérature comparative (Kolisch et Hartmann, 2006).
L’intérêt de ce codage est double. D’une part, toute liste compatible avec les précédences se décode en un planning admissible : la recherche ne produit jamais de plan impossible, parce que les contraintes de capacité sont satisfaites par construction au moment du décodage. D’autre part, les opérateurs de croisement et de mutation travaillent sur des listes, un objet simple, plutôt que sur des dates, ce qui rend la combinaison de deux solutions bien plus facile à définir.
La contrepartie, qu’il faut assumer
Une recherche stochastique n’explore pas deux fois le même chemin. Deux exécutions sur les mêmes données produisent donc deux plans admissibles qui peuvent différer : un ticket placé à l’itération deux plutôt qu’à l’itération trois, une équipe chargée différemment.
Présenter cela comme un défaut serait une erreur d’analyse. Ces deux plans respectent tous deux les contraintes déclarées, ce sont donc deux solutions valides du même problème, et le fait qu’il en existe plusieurs est une propriété du problème, pas de la méthode. Ce que cela produit n’est pas de l’instabilité mais des scénarios, et un comité qui dispose de deux scénarios admissibles comparables sur leurs conséquences est mieux outillé qu’un comité qui dispose d’un seul plan dont nul ne sait d’où il vient.
Deux conditions rendent cette propriété exploitable. Il faut que chaque exécution soit archivée, de sorte qu’un plan puisse être retrouvé et comparé plus tard. Il faut que les contraintes et le critère soient déclarés et lisibles, sans quoi la comparaison entre deux scénarios ne porte sur rien d’explicite.
Le point de comparaison utile, en pratique, n’est jamais l’optimum théorique. C’est le plan que l’organisation produit aujourd’hui, à la main ou dans un tableur, dont personne ne sait non plus s’il est le meilleur, et dont la construction a coûté plusieurs jours-homme. Chez Konatus, une simulation AlignIQ dure cinq minutes ; une simulation KoAlign, de dix à trente minutes.
Sur votre dernier plan, combien d’alternatives avez-vous pu comparer avant de le valider ?
