Abstract FR:

Dans cette these, nous etudions plusieurs formulations des problemes d'ordonnancement deterministe statique dans les systemes paralleles et distribues. Nous considerons deux axes principaux de travail. Le premier axe est la determination du niveau d'approximabilite des problemes d'ordonnancement de taches independantes. Dans la premiere partie de la these, nous developpons des schemas d'approximation polynomiaux pour des problemes d'ordonnancemment de taches independantes dans les systemes paralleles. Nous proposons une methode generale de construction des schemas d'approximation qui est appliquee pour l'ordonnancement sur des processeurs homogenes, uniformes, heterogenes et pour l'ordonnancement sur l'hypercube. Nous presentons des algorithmes de complexite reduite par rapport aux schemas d'approximation existants dans la litterature pour les problemes consideres. Le deuxieme axe est l'etude de la structure des solutions des problemes d'allocation de taches communicantes dans les systemes distribues. Nous developpons des heuristiques pour le probleme du placement de taches afin de minimiser le temps total d'execution et de communication et pour le probleme d'allocation de taches afin de minimiser le temps de completude. Les experiences effectuees avec des instances aleatoires montrent l'efficacite des methodes proposees et la tendance vers l'utilisation d'un nombre limite de processeurs disponibles. Nous explorons egalement la relation entre les deux problemes par une etude theorique de la structure des solutions optimales.