Stochastic Scheduling with Variable Profile and Precedence Constraints

摘要

The stochastic profile scheduling problem of a partially ordered set of tasks onuniform processors is considered. The set of available processors varies in time. The running times of the tasks are independent random variables with exponential distributions. Simple optimal preemptive policies which stochastically minimize the makespan when the partial order is an interval order, or an in-forest, or an out-forest, are obtained.