Sensitivity analysis of tree scheduling on two machines with communication delays
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), 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). 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 graphs admit an absolute sensitivity bound equal to the difference between the maximum and the minimum actual communication delays: . This bound is tight.
sensitivity analysis trees unit execution and communication times uncertain communication delays two-processor scheduling