Semi-on-line scheduling with ordinal data on two uniform machines

We investigate the problem of semi-on-line scheduling of jobs on two uniform machines where the order of jobs by their processing times is known as a priori. We propose an algorithm for any machine speed ratio s ⩾ 1. We also present a comprehensive lower bound, which is a piecewise function of s. The algorithm is optimal for the majority of s∈[1,∞). The total length of the intervals of s where the competitive ratio does not match the lower bound is less than 0.7784 and the biggest gap between them never exceeds 0.0521.