A Stochastic Optimization Algorithm Minimizing Expected Flow Times on Uniform Processors

Consider a set of processors P1, • • •, Pmdiffering only in speed, and a set of jobs with exponentially distributed execution times. The rate parameter for the ith processor is given by, 1 < i < m, where we assume the processors are ordered so that μ1 • • • >μ 2.> μm. The problem is to sequence the jobs nonpreemptively so as to minimize expected total flow time (sum of finishing times). We define a threshold rule that assigns a job to a lowest indexed available processor Pj if and only if the number k of waiting jobs satisfies • • + k > (j — 1).+• My Our main result is a proof that this rule minimizes expected total flow time.