Printed in N. Ireland? Applied Probability Trust 1987 MINIMIZING EXPECTED MAKESPANS ON UNIFORM PROCESSOR SYSTEMS

We study the problem of scheduling n given jobs on m uniform processors to minimize expected makespan (maximum finishing time). Job execution times are not known in advance, but are known to be exponentially distributed, with identical rate parameters depending solely on the executing processor. For m = 2 and 3, we show that there exist optimal scheduling rules of a certain threshold type, and we show how the required thresholds can be easily determined. We conjecture that similar threshold rules suffice for m> 3 but are unable to prove this. However, for m> 3 we do obtain a general bound on problem size that permits Bellman equations to be used to construct an optimal scheduling rule for any given set of m rate parameters, with the memory required to represent that scheduling rule being independent of the number of remaining jobs. STOCHASTIC S HEDULING; STOCHASTIC OPTIMIZATION ALGORITHMS 1