Algorithmes d'ordonnancement pour les nouveaux supports d'exécution

Grid processing and clusters are today a cost efficient alternative tostand-alone high performance multi-processors. Large national projectssuch as GRID5000 in France are relying on this kind of architectures. Thischange in the high performance computing landscape calls for new dedicated algorithms to get the best out of these new machines. To define such algorithms and to prove their efficiency, we have to consider newcomputing models, which closely simulates the hardware while stayingsimple enough to be understandable and useful. In this thesis, we studiedtwo models in particular, chosen among the post important for thesearchitectures. For each model we provided optimal polynomial algorithmsfor some problems, or approximation algorithms and NP-hardness proofs ifneeded.Les nouveaux supports d'exécution que sont les grilles de processeursapparaissent aujourd'hui comme une alternative économiquement viable aux grands systèmes de calcul centralisés. De grands projets nationaux comme GRID5000 sont basés sur ce concept de machines réparties. Ce changement du paysage du calcul parallèle haute performance a créé une nouvelle demande d'algorithmes spécifiques pour tirer le meilleur parti des ressources déployées. Pour concevoir ces algorithmes et démontrer leur efficacité, il faut s'appuyer sur des modèles qui tentent de décrire fidèlement le comportement réel des machines tout en restant suffisamment simples à manipuler. Dans cette thèse, nous avons étudié deux modèles parmi les plus importants pour ces nouveaux supports et nous avons fourni des algorithmes polynomiaux optimaux, des algorithmes d'approximations garantis, ou des preuves de NP-complètudes le cas échéant