On scheduling tasks with exponential service times and in-tree precedence constraints (Q1060842)

In this paper we extend the work of Chandy and Reynolds in which they considered the problem of scheduling tasks on two identical processors. The processing times of the tasks are independent, identically distributed exponential random variables. The tasks are subject to in- tree precedence constraints. Chandy and Reynolds have shown that the expected value of the makespan is minimized if and only if the scheduling policy is Highest-Level-First (HLF). We extend their result by showing that a policy maximizes the probability that all tasks finish by some time \(t\geq 0\) if and only if the policy is HLF. Additionally, we show that a policy maximizes the probability that the sum of the finishing times of all the tasks is less than some value \(s\geq 0\) if and only if the policy is HLF.