La resolution exacte de problemes d'optimisation combinatoire de grande taille constitue un vrai defi pour les grilles informatiques. En effet, il est necessaire de repenser les algorithmes de resolution pour prendre en compte les caracteristiques de tels environnements, notamment leur grande echelle, l'heterogeneite et la disponibilite dynamique de leurs ressources, et leur nature multi-domaine d'administration. Dans cette these, nous avons propose une nouvelle approche de passage sur grilles de calcul des methodes exactes de type Branch-and-Bound appelee B&B@Grid. Cette approche est basee sur un codage des unites de travail (sous-problemes) sous forme d'intervalles permettant de minimiser le cout des communications induites par les operations de regulationde charge, de tolerance aux pannes et de detection de la terminaison. Cette approche, environ 100 fois plus performante en termes de cout de communication que la meilleure approche connue, a permis la resolution optimale sur la grillenationale Grid5000 d'une instance standard du probleme du Flow-Shop restee non resolue depuis une quinzaine d'annees."