On the optimality of list scheduling for online uniform machines scheduling

摘要

This paper considers classical online scheduling problems on uniform machines. We show the tight competitive ratio of LS for any combinations of speeds of three machines. We prove that LS is optimal when s _3 ≥ s _2 ≥ s _1=1 and s _3 ~2≥ s _2 ~2 s _2, s _3 are the speeds of three machines. On the other hand, LS can not be optimal for all combinations of machine speeds, even restricted to the case of 1 = s _1=s _2 < s _3. For m ≥ 4 machines, LS remains optimal when one machine has very large speed, and the remaining machines have the same speed.