Scheduling in the Presence of Processor Networks: Complexity and Approximation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles RAIRO - Operations Research Year : 2012

Scheduling in the Presence of Processor Networks: Complexity and Approximation

Abstract

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.

Dates and versions

lirmm-00697219 , version 1 (14-05-2012)

Identifiers

Cite

Rodolphe Giroudeau, Jean-Claude König, Vincent Boudet, Joanne Cohen. Scheduling in the Presence of Processor Networks: Complexity and Approximation. RAIRO - Operations Research, 2012, 46, pp.1-22. ⟨10.1051/ro/2012005⟩. ⟨lirmm-00697219⟩
201 View
2 Download

Altmetric

Share

More