An approximation algorithm for scheduling unitary tasks on m processors with communication delays

A.Munier, C.Hanen

IBP-Litp 1995/12: Rapport de Recherche Litp / Litp research reports
19 pages - Février/February 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: An approximation algorithm for scheduling unitary tasks on m processors with communication delays

Résumé : Ce papier est consacré à l'étude d'un nouvel algorithme approché pour un problème d'ordonnancement à temps de communication.
La durée des tâches et les temps de communication entre les différents processeurs sont unitaires, et l'on dispose d'un nombre limité m de processeurs. Dans une première phase, on calcule une solution pour le problème avec un nombre illimité de processeurs. Puis, on l'utilise pour résoudre les conflits dans le cas où le nombre de processeurs est limité.
On montre que la performance relative de cet algorithme est inférieure à 1+r-r/m où r désigne la performance relative de l'ordonnancement obtenu pour un nombre illimité de processeurs. On développe alors un algorithme polynomial de performance relative r=4/3 pour la première phase. L'algorithme obtenu pour le problème à m processeurs a donc une performance relative de 7/3-4/3m et nous montrons que cette performance est atteinte.

Abstract : This paper defines and studies a new list scheduling approximation algorithm for scheduling unitary tasks with unitary communication delays on m processors. In a first step, an approximated solution of the problem instance with an unlimited number of processors is generated. Then this solution is used to solve the resource conflicts during the list scheduling phase on m processors.
We prove that the relative performance of this algorithm can be bounded by 1+r-r/m, where r denotes the worst case performance of the solution generated in the first step. Then, we provide a polynomial algorithm with performance r=4/3 for the first step that leads to an overall worst case performance of 7/3-4/3m and we show that this bound is tight.

Publications internes Litp 1995 / Litp research reports 1995