Semi-online Multiprocessor Scheduling with Known Largest Job Processing Time
摘要
We study a semi-online variant of the online multiprocessor scheduling problem, in which the largest job processing time is known. We show affirmatively that such a known value can be explored to design better online algorithms, for a large number of machines in particular. Specifically, we design the first 1.8686-competitive algorithm for the semi-online variant, compared against the long-standing competitive ratio of 1.9201 for the classic online problem. When there are only three machines, we present a 1.4655-competitive algorithm, improving the previous best known ratio of 1.5. Our algorithm design deviates from the well-known list scheduling that always assigns the current job to a least loaded machine, by incorporating a novel idea to assign the current job to a maximum loaded “safe” machine, where “safe” is defined using the largest job processing time.