On the optimality of list scheduling for online uniform machines scheduling

Autor: Fangqiu Han, Zhiyi Tan, Yang Yang
Rok vydání: 2011
Předmět:
Zdroj: Optimization Letters. 6:1551-1571
ISSN: 1862-4480
1862-4472
DOI: 10.1007/s11590-011-0335-x
Popis: 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 s3 ≥ s2 ≥ s1 = 1 and \({s_3^2\geq s_2^2+s_2s_3+s_2}\), where s1, s2, s3 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 = s1 = s2 < s3. For m ≥ 4 machines, LS remains optimal when one machine has very large speed, and the remaining machines have the same speed.
Databáze: OpenAIRE
Externí odkaz: