Abstract FR:

Dans cette these, nous considerons plusieurs problemes d'ordonnancement pour les calculs paralleles dans un systeme multiprocesseur. Un programme parallele est represente par un graphe, ou les sommets representent les taches et les arcs les precedences et/ou les communications entre les taches. Le probleme est d'affecter les taches aux processeurs et d'ordonnancer leur execution, tout en respectant les contraintes de precedence, dans le but de minimiser la duree d'ordonnancement. Un premier sous-probleme considere est le probleme d'ordonnancement avec contrainte de ressources, i. E. Le cas ou le systeme multiprocesseur a un seul bus de communication et a tout moment il y a au plus un message sur le bus. Dans ce cas on demontre que le probleme est np-difficile au sens fort. Le deuxieme sous-probleme traite est l'ordonnancement d'une seule machine sous contraintes de precedence avec retard. Si les temps d'execution de taches sont unitaires et les durees de retards sont entieres, on prouve que le probleme est np-difficile au sens fort. Cependant, si les temps d'execution de taches sont entiers et les durees de retards sont unitaires, le probleme est polynomial, et un algorithme quadratique est presente. Les cas d'executions preemptives et non-preemptives sont tous les deux consideres. En suite, l'ordonnancement de graphes de taches uet-uct sur deux processeurs est analyse. Un algorithme optimal quadratique est propose pour une classe de graphes serie-paralleles. En fin, l'ordonnancement stochastique d'un graphe de taches sur deux processeurs identiques est le quatrieme sous-probleme considere. Nous prouvons qu'une politique optimale preemptive minimise stochastiquement la longueur de l'ordonnancement, pourvu que le graphe de precedence appartient a la classe de graphes de type foret coupee