##
Scheduling jobs with stochastic processing requirements on parallel
machines to minimize makespan or flowtime

###
R.R. Weber,
*J. Appl. Prob.* 19, 167-182, 1982.

Abstract

A number of identical machine operating in parallel are to be used to complete
the processing of a collection of jobs so as to minimize the jobs' makespan or
flowtime. The total processing time required to complete each job has the same
probability distribution, but some jobs have received differing amounts of
processing prior to the start. When the distribution has a monotone hazard rate
the expected value of the makespan (flowtime) is minimized by a strategy which
always processes those jobs with the least (greatest) hazard rates. When the
distribution has a density whose logarithm is concave or convex these strategies
minimize the makespan and flowtime in distribution. These results are also
true when the processing requirements are distributed as exponential random
variables with different parameters.

**back to list of papers**