Sensitivity analysis of tree scheduling on two machines with communication delays

✍ Scribed by Frédéric Guinand; Aziz Moukrim; Eric Sanlaville

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 282 KB
• Volume: 30
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(03)00091-7

✦ Synopsis

This paper presents a sensitivity analysis for the problem of scheduling trees with communication delays on two identical processors, to minimize the makespan. Tasks are supposed to have unit execution time (UET UET), and the values associated to communication delays are supposed unknown before the execution.

The paper compares the optimal makespans with and without communication delays. The results are used to obtain sensitivity bounds for algorithms providing optimal schedules for graphs with unit execution and communication times (UECT UECT). The notion of processor-ordered schedules, for two-processor systems, is introduced. It describes schedules in which all communications are oriented from one processor to the other. It is shown that these schedules are dominant for unit delays, for zero delays, but not for delays of less than or equal to one. We establish that algorithms building optimal processor-ordered schedules for UECT UECT graphs admit an absolute sensitivity bound equal to the difference between the maximum and the minimum actual communication delays: x À x à 6 c c À c. This bound is tight.