{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:32Z","timestamp":1725490232306},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_41","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"464-473","source":"Crossref","is-referenced-by-count":1,"title":["On-Line Scheduling with Tight Deadlines"],"prefix":"10.1007","author":[{"given":"Chiu-Yuen","family":"Koo","sequence":"first","affiliation":[]},{"given":"Tak-Wah","family":"Lam","sequence":"additional","affiliation":[]},{"given":"Tsuen-Wan","family":"Ngan","sequence":"additional","affiliation":[]},{"given":"Kar-Keung","family":"To","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"issue":"2","key":"41_CR1","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/BF00365406","volume":"4","author":"S. Baruah","year":"1992","unstructured":"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\u2013144, 1992.","journal-title":"Journal of Real-Time Systems"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"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\u2013110, San Juan, Porto Rico, October 1991.","DOI":"10.1109\/SFCS.1991.185354"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"P. Berman and C. Coulston. Speed is more powerful than clairvoyance. In Proceedings of the Sixth Scandinavian Workshop on Algorithm Theory, pages 255\u2013263, July 1998.","DOI":"10.1007\/BFb0054373"},{"key":"41_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/3-540-44436-X_11","volume-title":"Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization","author":"B. DasGupta","year":"2000","unstructured":"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\u2013107. Springer, September 2000."},{"issue":"12","key":"41_CR5","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/32.58762","volume":"15","author":"L. Michael","year":"1989","unstructured":"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\u20131506, December 1989.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"Jeff Edmonds. Scheduling in the dark. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 179\u2013188, 1999.","DOI":"10.1145\/301250.301299"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"Bala Kalyanasundaram and Kirk Pruhs. Maximizing job completions online. In Proceedings of the Sixth European Symposium on Algorithms, pages 235\u2013246, 1998.","DOI":"10.1007\/3-540-68530-8_20"},{"issue":"4","key":"41_CR8","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"Bala Kalyanasundaram and Kirk Pruhs","year":"2000","unstructured":"Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM, 47(4):617\u2013643, July 2000.","journal-title":"Journal of the ACM"},{"issue":"2","key":"41_CR9","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"Gilad Koren and Dennis Shasha. Dover","year":"1995","unstructured":"Gilad Koren and Dennis Shasha. Dover: An optimal on-line scheduling algorithm for overloaded real-time systems. SIAM Journal of Computing, 24(2):318\u2013339, April 1995.","journal-title":"SIAM Journal of Computing"},{"key":"41_CR10","unstructured":"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."},{"key":"41_CR11","unstructured":"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\u2013632, 1999."},{"key":"41_CR12","unstructured":"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\u2013764, 2001."},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"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\u2013149, 1997.","DOI":"10.1145\/258533.258570"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:54Z","timestamp":1556803674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}