Scheduling in the dark

We considered non-clairvoyant multiprocessor scheduling of jobs with arbitrary arrival times and changing execution characteristics. The problem has been studied extensively when either the jobs all arrive at time zero, or when all the jobs are fully parallelizable, or when the scheduler has considerable knowledge about the jobs. This paper considers for the first time this problem without any of these three restrictions although our algorithm is given more resources than the adversary. We provide new upper acid lower bound techniques applicable in this more difficult scenario. The results an of both theoretical and practical interest. In our model, a job can arrive at any arbitrary time and its execution characteristics can change through the life of the job from being anywhere from fully parallelizable to completely sequential. We assume that the scheduler has no knowledge about the jobs except for knowing when a job arrives and when it completes. (This is why we say that the scheduler is completely in the dark.) Given all this, we prove that the scheduler algorithm Equi-partition, though simple, performs within a constant factor as well as the optimal scheduler as long as it is given at least twice as many processors. Moreover, we prove that if none of the jobs are "strictly" fully parallelizable, then Equi-partition performs competitively with no extra processors. We also consider other variations: faster processors; fewer preemptions; and a wider range of execution characteristics. (C) 2000 Elsevier Science B.V. All rights reserved.