##
Minimizing expected makespan on uniform processor systems

###
E.G. Coffman, Jr, L. Flatto, M.R. Garey, and R.R. Weber,
*Adv. Appl. Prob.* **19** 117-201, 1987.

Abstract

We study the problem of scheduling $n$ given jobs on $m$ uniform processors to
minimize expected makespan (maximum job finish 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.

**back to list of papers**