Abstract FR:

Cette these porte sur le probleme de l'ordonnancement de taches sur les architectures multiprocesseurs a memoire distribuee. Nous avons ajoute des durees de communication aux graphes de dependance classiques. A partir de la methode c. P. M. Et de plusieurs concepts nouveaux (duplication de taches en plusieurs copies, architecture distribuee virtuelle vds. . . ) nous avons obtenu les resultats suivants: si les temps de calculs des taches sont superieures ou egaux aux temps de communication, nous presentons un algorithme polynomial qui determine l'ordonnancement au plus tot des copies des taches sur l'architecture vds; dans le cas contraire, le probleme d'ordonnancement devient np-difficile. Nous proposons une heuristique efficace pour trouver une solution approchee; lorsque les canaux de communication ont une capacite limitee, le probleme se complique. Si chaque tache ne calcule qu'un unique resultat et si les temps de calculs des taches sont superieurs ou egaux aux temps de communication, l'algorithme polynomial vu plus haut donne une solution au plus tot dont les messages ne saturent pas les canaux de communication