{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T18:24:51Z","timestamp":1648751091459},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T00:00:00Z","timestamp":1109635200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2005,3]]},"DOI":"10.1007\/s10878-005-6854-6","type":"journal-article","created":{"date-parts":[[2005,5,3]],"date-time":"2005-05-03T09:42:13Z","timestamp":1115113333000},"page":"157-165","source":"Crossref","is-referenced-by-count":1,"title":["A Tighter Extra-Resource Analysis of Online Deadline Scheduling"],"prefix":"10.1007","volume":"9","author":[{"given":"Tak-Wah","family":"Lam","sequence":"first","affiliation":[]},{"given":"Tusen-Wan Johnny","family":"Ngan","sequence":"additional","affiliation":[]},{"given":"Kar-Keung","family":"To","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"S. Baruah, \u201cOverload tolerance for single-processor workloads,\u201d in IEEE Symposium on Real Time Technology and Application, 1998, pp. 2\u201311.","DOI":"10.1109\/RTTAS.1998.683182"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"S. Baruah, G. Koren, B. Mishra, A. Raghunathan, L. Rosier, and D. Shasha, \u201cOn-line scheduling in the presence of overload,\u201d in Proc. 1991 IEEE Real-Time Systems Symposium, 1991, pp. 101\u2013110.","DOI":"10.1109\/SFCS.1991.185354"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"P. Berman and C. Coulston, \u201cSpeed is more powerful than clairvoyance,\u201d in Proc. 6th SWAT, 1998, pp. 255\u2013263.","DOI":"10.1007\/BFb0054373"},{"key":"CR4","unstructured":"A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998."},{"issue":"5","key":"CR5","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1002\/1099-1425(200009\/10)3:5<273::AID-JOS48>3.0.CO;2-0","volume":"3","author":"M. Brehob","year":"2000","unstructured":"M. Brehob, E. Torng, and P. Uthaisombut, \u201cApplying extra-resource analysis to load balancing,\u201d Journal of Scheduling, vol. 3, no. 5, pp. 273\u2013288, 2000.","journal-title":"Journal of Scheduling"},{"key":"CR6","unstructured":"H.L. Chan, T.W. Lam, and K.K. To, \u201cNon-migratory Online Deadline Scheduling on Multiprocessors,\u201d in Proc. SODA, 2004, pp. 970\u2013979."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tich\u00fd, and N. Vakhania, \u201cPreemptive scheduling in overloaded systems,\u201d in Proc. ICALP, 2002, pp. 800\u2013811.","DOI":"10.1007\/3-540-45465-9_68"},{"key":"CR8","unstructured":"M.L. Dertouzos, \u201cControl robotics: The procedural control of physical processes,\u201d in Proc. IFIP Congress, 1974, pp. 807\u2013813."},{"issue":"12","key":"CR9","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/32.58762","volume":"15","author":"M.L. Dertouzos","year":"1989","unstructured":"M.L. Dertouzos and A.K.L. Mok, \u201cMultiprocessor On-Line Scheduling of Hard-Real-Time Tasks,\u201d IEEE Transactions on Software Engineering, vol. 15, no. 12, pp. 1497\u20131506, 1989.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"J. Edmonds, \u201cScheduling in the dark,\u201d in Proc. STOC, 1999, pp. 179\u2013188.","DOI":"10.1145\/301250.301299"},{"issue":"4","key":"CR11","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B. Kalyanasundaram","year":"2000","unstructured":"B. Kalyanasundaram and K.R. Pruhs, \u201cSpeed is as powerful as clairvoyance,\u201d J. ACM, vol. 47, no. 4, pp. 617\u2013643, 2000.","journal-title":"J. ACM"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K.R. Pruhs, \u201cMaximizing job completions online,\u201d in Proc. ESA, 1998, pp. 235\u2013246.","DOI":"10.1007\/3-540-68530-8_20"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and K.R. Pruhs, \u201cOn-demand Broadcasting under Deadline,\u201d in Proc. ESA, 2003, pp. 313\u2013324.","DOI":"10.1007\/978-3-540-39658-1_30"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"J.H. Kim and K.Y. Chwa, \u201cScheduling Broadcasts with Deadlines,\u201d in Proc. COCOON, 2003, pp. 415\u2013424.","DOI":"10.1007\/3-540-45071-8_42"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"C.Y. Koo, T.W. Lam, T.W. Ngan, and K.K. To, \u201cExtra Processors versus Future Information in Optimal Deadline Scheduling,\u201d in Proc. SPAA, 2002, pp. 133\u2013142.","DOI":"10.1145\/564870.564890"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0304-3975(94)90165-1","volume":"128","author":"G. Koren","year":"1994","unstructured":"G. Koren and D. Shasha, \u201c{M}{O}{C}{A}: A multiprocessor on-line competitive algorithm real-time system scheduling,\u201d Theoretical Computer Science, vol. 128, pp. 75\u201397, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"CR17","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G. Koren","year":"1995","unstructured":"G. Koren and D. Shasha, \u201cDover: An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems,\u201d SIAM J. Comput., vol. 24, no. 2, pp. 318\u2013339, 1995.","journal-title":"SIAM J. Comput."},{"key":"CR18","unstructured":"T.W. Lam and K.K. To, \u201cPerformance Guarantee for Online Deadline Scheduling in the Presence of Overload,\u201d in Proc. SODA, 2001, pp. 755\u2013764."},{"key":"CR19","unstructured":"J. McCullough and E. Torng, \u201cSRPT Optimally Utilizes Faster Machines to Minimize Flow Time,\u201d in Proc. SODA, 2004, pp. 350\u2013358."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"C.A. Phillips, C. Stein, E. Torng, and J. Wein, \u201cOptimal time-critical scheduling via resource augmentation,\u201d in Proc. STOC, 1997, pp. 140\u2013149.","DOI":"10.1145\/258533.258570"},{"key":"CR21","first-page":"196","volume-title":"On-Line Algorithms: The State of the Art","author":"J. Sgall","year":"1998","unstructured":"J. Sgall, \u201cOn-line scheduling\u2013-a survey,\u201d in A. Fiat and G. Woeginger (ed.), On-Line Algorithms: The State of the Art, Lecture Notes in Computer Science, Springer Verlag, 1998, pp. 196\u2013231."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"J.A. Stankovic, M. Spuri, K. Ramamritham, and G.C. Buttazzo, Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms, Kluwer Academic Publishers, 1998.","DOI":"10.1007\/978-1-4615-5535-3"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-6854-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-005-6854-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-6854-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T05:22:10Z","timestamp":1586236930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-005-6854-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["6854"],"URL":"https:\/\/doi.org\/10.1007\/s10878-005-6854-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]}}}