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 27/5 - 2008  - pp.571-588  - doi:10.3166/tsi.27.571-588
TITRE
Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs. Une preuve alternative

RÉSUMÉ
Nous proposons une nouvelle approche pour la démonstration de la NP-complétude pour l'un des problèmes central de l'ordonnancement avec délais de communication. 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 multiprocesseur est constitué d'un nombre non borné de processeurs. 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 processeurs différents dure une unité de temps (modèle UET-UCT). Dans ce cadre, nous allons redémontrer qu'il n'existe pas d'algorithme avec une garantie de performance inférieure à 7/6 (resp. 9/8) pour le cas de la minimisation de la longueur de l'ordonnancement (resp. de la somme des temps de complétude).


ABSTRACT
We propose a new approach for the proof of classical scheduling problem with communication delay. We study the problem of minimizing the makespan for the multiprocessor scheduling problem in the presence of a communication delay. We consider the problem in which all the tasks, in the precedence graph admit an unit execution time and the multiprocessor system is constituted by an unrestricted number of processors. The communication delays between two adjacency tasks i and j which are executed on two different processors is equal to one unit of time (UET-UCT model). In such a context, we prove that there is no heuristic with performance guarantee smaller than 7/6 (resp. 9/8) for the minimization of the length of the schedule (resp. the sum of the completion time).


AUTEUR(S)
Rodolphe GIROUDEAU

Reçu le 15 septembre 2006.    Accepté le 31 mai 2007.

MOTS-CLÉS
ordonnancement, délais de communication, non-approximabilité.

KEYWORDS
scheduling, communication delays, non-approximability.

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  (234 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier