Résumé
Nous étudions un problème d’ordonnancement dans un système multiprocesseur en présence de communications hiérarchiques. Nous nous intéressons au problème où toutes les tâches du graphe de précédence ont une durée unitaire et où le système multiprocesseurs est constitué d’un nombre non borné de modules avec deux processeurs identiques chacun. Le délai de communication pour transférer les données entre une tâche prédécesseur i et une tâche successeur j exécutée sur des modules différents s’effectue en deux unités de temps, tandis que le coût de transfert est égal à une unité de temps quand les tâches sont ordonnancées sur des processeurs différents à l’intérieur d’un même module. Dans ce cadre, nous allons montrer qu’il n’existe pas d’algorithme avec une garantie de performance inférieure à 6/5 (resp. 9/8) pour le cas de la minimisation de la longueur de l’ordonnancement (resp. de la somme des temps de complétude). De plus, nous proposons un algorithme polynomial dans le cas où la longueur de l’ordonnancement est de trois.
We study the problem of minimizing the makespan for the multiprocessor scheduling problem in the presence of a hierarchical communications. We consider the problem in which all the tasks, in the precedence graph admit an unit execution time and the multiprocessor machines is constitued by an unrestricted number of machines with two identical processors each. The communication delays betweeen two adjacency tasks i and j which are executed on two differents clusters is equal to two units of time, whereas if and are scheduled on two differents processors on the same cluster is equal to one unit of time. In such a context, we prove that there is no heuristic with performance guarantee smaller than 6/5 (resp. 9/8) for the minimization of the length of the schedule (resp. the sum of the completion time). Moreover, we develop a polynomial time algorithm in the case where the length of the schedule is three.