Scheduling in the presence of processor networks : complexity and approximation

¹ LIRMM, 161 rue Ada, 34392 Montpellier Cedex 5, UMR 5055, France
boudet@lirmm.fr; rgirou@lirmm.fr; konig@lirmm.fr
² LORIA, 54506 Vandoeuvre-lès-Nancy Cedex, France
Johanne.Cohen@loria.fr

Received: 25 June 2009
Accepted: 27 March 2012

Abstract

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks i and j depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless 𝒫 = 𝒩𝒫) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.

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 𝒩𝒫-complet quand la longueur de l’ordonnancement est au plus trois) existe, voir [C. Lahlou, Ordonnancement dans les réseaux de processeurs : complexité et approximation. Ph.D. thesis, Université Paris VI (1998)]. pour ces deux résultats. Nous démontrons qu’il n’existe pas d’algorithme polynomial ρ-approché avec ρ < 4/3 sous l’hypothèse que 𝒫 ≠ 𝒩𝒫 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.