Stratégies de résolution exacte du problème RCCP pour améliorer la planification tactique

Cette thèse aborde la problématique de la planification tactique de projets, à travers l’étude du Rough-Cut Capacity Planning (RCCP). Ce type de modèle s’applique aux premières phases des projets et vise à optimiser, pour chaque période, les intensités d’exécution des lots de travail nécessaires à la réalisation du projet. L’objectif est d’assurer la cohérence entre les besoins du projet et la disponibilité des ressources critiques sur un horizon de moyen terme, avant la phase d’ordonnancement détaillée. L’objectif général de cette recherche est de proposer de nouvelles formulations linéaires en nombres entiers mixtes (MIP) permettant de résoudre efficacement le problème du RCCP et ses extensions, tout en améliorant à la fois la qualité des solutions et la performance numérique des modèles existants. Les travaux s’appuient sur une analyse approfondie du comportement des solveurs modernes et sur une reformulation méthodique des contraintes, afin de réduire la complexité du modèle, d’améliorer ses performances de résolution et, par la mème, d’aborder des extensions plus complexes, également visées par les objectifs de cette recherche. La première contribution de cette thèse consiste à développer un nouveau modèle MIP en temps continu (CT) pour le RCCP, fondé sur une analyse approfondie du comportement du solveur d’optimisation. L’étude du comportement du solveur CPLEX a mis en évidence plusieurs sources de ralentissement, notamment la symétrie des solutions, qui bloque la progression de la borne inférieure, ainsi que la faiblesse de la relaxation linéaire après le prétraitement du solveur. Les résultats expérimentaux montrent une réduction moyenne de 72 % du nombre d’itérations du dual simplexe et une diminution significative du gap d’optimalité (c’est-à-dire du gap d’intégralité à la fin de la résolution), permettant de résoudre des instances de taille supérieure à celles traitées avec le modèle de base. Cette contribution met également en lumière l’intérêt d’une analyse du comportement du solveur comme levier d’amélioration des formulations MIP. Enfin, une approche bi-objectif combinant les variantes Time-driven et Resource-driven a été proposée afin d’aborder des contextes de planification plus proches des applications industrielles réelles. La deuxième contribution vise à améliorer davantage la formulation en traitant la variante Time-driven, à travers la résolution de deux anomalies principales : l’instabilité numérique et la faiblesse de la relaxation linéaire après le prétraitement. Pour cela, une étude comparative a été menée entre plusieurs formulations du RCCP afin d’évaluer leurs performances structurelles. Huit modèles ont été comparés selon deux axes : le temps de résolution et la qualité des solutions. Les résultats montrent que la formulation en temps continu, basée sur les step variables et l’ajout de variables continues, surpasse les autres versions en temps continu pour l’ensemble des critères étudiés. Elle offre des bornes plus serrées, un arbre de branchement plus restreint et une convergence plus rapide vers l’optimalité. Une étude théorique a également été menée entre les modèles testés, montrant que la qualité de la relaxation linéaire n’est qu’un facteur parmi d’autres influençant la performance globale du modèle. En moyenne, le modèle proposé est environ sept fois plus rapide que le modèle en temps continu présenté dans le premier article, et la qualité des solutions est significativement supérieure, atteignant jusqu’à 67 % de gain au niveau des coûts dans certaines instances. Cette étude met en évidence qu’un modèle en temps continu peut rivaliser, voire surpasser, les modèles en temps discret souvent privilégiés dans la littérature pour leur complexité moindre par rapport aux formulations en temps continu, tout en conservant une flexibilité dans la représentation du temps et dans la manière dont les relations de précédence sont traitées, notamment lorsque les périodes sont agrégées. Cette étude comparative a également permis d’identifier les éléments structurels qui influencent le plus le comportement du solveur, notamment les relations de précédence et la manière de lier les périodes aux dates de début et de fin des lots de travail, offrant ainsi des pistes méthodologiques pour la conception de modèles plus performants. La troisième contribution de la thèse concerne l’intégration du nivellement des ressources (resource leveling) au modèle RCCP. Ce volet vise à lisser les fluctuations de charge sur l’horizon de planification afin d’éviter les périodes de surcharge et de sous-utilisation, qui nuisent à la productivité et augmentent les coûts liés à la main-d’œuvre. Pour ce faire, un modèle étendu a été proposé, permettant des intensités non uniformes entre les ressources. Les expériences numériques montrent que ce modèle permet une réduction moyenne de 35 %de la variance inter-périodes, tout en maintenant la dur´ee globale du projet. Une contrainte imposant un profil de charge unimodal a été intégrée, de sorte que la charge augmente jusqu’`a un pic avant de décroitre jusqu’à la fin de l’horizon. Cette approche permet d’éviter les cycles de recrutement et de licenciement, stabilise la charge globale et offre une représentation plus réaliste du fonctionnement des organisations. Une stratégie incrémentale de résolution a également été développée afin d’améliorer l’efficacité computationnelle du modèle étendu. Cette stratégie ajuste progressivement l’horizon de planification et intègre une procédure d’amélioration incrémentale des bornes inférieures. Cette méthode réduit les temps de calcul sur les grandes instances allant jusqu’à un gain d’un ordre de grandeur. Enfin, une analyse bi-objectif, basée sur la méthode ε-contrainte, a permis d’explorer le compromis entre la durée totale du projet (Cmax) et la stabilité du profil de charge. L’étude des fronts de Pareto obtenus révèle une corrélation entre la variabilité des charges et le temps d’achèvement du projet. Mots-clés : Planification tactique, RCCP, MIP, Nivellement de ressources, Optimisation bi-objectif, Profil de charge unimodal, CPLEX.