On-line machine covering

Abstract. We consider the problem of scheduling a sequence of jobs to m parallel machines as to maximize the minimum load over the machines. This situation corresponds to a case that a system which consists of the mmachines 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 anm competitive algorithm. In contrast we design an on-line randomized algorithm which is O