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.

Abstract

This thesis addresses the issue of tactical planning of projects through the study of the Rough-Cut Capacity Planning (RCCP) problem. This type of model applies to the early planning phases of projects and aims to optimize, for each period, the execution intensities of the work packages required for project completion. The objective is to ensure consistency between project requirements and the availability of critical resources over a medium-term horizon, prior to the detailed scheduling phase. The general objective of this research is to propose new mixed-integer linear programming (MIP) formulations to efficiently solve the RCCP problem and its extensions, while improving both the solution quality and the numerical performance of existing models. The work is based on an in-depth analysis of modern solver behavior and on a systematic reformulation of constraints, in order to reduce model complexity, enhance computational performance, and thereby enable the treatment of more complex extensions, which are also part of the objectives of this research. The first contribution of this thesis consists in developing a new continuous-time (CT) MIP formulation for the RCCP, grounded in a detailed analysis of the solver’s computational behavior. The study of the CPLEX solver revealed several sources of inefficiency, notably the symmetry of solutions that hinders the progress of the lower bound, and the weakness of the linear relaxation after the presolve phase. Experimental results show an average reduction of 72 % in the number of dual simplex iterations and a significant decrease in the optimality gap, enabling the resolution of larger instances than those solvable with the base model. This contribution also highlights the relevance of solver behavior analysis as a lever for improving MIP formulations. Finally, a bi-objective approach combining the Time-driven and Resource-driven variants was proposed to address planning contexts closer to real industrial applications. The second contribution aims to further enhance the formulation by refining the Time-driven variant, addressing two main issues: numerical instability and the weakness of the linear relaxation after presolve. To this end, a comparative study was conducted among several RCCP formulations to assess their structural performance. Eight models were compared according to two main criteria: solving time and solution quality. Results show that the continuous-time formulation based on step variables and the addition of continuous variables outperforms other continuous-time versions across all criteria studied. It provides tighter bounds, a smaller branching tree, and faster convergence to optimality. A theoretical analysis was also conducted among the tested models, demonstrating that the quality of the linear relaxation is only one of several factors influencing overall model performance. On average, the proposed model is about seven times faster than the best previous continuous formulation, and the solution quality is significantly higher, achieving up to a 67 % improvement in cost in some instances. This study demonstrates that a continuous-time model can rival and even surpass discrete-time formulations, often preferred in the literature for their lower numerical complexity, while maintaining greater flexibility in time representation and in handling precedence relations, particularly when periods are aggregated. The comparative analysis also identified the structural components that most influence solver behavior, notably the precedence relations and the linkage between periods and the start and finish dates of work packages, thereby offering methodological insights for the design of more efficient models. The third contribution of this thesis focuses on the integration of resource leveling into the RCCP model. This part aims to smooth workload fluctuations over the planning horizon in order to avoid periods of overload and underutilization, which reduce productivity and increase labor-related costs. To achieve this, an extended model was proposed, allowing non-uniform execution intensities among resources. Numerical experiments show that this model achieves an average reduction of 35 % in inter-period variance while maintaining the overall project duration. A constraint enforcing a unimodal workload profile was also integrated, ensuring that the workload increases to a peak and then decreases until the end of the planning horizon. This approach prevents cycles of hiring and layoffs, stabilizes the overall workload, and provides a more realistic representation of organizational behavior. An incremental solution strategy was also developed to enhance the computational efficiency of the extended model. This strategy progressively adjusts the planning horizon and incorporates an incremental improvement procedure for lower bounds. The method reduces computation times for large instances by roughly an order of magnitude. Finally, a bi-objective analysis based on the ε-constraint method was conducted to explore the trade-off between total project duration (Cmax) and workload stability. The analysis of the resulting Pareto fronts reveals a clear correlation between workload variability and project completion time. Keywords: Tactical planning, RCCP, MIP, Resource leveling, Bi-objective optimization, Unimodal workload profile, CPLEX.