Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-size Tasks to Related Machines

subject of intensive research for the last decade. The problem is intriguing in the sense that the natural extensions of the greedy oblivious schedulers, which have near-optimal performance in the case of identical machines, do not work so well in the case of the related machines.

In this work we present a rather surprising lower bound stating that any oblivious scheduler that assigns an arbitrary number of tasks to n related machines would need at least $\Theta\left(\frac{\logn}{\loglogn}\right)$ polls of machine loads per task, in order to have a constant competitive ratio versus the optimum offline assignment of these tasks. On the other hand, we prove that the missing information for an oblivious scheduler to perform almost optimally, is the amount of tasks to be inserted into the system. In particular, we provide an oblivious scheduler that only uses O(\loglogn) polls and the additional information of
the size of the input sequence, in order to achieve a constant competitive ratio. The philosophy of this scheduler is based on an interesting exploitation of the SLOWFIT concept ([AAFPW97,BFN00,BCK97]; for a survey see
[BY98,Azar98,Sgall98]) for the assignment of the tasks to the related machines despite the restrictions on the provided online information, in combination with a layered induction argument for bounding the tails of the number of tasks passing from slower to faster machines. We finally use this oblivious scheduler as the core of an adaptive scheduler that does not demand the knowledge of the input sequence and yet achieves almost the same performance.