M thodes d''optimisation Combinatoire Sur Grilles de Calcul

La rsolution exacte de problmes d'optimisation combinatoire de grande taille constitue un vrai dfi pour les grilles informatiques. En effet, il est ncessaire de repenser les algorithmes de rsolution pour prendre en compte les caracteristiques de tels environnements, notamment leur grande chelle, l'htrognit et la disponibilit dynamique de leurs ressources, et leur nature multi-domaine d'administration. Dans cette thse, nous avons propos une nouvelle approche de passage sur grilles de calcul des mthodes exactes de type Branch-and-Bound appele B&B@Grid. Cette approche est base sur un codage des units de travail (sous-problmes) sous forme d'intervalles permettant de minimiser le cot des communications induites par les oprations de rgulationde charge, de tolrance aux pannes et de dtection de la terminaison. Cette approche, environ 100 fois plus performante en termes de cot de communication que la meilleure approche connue, a permis la rsolution optimale sur la grillenationale Grid5000 d'une instance standard du problme du Flow-Shop reste non rsolue depuis une quinzaine d'annes.