An extension of energetic reasoning for the cumulative scheduling problem and its application to solving the RCPSP

Cette thèse propose une extension du raisonnement énergétique appliqué au problème d’ordonnancement cumulatif et explore son intégration dans le problème d’ordonnancement de projets sous contraintes de ressources. Les approches classiques de raisonnement énergétique, bien qu’efficaces, reposent sur des relaxations continues qui négligent la nature discrète des capacités de ressources. Cette approximation limite leur aptitude à détecter certaines infaisabilités et à produire des bornes inférieures précises. Afin de pallier cette limite, nous redéfinissons le bilan énergétique en tenant compte des portions de tâches exécutées en dehors des intervalles temporels considérés et en intégrant explicitement les contraintes d’intégralité des ressources. Cette évolution conceptuelle conduit à un test de faisabilité plus puissant et à des bornes inférieures significativement renforcées. L’une des contributions majeures de ce travail réside dans la formulation d’un nouveau problème de tripartition, résolu par programmation dynamique. Ce modèle transforme l’évaluation énergétique en une optimisation de type problème du sac à dos, permettant de capturer la véritable structure combinatoire de l’utilisation des ressources. Nous proposons également plusieurs stratégies avancées de calcul de bornes inférieures (notamment des approches destructives et constructives), ainsi qu’une analyse des ressources redondantes, prolongeant les travaux fondateurs de Carlier et Néron [1] afin d’obtenir des estimations du makespan plus serrées et plus réalistes. Les expérimentations numériques menées démontrent l’efficacité pratique du cadre développé : le vérificateur énergétique enrichi détecte des infaisabilités ignorées par les méthodes existantes, fournit des bornes inférieures plus fortes et améliore les performances des solveurs lorsqu’il est intégré à des systèmes industriels de programmation par contraintes. Au-delà du contexte de l’ordonnancement cumulatif, ces résultats illustrent la portée générale du raisonnement énergétique amélioré pour les problèmes d’optimisation sous contraintes de ressources, établissant ainsi cette approche comme un outil à la fois rigoureux, performant et polyvalent pour la recherche théorique et appliquée en ordonnancement.