Abstract
This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a single-processor system. It has been known for long that in such a setting, no on-line algorithm is optimal (or 1-competitive) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be Ω(k)-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to O(1) if the on-line scheduler is equipped with a processor O(1) times faster [8]; furthermore, optimality can be achieved when using a processor O(log k) times faster [12]. This paper presents a new on-line algorithm for scheduling jobs with tight deadlines, which can achieve optimality when using a processor that is only O(1) times faster.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, and F. Wang. On the competitiveness of on-line task real-time task scheduling. Journal of Real-Time Systems, 4(2):124–144, 1992.
S. Baruah, G. Koren, B. Mishra, A. Raghunathan, L. Rosier, and D. Shasha. On-line scheduling in the presence of overload. In Proceedings of the IEEE Thirtysecond Annual Symposium on the Foundations of Computer Science, pages 101–110, San Juan, Porto Rico, October 1991.
P. Berman and C. Coulston. Speed is more powerful than clairvoyance. In Proceedings of the Sixth Scandinavian Workshop on Algorithm Theory, pages 255–263, July 1998.
Bhaskar DasGupta and Michael A. Palis. Online real-time preemptive scheduling of jobs with deadlines. In Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 1913 of Lecture Notes in Computer Science, pages 96–107. Springer, September 2000.
Michael L. Dertouzos and Aloysius Ka-Lau Mok. Multiprocessor on-line scheduling of hard-real-time tasks. IEEE Transactions on Software Engineering, 15(12):1497–1506, December 1989.
Jeff Edmonds. Scheduling in the dark. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 179–188, 1999.
Bala Kalyanasundaram and Kirk Pruhs. Maximizing job completions online. In Proceedings of the Sixth European Symposium on Algorithms, pages 235–246, 1998.
Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47(4):617–643, July 2000.
Gilad Koren and Dennis Shasha. Dover: An optimal on-line scheduling algorithm for overloaded real-time systems. SIAM Journal of Computing, 24(2):318–339, April 1995.
Tak-Wah Lam, Tsuen-Wan Ngan, and Kar-Keung To. On the speed requirement for optimal deadline scheduling in overloaded systems. In Proceedings of the Fifteenth International Parallel and Distributed Processing Symposium, page 202, 2001.
Tak-Wah Lam and Kar-Keung To. Trade-offs between speed and processor in hard-deadline scheduling. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 623–632, 1999.
Tak-Wah Lam and Kar-Keung To. Performance guarantee for online deadline scheduling in the presence of overload. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 755–764, 2001.
Cynthia A. Phillips, Cliff Stein, Eric Torng, and Joel Wein. Optimal time-critical scheduling via resource augmentation. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 140–149, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koo, CY., Lam, TW., Ngan, TW., To, KK. (2001). On-Line Scheduling with Tight Deadlines. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_41
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive