A.Munier, C.Hanen
Using duplication for scheduling unitary tasks on m processors with communication delays

 Ce papier est consacré à l'étude d'un nouvel algorithme de liste
pour un problème d'ordonnancement à temps de communication  et  à
resources  limitées. Cet algorithme fait appel à une procédure de
duplication des tâches utilisée de manière gloutonne.  On  montre
que,  pour  toute  liste de priorité, sa performance relative est
bornée par 2-1/m, où m représente le nombre de machines,  et  que
cette borne est atteinte.
 This  paper introduces a new list scheduling algorithm that uses
greedy duplication to solve a scheduling problem with  communica­
tion delays and resource limitations. We prove that, for any pri­
ority list, its worst case relative  performance  is  bounded  by
2-1/m and that this bound is tight.