Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines

In this paper, we consider the semi-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s .. [1,.), and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s > (s 2 + 3s + 1 / (s 2 + 2s + 1). The competitive ratio of the algorithms is (s 2 + 3s + 1) / (s 2 + 2s + 1), which matches the randomized lower bound for every s . 1. Hence randomization does not help for the discussed preemptive scheduling problem.