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