On‐line machine covering

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. © 1998 John Wiley & Sons, Ltd.