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

✍ Scribed by C. Hanen; A. Munier

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 1023 KB
• Volume: 81
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00077-2

✦ Synopsis

This paper studies the relative performance of the Coffman-Graham algorithm for scheduling unitary tasks on VI processors with unitary communication delays.

Using a particular decomposition of CC-schedules, we prove that its worst case relative pcrformance is bounded by $ for m = 2 and that this bound is tight. For VI> 3, we provide an instance of the problem for which the performance ratio is 3 -[6,!(m + I )].