In this paper, we investigate a semi-online scheduling problem on two uniform machines with the speed ratio  s . It is assumed that all jobs have their processing times between  p  and  tp    (  p>0     p  >  0       ,   t≥1     t  ≥  1       ). The objective is to minimize the makespan. We give the competitive ratio of  LS    algorithm which is a piecewise function on   t≥1     t  ≥  1        and   s≥1     s  ≥  1       . It shows that  LS  is an optimal algorithm for most regions on  s  and  t   . We further present two optimal algorithms. The algorithm   H 1        H    1          with competitive ratio of  s    is optimal for            1.325  ≤  s  ≤    1  +   5    2         and            s    t  ≤      s    2    −  1    1  +  s  −    s    2           . The algorithm   H 2        H    2          with competitive ratio of  s    is optimal for   1.206≤s≤1.5     1.206  ≤  s  ≤  1.5        and            s  ≤  t  ≤  min  ⁡  {  2  s  −  1  ,      2  (    s    2    −  1  )    1  +  s  −    s    2      }       , and it is also optimal for            1  ≤  s  ≤    1  +   17    4         and            max  ⁡  {  2  s  −  1  ,      −  s  +    9    s    2    +  8  s      2  s    }  ≤  t  ≤   2  s         with competitive ratio of              1  +  t   2        .
['Qian Cao', 'Zhaohui Liu']
Semi-online scheduling with bounded job sizes on two uniform machines