Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs : Une preuve alternative

Rodolphe Giroudeau 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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).
Keywords : Non-Approximation
Type de document :
Article dans une revue
Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2008, 27 (5), pp.571-588. 〈10.3166/tsi.27.571-588〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00276718
Contributeur : Rodolphe Giroudeau <>
Soumis le : mercredi 30 avril 2008 - 19:35:49
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

Collections

Citation

Rodolphe Giroudeau. Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs : Une preuve alternative. Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, Lavoisier, 2008, 27 (5), pp.571-588. 〈10.3166/tsi.27.571-588〉. 〈lirmm-00276718〉

Partager

Métriques

Consultations de la notice

82