AbstractWe consider the problem of preemptive non-clairvoyant scheduling on a single machine. In this model a scheduler receives a number of jobs at different times without prior knowledge of the future jobs or the required processing time of jobs that are not yet completed. We want to minimize the total response time, i.e. the sum of times each job takes from its release to completion. One particular algorithm, Balance, always schedules the job that is least processed so far. A comparison of an on-line scheduler running Balance against the optimal off-line shows a very large competitive ratio if both algorithms use machines of the same speed. However, it has been shown that if Balance is run on a v times faster machine than its clairvoyant competitor, then the competitive ratio drops to v/(v-1) at most. This result showed that speed can be almost as good as clairvoyance. We show for v >= 2 the competitive ratio of Balance is 2/v. In other words, sufficiently high speed is more powerful than clairvoyance.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]
Additional Key Words and Phrases: scheduling, on-line algorithms, resource augmentation
Selected references
- Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. In 36th Annual Symposium on Foundations of Computer Science, pages 214-221, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Rajeev Motwani, Steven Phillips, and Eric Torng. Non-clairvoyant scheduling. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 422-431, Austin, Texas, 25-27 January 1993.
- Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 140-149, El Paso, Texas, 4-6 May 1997.