Abstract FR:

Le sujet de cette these est l'etude de problemes d'optimisation combinatoire issus de la conception et de l'utilisation d'ordinateurs multiprocesseurs. Nous etudions deux classes importantes de problemes: les ordonnancements avec delais de communication et le placement de taches. Notre etude des ordonnancements avec communications comporte deux parties. Dans la premiere, consacree aux problemes sans limitation du nombre de processeurs, nous montrons la np-completude du probleme consistant a ordonnancer un graphe de taches unitaires avec des delais de communication unitaires (probleme uet-uct). Nous degageons certains sous-problemes polynomiaux et fournissons un algorithme polynomial approche avec garantie de performance. Sous des hypotheses plus generales nous etudions les problemes ayant un arbre pour graphe de precedence. Nous etablissons un resultat de complexite dans le cas de temps de communication constant et concevons un algorithme approche pour les arborescences. La seconde partie traite du probleme uet-uct avec un nombre limite de processeurs. Nous montrons la np-completude du probleme consistant a trouver un ordonnancement de duree inferieure a 4 et montrons l'existence de nombreuses classes de sous-problemes polynomiaux. Nous nous interessons, dans la derniere partie de cette these, a des problemes de placement consistant en la recherche de cycles hamiltoniens dans les graphes reguliers. Nous generalisons le resultat de np-completude obtenu pour les graphes 3-reguliers, aux graphes reguliers de degre superieur a 3 et aux graphes reguliers planaires de degre 4 et 5