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