OPTIMAL ONLINE ALGORITHMS ON TWO HIERARCHICAL MACHINES WITH RESOURCE AUGMENTATION

摘要

This paper investigates an online hierarchical scheduling problem with resource augmentation, i.e., the resources of the online algorithms are different from those of the offline algorithms. The machines are provided with different capacity according to their hierarchies. One with the hierarchy 1 has a speed of s (q) in the online (offline) algorithms and can process all the jobs. The other with hierarchy 2 has a speed of 1 in the online/offline algorithms and can only process partial jobs. The objective is to minimize makespan. For any 0 < q, s < ∞, we present optimal online algorithms with parametric competitive ratios.