On the optimality of static priority policies in stochastic scheduling on parallel machines

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g ( U ) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of w i while job i is incomplete, the sufficient condition is simply w 1 ≧ … ≧ w n and λ 1 w 1 ≧ … ≧ λ n w n .