{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T17:09:44Z","timestamp":1675357784253},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,7]]},"abstract":"\n We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this analysis to two well-known on-line scheduling problems, the classic uniprocessor CPU scheduling problem 1 |\n \n r\n i<\/jats:sub>\n , pmtn|\u03a3 F\n i<\/jats:sub>\n ,\n <\/jats:italic>\n and the best-effort firm real-time scheduling problem 1|\n \n r\n i<\/jats:sub>\n , pmtn\n <\/jats:italic>\n | \u03a3\n \n w\n i<\/jats:sub>\n <\/jats:italic>\n ( 1-\n \n U\n i<\/jats:sub>\n <\/jats:italic>\n ). It is known that there are no constant competitive nonclairvoyant on-line algorithms for these problems. We show that there are simple on-line scheduling algorithms for these problems that are constant competitive if the online scheduler is equipped with a slightly faster processor than the adversary. Thus, a moderate increase in processor speed effectively gives the on-line scheduler the power of clairvoyance. Furthermore, the on-line scheduler can be constant competitive on all inputs that are not closely correlated with processor speed. We also show that the performance of an on-line scheduler is best-effort real time scheduling can be significantly improved if the system is designed in such a way that the laxity of every job is proportional to its length.\n <\/jats:p>","DOI":"10.1145\/347476.347479","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"617-643","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":323,"title":["Speed is as powerful as clairvoyance"],"prefix":"10.1145","volume":"47","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[{"name":"Univ. of Pittsburgh, Pittsburgh, PA"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"Univ. of Pittsburgh, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2000,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"31","volume-title":"Proceedings of the lOth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"ALBERS S.","year":"1999","unstructured":"ALBERS , S. , ARORA , S. , AND KHANNA , S. 1999 . Page replacement for generalized caching problems . In Proceedings of the lOth Annual ACM-SIAM Symposium on Discrete Algorithms ( Baltimore, Md., Jan. 17-19). ACM, New York , pp. 31 - 40 .]] ALBERS, S., ARORA, S., AND KHANNA, S. 1999. Page replacement for generalized caching problems. In Proceedings of the lOth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 31-40.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.620484"},{"key":"e_1_2_1_3_1","first-page":"228","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif.","author":"BARUAH S.","year":"1994","unstructured":"BARUAH , S. , HARITSA , J. , AND SHARMA , N. 1994 . On-line scheduling to maximize task completions . In Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 228 - 237 .]] BARUAH, S., HARITSA, J., AND SHARMA, N. 1994. On-line scheduling to maximize task completions. In Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 228-237.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"e_1_2_1_5_1","first-page":"101","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"BARUAH S.","year":"1991","unstructured":"BARUAH , S. , KOREN , G. , MISHRA , B. , RAGHUNATHAN , A. , ROSIER , L. , AND SHASHA , D. 1991 . On-line scheduling in the presence of overload . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 101 - 110 .]] 10.1109\/SFCS.1991.185354 BARUAH, S., KOREN, G., MISHRA, B., RAGHUNATHAN, A., ROSIER, L., AND SHASHA, D. 1991. On-line scheduling in the presence of overload. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 101-110.]] 10.1109\/SFCS.1991.185354"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01294264","article-title":"A new measure for the study of on-line algorithms","volume":"11","author":"BEN-DAVID S.","year":"1994","unstructured":"BEN-DAVID , S. , AND BORODIN , A. 1994 . A new measure for the study of on-line algorithms . Algorithmica 11 , 73 - 91 .]] BEN-DAVID, S., AND BORODIN, A. 1994. A new measure for the study of on-line algorithms. Algorithmica 11, 73-91.]]","journal-title":"Algorithmica"},{"key":"e_1_2_1_7_1","first-page":"255","volume-title":"Proceedings of the Scandinavian Workshop on Algorithms and Theory.","author":"BERMAN P.","year":"1998","unstructured":"BERMAN , P. , AND COULSTON , C. 1998 . Speed is more powerful than clairvoyance . In Proceedings of the Scandinavian Workshop on Algorithms and Theory. pp. 255 - 263 .]] BERMAN, P., AND COULSTON, C. 1998. Speed is more powerful than clairvoyance. In Proceedings of the Scandinavian Workshop on Algorithms and Theory. pp. 255-263.]]"},{"key":"e_1_2_1_8_1","volume-title":"Online Computation and Competitive Analysis","author":"BORODIN A.","unstructured":"BORODIN , A. , AND EL-YANIV , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press , Cambridge .]] BORODIN, A., AND EL-YANIV, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge.]]"},{"key":"e_1_2_1_9_1","volume-title":"Scheduling Algorithms","author":"BRUCKER P.","unstructured":"BRUCKER , P. 1995. Scheduling Algorithms . Springer-Verlag , New York .]] BRUCKER, P. 1995. Scheduling Algorithms. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_10_1","unstructured":"COLWELL R. SUCHOZA R. AND ZORINE D. 1995. On-line real-time scheduling with laxities. Manuscript.]] COLWELL R. SUCHOZA R. AND ZORINE D. 1995. On-line real-time scheduling with laxities. Manuscript.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/301250.301299","volume-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga., May 1-4). ACM","author":"EDMONDS J.","year":"1999","unstructured":"EDMONDS , J. 1999 . Scheduling in the dark . In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga., May 1-4). ACM , New York , pp. 179 - 188 .]] 10.1145\/301250.301299 EDMONDS, J. 1999. Scheduling in the dark. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (Atlanta, Ga., May 1-4). ACM, New York, pp. 179-188.]] 10.1145\/301250.301299"},{"key":"e_1_2_1_12_1","volume-title":"Operating System Concepts","author":"GALVIN P.","unstructured":"GALVIN , P. , AND SILVERSCHATZ , A. 1994. Operating System Concepts . Addison-Wesley, Reading , Mass .]] GALVIN, P., AND SILVERSCHATZ, A. 1994. Operating System Concepts. Addison-Wesley, Reading, Mass.]]"},{"key":"e_1_2_1_13_1","volume-title":"Approximation Algorithms for NP-hard Problems","author":"HALL L.","unstructured":"HALL , L. 1997. Approximation algorithms for scheduling . In Approximation Algorithms for NP-hard Problems . D. Hochbaum, ed. Chap. 2. PWS Publishing .]] HALL, L. 1997. Approximation algorithms for scheduling. In Approximation Algorithms for NP-hard Problems. D. Hochbaum, ed. Chap. 2. PWS Publishing.]]"},{"key":"e_1_2_1_14_1","first-page":"296","volume-title":"Proceedings of the European Symposium on Algorithms. Springer-Verlag","author":"KALYANASUNDARAM B.","year":"1997","unstructured":"KALYANASUNDARAM , B. , AND PRUHS , K. 1997 . Fault-tolerant real-time scheduling . In Proceedings of the European Symposium on Algorithms. Springer-Verlag , New York , pp. 296 - 307 .]] KALYANASUNDARAM, B., AND PRUHS, K. 1997. Fault-tolerant real-time scheduling. In Proceedings of the European Symposium on Algorithms. Springer-Verlag, New York, pp. 296-307.]]"},{"key":"e_1_2_1_15_1","first-page":"484","volume-title":"Proceedings of the European Symposium on Algorithms. Springer-Verlag","author":"KALYANASUNDARAM B.","year":"1995","unstructured":"KALYANASUNDARAM , B. , AND PRUHS , K. 1995 . The online transportation problem . In Proceedings of the European Symposium on Algorithms. Springer-Verlag , New York , pp. 484 - 493 .]] KALYANASUNDARAM, B., AND PRUHS, K. 1995. The online transportation problem. In Proceedings of the European Symposium on Algorithms. Springer-Verlag, New York, pp. 484-493.]]"},{"key":"e_1_2_1_16_1","first-page":"345","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag","author":"KALYANASUNDARAM B.","year":"1997","unstructured":"KALYANASUNDARAM , B. , AND PRUHS , K. 1997 . Minimizing flow-time nonclairvoyantly . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag , New York , pp. 345 - 352 .]] KALYANASUNDARAM, B., AND PRUHS, K. 1997. Minimizing flow-time nonclairvoyantly. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag, New York, pp. 345-352.]]"},{"key":"e_1_2_1_17_1","first-page":"235","volume-title":"Proceedings of the European Symposium on Algorithms. Springer-Verlag","author":"KALYANASUNDARAM B.","year":"1998","unstructured":"KALYANASUNDARAM , B. , AND PRUHS , K. 1998 . Maximizing job completions online . In Proceedings of the European Symposium on Algorithms. Springer-Verlag , New York , pp. 235 - 246 .]] KALYANASUNDARAM, B., AND PRUHS, K. 1998. Maximizing job completions online. In Proceedings of the European Symposium on Algorithms. Springer-Verlag, New York, pp. 235-246.]]"},{"key":"e_1_2_1_18_1","first-page":"394","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag","author":"KOUTSOUPIAS E.","year":"1994","unstructured":"KOUTSOUPIAS , E. , AND PAPADIMITRIOU , C. 1994 . Beyond competitive analysis . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag , New York , pp. 394 - 400 .]] KOUTSOUPIAS, E., AND PAPADIMITRIOU, C. 1994. Beyond competitive analysis. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. Springer-Verlag, New York, pp. 394-400.]]"},{"key":"e_1_2_1_19_1","volume-title":"The Art of Computer Programming","author":"KNUTH D.","unstructured":"KNUTH , D. 1973. The Art of Computer Programming , vol. 1 . Addison-Wesley , Reading, Mass .]] KNUTH, D. 1973. The Art of Computer Programming, vol. 1. Addison-Wesley, Reading, Mass.]]"},{"key":"e_1_2_1_20_1","first-page":"290","volume-title":"Proceedings of the IEEE Real-time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif.","author":"KOREN G.","year":"1992","unstructured":"KOREN , G. , AND SHASHA , D. 1992 . D .... : An optimal on-line scheduling algorithm for overloaded real-time systems . In Proceedings of the IEEE Real-time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 290 - 299 .]] KOREN, G., AND SHASHA, D. 1992. D .... : An optimal on-line scheduling algorithm for overloaded real-time systems. In Proceedings of the IEEE Real-time Systems Symposium. IEEE Computer Society Press, Los Alamitos, Calif., pp. 290-299.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90165-1"},{"key":"e_1_2_1_22_1","first-page":"623","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"LAM T. W.","year":"1999","unstructured":"LAM , T. W. , AND TO , K. K. 1999 . Trade-offs between speed and processor in hard-deadline scheduling . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms ( Baltimore, Md., Jan. 17-19). ACM, New York , pp. 623 - 632 .]] LAM, T. W., AND TO, K. K. 1999. Trade-offs between speed and processor in hard-deadline scheduling. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Md., Jan. 17-19). ACM, New York, pp. 623-632.]]"},{"key":"e_1_2_1_23_1","first-page":"445","volume-title":"Logistics of Production and Inventory, Handbooks in OR &","author":"LAWLER E.","unstructured":"LAWLER , E. , LENSTRA , J. K. , RINNOOY NAN , A. , AND SHMOYS , D. 1993. Sequencing and scheduling: algorithms and complexity . In Logistics of Production and Inventory, Handbooks in OR & ; MS 4, S. Graves, A. Rinnooy Kan, and P. Zipkin, eds. Chap. 9. Elsevier Science , Amsterdam, The Netherlands, pp. 445 - 522 .]] LAWLER, E., LENSTRA, J. K., RINNOOY NAN, A., AND SHMOYS, D. 1993. Sequencing and scheduling: algorithms and complexity. In Logistics of Production and Inventory, Handbooks in OR & MS 4, S. Graves, A. Rinnooy Kan, and P. Zipkin, eds. Chap. 9. Elsevier Science, Amsterdam, The Netherlands, pp. 445-522.]]"},{"key":"e_1_2_1_24_1","first-page":"50","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif.","author":"MANSOUR Y.","year":"1998","unstructured":"MANSOUR , Y. , AND PATT-SHAMIR , B. 1998 . Jitter control in QoS networks . In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif. , pp. 50 - 59 .]] MANSOUR, Y., AND PATT-SHAMIR, B. 1998. Jitter control in QoS networks. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 50-59.]]"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Symposium on Algorithms and Computation. 71-77","author":"MATSUMOTO T.","year":"1992","unstructured":"MATSUMOTO , T. 1992 . Competitive analysis of the round robin algorithm . In Proceedings of the International Symposium on Algorithms and Computation. 71-77 .]] MATSUMOTO, T. 1992. Competitive analysis of the round robin algorithm. In Proceedings of the International Symposium on Algorithms and Computation. 71-77.]]"},{"key":"e_1_2_1_26_1","volume-title":"Operating Systems: Concepts and Designs","author":"MILENKOVIC M.","year":"1992","unstructured":"MILENKOVIC , M. 1992 . Operating Systems: Concepts and Designs . McGraw-Hill , New York .]] MILENKOVIC, M. 1992. Operating Systems: Concepts and Designs. McGraw-Hill, New York.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_28_1","first-page":"140","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM","author":"PHILLIPS C.","year":"1997","unstructured":"PHILLIPS , C. , STEIN , C. , TORNG , E. , AND WEIN , J. 1997 . Optimal time-critical scheduling via resource augmentation . In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM , New York , pp. 140 - 149 .]] 10.1145\/258533.258570 PHILLIPS, C., STEIN, C., TORNG, E., AND WEIN, J. 1997. Optimal time-critical scheduling via resource augmentation. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 4-6). ACM, New York, pp. 140-149.]] 10.1145\/258533.258570"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1090\/dimacs\/007\/05","article-title":"A statistical adversary for on-line algorithms","volume":"7","author":"RAGHAVAN P.","year":"1992","unstructured":"RAGHAVAN , P. 1992 . A statistical adversary for on-line algorithms . Online Algorithms, DIMACS Series in Discrete Mathematics and Computer Science 7 , 79 - 83 .]] RAGHAVAN, P. 1992. A statistical adversary for on-line algorithms. Online Algorithms, DIMACS Series in Discrete Mathematics and Computer Science 7, 79-83.]]","journal-title":"Online Algorithms, DIMACS Series in Discrete Mathematics and Computer Science"},{"key":"e_1_2_1_30_1","volume-title":"On-Line Algorithms: The State of the Art","author":"SGALL J.","unstructured":"SGALL , J. 1998. On-line scheduling--A survey . In On-Line Algorithms: The State of the Art , A. Fiat and G. Woeginger, eds. Lecture Notes in Computer Science, Springer-Verlag , New York.]] SGALL, J. 1998. On-line scheduling--A survey. In On-Line Algorithms: The State of the Art, A. Fiat and G. Woeginger, eds. Lecture Notes in Computer Science, Springer-Verlag, New York.]]"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90150-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","article-title":"The k-server dual and loose competitiveness for paging","volume":"11","author":"YOUNG N.","year":"1994","unstructured":"YOUNG , N. 1994 . The k-server dual and loose competitiveness for paging . Algorithmica 11 , 525 - 541 .]] YOUNG, N. 1994.The k-server dual and loose competitiveness for paging. Algorithmica 11,525-541.]]","journal-title":"Algorithmica"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/347476.347479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T23:36:19Z","timestamp":1672616179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/347476.347479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,7]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2000,7]]}},"alternative-id":["10.1145\/347476.347479"],"URL":"http:\/\/dx.doi.org\/10.1145\/347476.347479","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,7]]},"assertion":[{"value":"2000-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}