Performance of Coffman-Graham schedules in presence of unit communication delays

C. Hanen, A. Munier

IBP-Litp 1994/57: Rapport de Recherche Litp / Litp research reports
28 pages - Octobre/October 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Performance of Coffman-Graham schedules in presence of unit communication delays

Résumé : Cet article est une etude de la performance relative de l'algorithme de Coffman-Graham pour ordonnancer un système de tâches de durées unitaires sur m machines avec des délais de communication unitaires. Nous montrons que cette performance est bornée supérieurement par min(3-3/m, 2m/3+e). grâce à la décomposition de l'ordonnancement.
Pour deux machines, nous montrons que cette borne est atteinte. Lorsque m„3, nous présentons un exemple pour lequel la performance de l'algorithme dans le pire des cas est
3 -6 /(m+1).

Abstract : This paper studies the relative performance of the Coffman-Graham algorithm for scheduling unitary tasks on m processors with unitary communication delays. Using a particular decomposition of CG-schedules, we prove that its worst case relative performance is bounded by min(3-3/m, 2m/3+e).
For m=2, we show that this bound is tight. For m„3, we provide an instance of the problem for which the performance ratio is 3 -6 /(m+1).

Publications internes Litp 1994 / Litp research reports 1994