On-line and semi-on-line scheduling on uniform machines with non-simultaneous machine available times

This paper investigates on-line and semi-on-line scheduling problems on uniform machines with non-simultaneous machine available times. In on-line version, it is proved that the worst case performance ratio of LS algorithm is ≥ (1 + √(5))/2, (m = 2); ≥ 1 + √((2m − 2))/2,(m = 3), furthermore, LS algorithm is the best possible approximation algorithm when m = 2 and the bound is tight when m = 2,3,…,6. For the case that s1 = s2 = … = sm − 1,sm = 1 it is proved that the worst case performance ratio of LS algorithm is ≥ (1 + √(5))/2,(m = 2); ≥ 3 − 4/(m + 1), (m = 3), and the bound is tight. For the semi on-line scheduling where the jobs are ordered in decreasing times, it is proved that the worst case performance ratio of LS algorithm is 2 − 2/(m + 1).