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