The Stochastic Optimality of Sept in Parallel Machine Scheduling

Abstract

We consider preemptive scheduling on parallel machines where processing times of jobs are i.i.d. but jobs may already have received distinct amounts of service. We show that when processing times are increasing in likelihood ratio, SEPT (shortest expected [remaining] processing time first) stochastically minimizes any increasing and Schur-concave function of the job completion times. The same result holds when processing times are exponential with possibly different means. © 1994, Cambridge University Press. All rights reserved.