Optimal Scheduling of Exponential Tasks with In-Tree Precedence Constraints on Two Parallel Processors Subject to Failure and Repair

In this paper, we consider the problem of scheduling n tasks on two processors. The processing times of the n tasks are i.i.d. exponential random variables. The precedence constraints among the n tasks form an in-tree. The two processors are subject to failure and repair in a completely arbitrary manner, but are independent of the task processing times. We introduce the concept of stochastic partial ordering on random in-trees and show that among all policies, the highest level first (HLF) policy produces the smallest in-tree of unfinished tasks under the stochastic partial ordering. This implies that the HLF policy stochastically minimizes the makespan even when the two processors are subject to failures and repairs. As a special case, we also show that the HLF policy minimizes the dynamic failure probability when the processors are subject to failure, but no repairs can be done.