Scheduling with unexpected machine breakdowns

We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to mini mize the makespan. The job processing times are known in advance and preemp tion of jobs is allowed. Machines an non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advanc e. New machines may be added as well. Thus machine availabilities change on line. We first show that no online algorithm can construct optimal schedule s. We also show that no online algorithm can achieve a bounded competitive ratio if there may be time intervals where no machine is available, Then we present an online algorithm that constructs schedules with an optimal make span of C-max(OPT) if a lookahead of one is given, i.e., the algorithm alwa ys knows the next point in time when the set of available machines changes. Finally, we give an online algorithm without lookahead that constructs sch edules with a nearly optimal makespan of C-max(OPT) + epsilon, for any epsi lon > 0, if at any time at least one machine is available. Our results demo nstrate that not knowing machine availabilities in advance is of little har m. (C) 2001 Elsevier Science B.V. All rights reserved.