Abstract FR:

Ce memoire presente un ensemble original de techniques de propagation de contraintes de ressources en ordonnancement. Quatre types de ressources sont etudies : (1) les ressources disjonctives non-preemptives, (i. E. , de capacite 1 sur lesquelles les activites ne sont pas interrompues), (2) les ressources disjonctives preemptives, (3) les ressources cumulatives et (4) les ressources dites surchargees, sur lesquelles des activites peuvent etre sous-traitees. _ dans le cas preemptif, les outils mis en place sont totalement originaux. Ils generalisent les nombreux travaux effectues sur les ressources disjonctives non-preemptives. _ dans le cas cumulatif, les methodes deductives proposees reprennent en partie des resultats connus. L'accent est mis sur la caracterisation theorique et sur le cout algorithmique de ces methodes. Elles sont comparees avec les bornes inferieures classiques de recherche operationnelle. _ dans le cas des ressources surchargees, les mecanismes de propagation elabores reposent sur differentes formulations du probleme de la minimisation du nombre de jobs en retard sur une machine. Nous decrivons un algorithme de resolution pour la version preemptive de ce probleme - algorithme qui ameliore la meilleure complexite connue. Enfin, il est montre que la version ponderee du meme probleme est polynomiale si les durees sont egales, et ce dans le cas preemptif comme dans le cas non-preemptif. Nous illustrons l'efficacite des nouveaux algorithmes de propagation sur un ensemble de problemes combinatoires. _ le probleme du job-shop preemptif est tres bien resolu (toutes les instances de la litterature de taille 10*10 sont fermees). _ la procedure permettant de resoudre le probleme de gestion de projet a contraintes de ressources est tres efficace sur certaines instances. _ les resultats obtenus sur le probleme de la minimisation du nombre de jobs en retard sur une machine sont les meilleurs connus a ce jour.