On-line machine covering

✍ Scribed by Yossi Azar; Leah Epstein

• Publisher: Springer US
• Year: 1998
• Tongue: English
• Weight: 130 KB
• Volume: 1
• Category: Article
• ISSN: 1094-6136
• DOI: 10.1002/(sici)1099-1425(199808)1:2<67::aid-jos6>3.0.co;2-y

✦ Synopsis

We consider the problem of scheduling a sequence of jobs on m parallel identical machines so as to maximize the minimum load over the machines. This situation corresponds to a case that a system which consists of the m machines is alive (i.e. productive) only when all the machines are alive, and the system should be maintained alive as long as possible. It is well known that any on-line deterministic algorithm for identical machines has a competitive ratio of at least m and that greedy is an m competitive algorithm. In contrast we design an on-line randomized algorithm which is O((m log m) competitive and a lower bound of ((m) for any on-line randomized algorithm. In the case where the weights of the jobs are polynomially related we design an optimal O (log m) competitive randomized algorithm and a matching tight lower bound for any on-line randomized algorithm. In fact, if F is the ratio between the weights of largest job and the smallest job then our randomized algorithm is O(log F) competitive.

A sub-problem that we solve which is interesting in its own right is the problem where the value of the optimal algorithm is known in advance. Here we show a deterministic (constant) 2!(1/m) competitive algorithm. We also show that our algorithm is optimal for two, three and four machines and that no on-line deterministic algorithm can achieve a better competitive ratio than 1)75 for m*4 machines.