Nonmigratory online deadline scheduling on multiprocessors

Abstract. In this paper we consider multiprocessor scheduling with hard deadlines and inves-tigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a nonmigratory online schedule using m speed-5.828 processors (i.e., processors 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors [B. Kalyanasundaram and K. R. Pruhs, J. Algorithms, 38 (2001), pp. 2–24] or a migratory online schedule using m speed-2 processors [C. A. Phillips et al., Algorithmica, 32 (2002), pp. 163–200]. Our result is based on a simple conservative scheduling algorithm called PARK, which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online nonmigratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm