Online scheduling for jobs with arbitrary release times on uniform machines

In this paper, we study the problem of online scheduling on uniform machines, in which the jobs have arbitrary release times and the objective function is to minimize the maximum completion time. The speeds of the machines are 1 for the first $m-1$ machines, but the last one's is $s$ $(s>1)$. The performance of the LS (list scheduling) algorithm is analyzed. When the numbers of machines are $m=2$ and $m\ge~3$, it is presented that the competitive ratios of the LS algorithm are $\frac{3+\sqrt{5}}{2}$ and $4-\frac{4}{m+1}$, respectively. In general, a better algorithm called MLS (modified list scheduling) is also designed for the problem and it is shown that the competitive ratio of the MLS is no more than 3.8626.