@article {IOPORT.06015810,
    author       = {Cai, Sheng-Yi and Yang, Qi-Fan},
    title        = {Online scheduling on three uniform machines.},
    year         = {2012},
    journal      = {Discrete Applied Mathematics},
    volume       = {160},
    number       = {3},
    issn         = {0166-218X},
    pages        = {291-302},
    publisher    = {Elsevier Science B.V. (North-Holland), Amsterdam},
    doi          = {10.1016/j.dam.2011.10.001},
    abstract     = {Summary: This paper investigates the online scheduling on three uniform machines problem. Denote by $s_{j}$ the speed of each machine, $j=1,2,3$. Assume $0<s_{1}\le s_{2}\le s_{3}$, and let $s=s_{2}/s_{1}$ and $t=s_{3}/s_{2}$ be two speed ratios. We show that the greedy algorithm $\mathcal{LS}$ is an optimal online algorithm when the speed ratios $(s,t)\in G_{1}\cup G_{2}$, where $G_{1}=\{(s,t)|\;1\leq t < \frac{1 + \sqrt{31}}{6},\; s\geq \frac{3t}{5+2t-6t^2}\}$ and $G_{2}=\{(s,t)|\; s(t - 1)t\ge 1+s,\; s\ge 1,\; t\ge 1\}$. The competitive ratio of $\mathcal{LS}$ is $\frac{1+s+2st}{s+st}$ when $(s,t)\in G_{1}$ and $\frac{1+s}{st}$ when $(s,t)\in G_{2}$. Moreover, for the general speed ratios, we show the competitive ratio of $\mathcal{LS}$ is no more than $\min\{\frac{1+s+2st}{s+st}, \frac{1+s}{st} +1, \frac{1+s+3st}{1+s+st}\}$ and its overall competitive ratio is 2 which matches the overall lower bound of the problem.},
    identifier   = {06015810},
}