Scheduling in the Presence of Processor Networks: Complexity and Approximation

Résumé : Dans cet article, nous étudions le problème de la minimisation de la longueur de l'ordonnancement pour un système multi-processeur en présence de délais de communication. Le délai de communication entre deux tâches $i$ et $j$ dépend de la distance entre les processeurs exécutant ces deux tâches. Un algorithme simple, de complexité polynomiale quand la longueur de l'ordonnancement est au plus deux (le problème devient $\mathcal{NP}$-complet quand la longueur de l'ordonnancement est au plus trois) existe, voir \cite{lahlouthesis} pour ces deux résultats. Nous démontrons qu'il n'existe pas d'algorithme polynomial $\rho$-approché avec $\rho < 4/3$ sous l'hypothèse que ${\cal{P}} \neq {\cal{NP}}$ pour la minimisation de la longueur de l'ordonnancement dans le cas où le réseau de processeurs admet pour topologie une chaîne ou un anneau et le graphe de précédence est un graphe biparti de profondeur un. Nous avons également développé deux algorithmes d'approximation avec des garanties de performance constantes pour les versions limitées et non limitées sur le nombre de processeurs.
Mots-clés : Complexité approximation
Type de document :
Article dans une revue
RAIRO - Operations Research, EDP Sciences, 2012, 46, pp.1-22. 〈10.1051/ro/2012005〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00697219
Contributeur : Rodolphe Giroudeau <>
Soumis le : lundi 14 mai 2012 - 20:59:24
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Rodolphe Giroudeau, Jean-Claude König, Vincent Boudet, Joanne Cohen. Scheduling in the Presence of Processor Networks: Complexity and Approximation. RAIRO - Operations Research, EDP Sciences, 2012, 46, pp.1-22. 〈10.1051/ro/2012005〉. 〈lirmm-00697219〉

Partager

Métriques

Consultations de la notice

277