Optimal time-critical scheduling via resource augmentation

We consider two fundamental problems in dynamic scheduling: scheduling to m eet deadlines in a preemptive multiprocessor setting, and scheduling to pro vide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line a lgorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP. We study these problems using a relaxed notion of competitive analysis, int roduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is all owed more resources than the optimal off-line algorithm to which it is comp ared, Using this approach, we establish that several well-known on-line alg orithms, that have poor performance from an absolute worst-case perspective , are optimal for the problems in question when allowed moderately more res ources. For optimization of average flow time, these are the first results of any sort, for any NP-hard version of the problem, that indicate that it might be possible to design good approximation algorithms.