{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:38:17Z","timestamp":1742384297276,"version":"3.37.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642046322"},{"type":"electronic","value":"9783642046339"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04633-9_12","type":"book-chapter","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T13:57:15Z","timestamp":1254923835000},"page":"207-231","source":"Crossref","is-referenced-by-count":4,"title":["Competitive Two-Level Adaptive Scheduling Using Resource Augmentation"],"prefix":"10.1007","author":[{"given":"Hongyang","family":"Sun","sequence":"first","affiliation":[]},{"given":"Yangjie","family":"Cao","sequence":"additional","affiliation":[]},{"given":"Wen-Jing","family":"Hsu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Hsu, W.-J., Leiserson, C.E.: Adaptive scheduling with parallelism feedback. In: PPoPP, New York City, NY, USA, pp. 100\u2013109 (2006)","DOI":"10.1145\/1122971.1122988"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Leiserson, C.E.: An empirical evaluation of work stealing with parallelism feedback. In: ICDCS, Lisbon, Portugal, pp. 19\u201329 (2006)","DOI":"10.1109\/ICDCS.2006.14"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Leiserson, C.E.: Adaptive work stealing with parallelism feedback. In: PPoPP, San Jose, CA, USA, pp. 112\u2013120 (2007)","DOI":"10.1109\/IPDPS.2007.370496"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.L., Lam, T.W., Lee, L.K.: Scheduling for speed bounded processors. In: ICALP, Reykjavik, Iceland, pp. 409\u2013420 (2008)","DOI":"10.1007\/978-3-540-70575-8_34"},{"key":"12_CR5","unstructured":"Bansal, N., Pruhs, K., Stein, C.: Speed scaling for weighted flow time. In: SODA, New Orleans, LA, USA, pp. 805\u2013813 (2007)"},{"issue":"4","key":"12_CR6","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1145\/1008731.1008732","volume":"51","author":"L. Becchetti","year":"2004","unstructured":"Becchetti, L., Leonardi, S.: Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines. Journal of the ACM\u00a051(4), 517\u2013539 (2004)","journal-title":"Journal of the ACM"},{"issue":"2","key":"12_CR7","first-page":"181","volume":"6","author":"P. Berman","year":"1999","unstructured":"Berman, P., Coulston, C.: Speed is more powerful than clairvoyance. Nordic Journal of Computing\u00a06(2), 181\u2013193 (1999)","journal-title":"Nordic Journal of Computing"},{"issue":"5","key":"12_CR8","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"R.D. Blumofe","year":"1999","unstructured":"Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing. Journal of the ACM\u00a046(5), 720\u2013748 (1999)","journal-title":"Journal of the ACM"},{"key":"12_CR9","volume-title":"Online computation and competitive analysis","author":"A. Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)"},{"key":"12_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04550-3","volume-title":"Scheduling Algorithms","author":"P. Brucker","year":"2001","unstructured":"Brucker, P.: Scheduling Algorithms. Springer, New York (2001)"},{"key":"12_CR11","unstructured":"Chan, H.-L., Edmonds, J., Lam, T.-W., Lee, L.-K., Marchetti-Spaccamela, A., Pruhs, K.: Nonclairvoyant speed scaling for flow and energy. In: STACS, Freiburg, Germany, pp. 409\u2013420 (2009)"},{"key":"12_CR12","unstructured":"Deng, X., Gu, N., Brecht, T., Lu, K.: Preemptive scheduling of parallel jobs on multiprocessors. In: SODA, Philadelphia, PA, USA, pp. 159\u2013167 (1996)"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Scheduling in the dark. In: STOC, Atlanta, GA, USA, pp. 179\u2013188 (1999)","DOI":"10.1145\/301250.301299"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Chinn, D.D., Brecht, T., Deng, X.: Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. In: STOC, El Paso, TX, USA, pp. 120\u2013129 (1997)","DOI":"10.1145\/258533.258565"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Datta, S., Dymond, P.: TCP is competitive against a limited adversary. In: SPAA, San Diego, CA, USA, pp. 174\u2013183 (2003)","DOI":"10.1145\/777412.777440"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. In: SODA, New York, NY, USA, pp. 685\u2013692 (2009)","DOI":"10.1137\/1.9781611973068.75"},{"key":"12_CR17","unstructured":"Feitelson, D.G.: Job scheduling in multiprogrammed parallel systems (extended version). IBM Research Report RC19790 (87657) 2nd Revision (1997)"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-71035-6_1","volume-title":"Job Scheduling Strategies for Parallel Processing","author":"Y. He","year":"2007","unstructured":"He, Y., Hsu, W.-J., Leiserson, C.E.: Provably efficient two-level adaptive scheduling. In: Frachtenberg, E., Schwiegelshohn, U. (eds.) JSSPP 2006. LNCS, vol.\u00a04376, pp. 1\u201332. Springer, Heidelberg (2007)"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"He, Y., Hsu, W.-J., Leiserson, C.E.: Provably efficient online non-clairvoyant adaptive scheduling. In: IPDPS, Long Beach, CA, USA, pp. 1\u201310 (2007)","DOI":"10.1109\/IPDPS.2007.370303"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"He, Y., Sun, H., Hsu, W.-J.: Adaptive scheduling of parallel jobs on functionally heterogeneous resources. In: ICPP, Xi\u2019an, China, p. 43 (2007)","DOI":"10.1109\/ICPP.2007.12"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. In: FOCS, Milwaukee, WI, USA, pp. 214\u2013221 (1995)","DOI":"10.1109\/SFCS.1995.492478"},{"key":"12_CR22","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Pruhs, K.: Minimizing flow time nonclairvoyantly. In: FOCS, Miami Beach, FL, USA, p. 345 (1997)","DOI":"10.1109\/SFCS.1997.646123"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/978-3-540-87744-8_54","volume-title":"Algorithms - ESA 2008","author":"T.W. Lam","year":"2008","unstructured":"Lam, T.W., Lee, L.-K., To, I.K.-K., Wong, P.W.H.: Speed scaling functions for flow time scheduling based on active job count. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 647\u2013659. Springer, Heidelberg (2008)"},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/151244.151246","volume":"11","author":"C. McCann","year":"1993","unstructured":"McCann, C., Vaswani, R., Zahorjan, J.: A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors. ACM Transactions on Computer Systems\u00a011(2), 146\u2013178 (1993)","journal-title":"ACM Transactions on Computer Systems"},{"key":"12_CR25","unstructured":"Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. In: SODA, Austin, TX, USA, pp. 422\u2013431 (1993)"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation (extended abstract). In: STOC, El Paso, TX, USA, pp. 140\u2013149 (1997)","DOI":"10.1145\/258533.258570"},{"issue":"4","key":"12_CR27","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/1243401.1243411","volume":"34","author":"K. Pruhs","year":"2007","unstructured":"Pruhs, K.: Competitive online scheduling for server systems. ACM SIGMETRICS Performance Evaluation Review\u00a034(4), 52\u201358 (2007)","journal-title":"ACM SIGMETRICS Performance Evaluation Review"},{"key":"12_CR28","volume-title":"Handbook of scheduling: Algorithms, models, and performance analysis, ch. 15","author":"K. Pruhs","year":"2004","unstructured":"Pruhs, K., Torong, E., Sgall, J.: Online scheduling. In: Handbook of scheduling: Algorithms, models, and performance analysis, ch. 15, CRC Press, Boca Raton (2004)"},{"key":"12_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1007\/978-3-540-75520-3_65","volume-title":"Algorithms \u2013 ESA 2007","author":"J. Robert","year":"2007","unstructured":"Robert, J., Schabanel, N.: Non-clairvoyant batch set scheduling: Fairness is fair enough. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 741\u2013753. Springer, Heidelberg (2007)"},{"key":"12_CR30","unstructured":"Robert, J., Schabanel, N.: Non-clairvoyant scheduling with precedence constraints. In: SODA, San Francisco, CA, USA, pp. 491\u2013500 (2008)"},{"key":"12_CR31","unstructured":"Sen, S.: Dynamic processor allocation for adaptively parallel jobs. Master\u2019s thesis, Massachusetts Institute of technology (2004)"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Sun, H., Hsu, W.-J.: Adaptive B-Greedy (ABG): A simple yet efficient scheduling algorithm. In: SMTPS in conjunction with IPDPS, Miami, FL, USA, pp. 1\u20138 (2008)","DOI":"10.1109\/IPDPS.2008.4536546"},{"key":"12_CR33","doi-asserted-by":"crossref","unstructured":"Tucker, A., Gupta, A.: Process control and scheduling issues for multiprogrammed shared-memory multiprocessors. In: SOSP, New York, NY, USA, pp. 159\u2013166 (1989)","DOI":"10.1145\/74851.74866"}],"container-title":["Lecture Notes in Computer Science","Job Scheduling Strategies for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04633-9_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T16:28:21Z","timestamp":1739377701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04633-9_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642046322","9783642046339"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04633-9_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}