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.

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