On the optimality of list scheduling for online uniform machines scheduling |
| |
Authors: | Fangqiu Han Zhiyi Tan Yang Yang |
| |
Institution: | 1. Department of Mathematics, State Key Laboratory of CAD and CG, Zhejiang University, Hangzhou, 310027, People’s Republic of China
|
| |
Abstract: | 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\geq s_2^2+s_2s_3+s_2}$ , where s 1, 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|