Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines

Abstract

In stochastic online scheduling problems, a common class of policies is the class of fixed assignment policies. These policies first assign jobs to machines and then apply single machine scheduling policies for each machine separately. We consider a stochastic online scheduling problem for which the goal is to minimize total weighted expected completion time on uniform parallel machines. To solve the problem, we adapt policies introduced for the identical and unrelated parallel machine environments. We show that, with the help of lower bounds specific for the uniform machine environment, we can tighten the performance guarantees that are implied by the results for the unrelated machine environment for the special case of two machine speeds. Furthermore, in the Online-List model we show that a greedy assignment policy is asymptotically optimal. Finally, we construct a computational study to assess the performance of the policies in practice.