Scheduling in the Presence of Processor Networks: Complexity and Approximation

International audienceDans 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