Approches géométriques et duales pour l'ordonnancement cumulatif

This work falls in the scope of constraint-based scheduling. In this framework, the most frequently encountered resource constraint is the cumulative, which enables the modeling of parallel processes.In this thesis, we study the cumulative constraint with the help of tools rarely used in constraint programming (polyhedral analysis, linear programming duality, projective geometry duality) and propose two contributions for the domain.Cumulative strengthening is a means of generating tighter redundant cumulative constraints, analogous to the generation of cuts in integer linear programming. This is one of the first examples of a redundant global constraint.Energy Reasoning is an extremely powerful propagation for cumulative constraint, with hitherto a high complexity of O(n^{3}). We propose an algorithm that computes this propagation with a O(n^{2}log n) complexity, which is a significant improvement of this algorithm known for more than 25 years.Ce travail s’inscrit dans le domaine de l’ordonnancement à base de programmation par contraintes. Dans ce cadre, la contrainte de ressource la plus fréquemment rencontrée est la cumulative, qui permet de modéliser des processus se déroulant de manière parallèle.Nous étudions dans cette thèse la contrainte cumulative en nous aidant d’outils rarement utilisés en programmation par contraintes (analyse polyédrale, dualité de la programmation linéaire, dualité de la géométrie projective) et proposons deux contributions pour le domaine.Le renforcement cumulatif est un moyen de générer des contraintes cumulatives redondantes plus serrées, de manière analogue à la génération de coupes en programmation linéaire entière. Il s'agit ici de l'un des premiers exemples de contrainte globale redondante.Le Raisonnement Énergétique est une propagation extrêmement puissante pour la contrainte cumulative, avec jusque-là une complexité élevée en O(n^{3}). Nous proposons un algorithme qui calcule cette propagation avec une complexité O(n^{2}log n), ce qui constitue une amélioration significative de cet algorithme connu depuis plus de 25 ans