Using duplication for scheduling unitary tasks on m processors with communication delays

A.Munier, C.Hanen

IBP-Litp 1995/47: Rapport de Recherche Litp / Litp research reports
14 pages - Octobre/October 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Using duplication for scheduling unitary tasks on m processors with communication delays

Résumé : 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.

Abstract : This paper introduces a new list scheduling algorithm that uses greedy duplication to solve a scheduling problem with communication delays and resource limitations. We prove that, for any priority list, its worst case relative performance is bounded by 2-1/m and that this bound is tight.

Publications internes Litp 1995 / Litp research reports 1995