ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 24/1 - 2005  - pp.95-114  - doi:10.3166/tsi.24.95-114
TITRE
Seuil d'approximation pour un problème d'ordonnancement en présence de communications hiérarchiques

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.

ABSTRACT
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 i and j 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.


AUTEUR(S)
Rodolphe GIROUDEAU

MOTS-CLÉS
ordonnancement, communications hiérarchiques, non-approximabilité.

KEYWORDS
scheduling, hierarchical communications, non-approximability.

CITATIONS
tsi.revuesonline.com/revues/11/citation/5975.html

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (174 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier