View article

We consider an environment with m servers in parallel and n jobs. The n jobs have iid exponentially distributed processing requirements. The servers operate at different speeds and preemptions are allowed. The jobs have random release times that are not known in advance, but whenever a job is released, its due date is fixed and becomes known to the scheduler. We first consider three stochastic scheduling problems with three due date related objective functions and consider variations of the Earliest Due Date (EDD) rule, including the preemptive policy that at any point in time assigns the job with the Earliest Due Date to the Fastest Server (EDD-FS). Our optimality results turn out to be examples of stochastic scheduling problems that have relatively simple priority rules that are optimal while their deterministic counterparts do not allow such simple priority rules to be optimal. We furthermore extend our results to …