*Result*: 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 ² + 3 s + 1 / ( s ² + 2 s + 1). The competitive ratio of the algorithms is ( s ² + 3 s + 1) / ( s ² + 2 s + 1), which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem. [ABSTRACT FROM AUTHOR]

Copyright of Acta Mathematica Sinica is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*