{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,22]],"date-time":"2026-03-22T00:17:48Z","timestamp":1774138668817,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,8,9]],"date-time":"2012-08-09T00:00:00Z","timestamp":1344470400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9678-7","type":"journal-article","created":{"date-parts":[[2012,8,8]],"date-time":"2012-08-08T16:59:12Z","timestamp":1344445152000},"page":"404-425","source":"Crossref","is-referenced-by-count":37,"title":["Speed Scaling on Parallel Processors"],"prefix":"10.1007","volume":"68","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Swen","family":"Schmelzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,9]]},"reference":[{"issue":"5","key":"9678_CR1","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1735223.1735245","volume":"53","author":"S. Albers","year":"2010","unstructured":"Albers, S.: Energy-efficient algorithms. Commun. ACM 53(5), 86\u201396 (2010)","journal-title":"Commun. ACM"},{"issue":"4","key":"9678_CR2","doi-asserted-by":"crossref","DOI":"10.1145\/1290672.1290686","volume":"3","author":"S. Albers","year":"2007","unstructured":"Albers, S., Fujiwara, H.: Energy-efficient algorithms for flow time minimization. ACM Trans. Algorithms 3(4), 49 (2007)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9678_CR3","doi-asserted-by":"crossref","DOI":"10.1145\/1206035.1206038","volume":"54","author":"N. Bansal","year":"2007","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic speed scaling to manage energy and temperature. J. ACM 54(1), 3 (2007)","journal-title":"J. ACM"},{"key":"9678_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/978-3-540-70575-8_34","volume-title":"Proc. 35th International Colloquium on Automata, Languages and Programming","author":"N. Bansal","year":"2008","unstructured":"Bansal, N., Chan, H.-L., Lam, T.-W., Lee, K.-L.: Scheduling for speed bounded processors. In: Proc. 35th International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a05125, pp.\u00a0409\u2013420. Springer, Berlin (2008)"},{"key":"9678_CR5","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1137\/1.9781611973068.76","volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Chan, H.-L., Pruhs, K.: Speed scaling with an arbitrary power function. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 693\u2013701 (2009)"},{"key":"9678_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/978-3-642-02927-1_14","volume-title":"Proc. 36th International Colloqium on Automata, Languages and Programming","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Chan, H.-L., Pruhs, K., Katz, D.: Improved bounds for speed scaling in devices obeying the cube-root rule. In: Proc. 36th International Colloqium on Automata, Languages and Programming. LNCS, vol. 5555, pp. 144\u2013155. Springer, Berlin (2009)"},{"issue":"4","key":"9678_CR7","doi-asserted-by":"crossref","first-page":"1294","DOI":"10.1137\/08072125X","volume":"39","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Pruhs, K., Stein, C.: Speed scaling for weighted flow time. SIAM J. Comput. 39(4), 1294\u20131308 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9678_CR8","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1007\/s00453-009-9379-z","volume":"60","author":"N. Bansal","year":"2011","unstructured":"Bansal, N., Bunde, D.P., Chan, H.-L., Pruhs, K.: Average rate speed scaling. Algorithmica 60(4), 877\u2013889 (2011)","journal-title":"Algorithmica"},{"key":"9678_CR9","first-page":"364","volume-title":"Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Baptiste","year":"2006","unstructured":"Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: A polynomial time algorithm for offline dynamic power management. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 364\u2013367 (2006)"},{"key":"9678_CR10","series-title":"LNCS","first-page":"136","volume-title":"Proc. 15th Annual European Symposium on Algorithms","author":"P. Baptiste","year":"2007","unstructured":"Baptiste, P., Chrobak, M., D\u00fcrr, C.: Polynomial time algorithms for minimum energy scheduling. In: Proc. 15th Annual European Symposium on Algorithms. LNCS, vol. 4698, pp. 136\u2013150. Springer, Berlin (2007)"},{"issue":"7","key":"9678_CR11","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/1095408.1095420","volume":"3","author":"L.A. Barroso","year":"2005","unstructured":"Barroso, L.A.: The price of performance. ACM Queue 3(7), 48\u201353 (2005)","journal-title":"ACM Queue"},{"key":"9678_CR12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/978-3-642-20877-5_4","volume-title":"Proc. 8th Annual Conference on Theory and Applications of Models of Computation (TAMC)","author":"P.C. Bell","year":"2011","unstructured":"Bell, P.C., Wong, P.W.H.: Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. In: Proc. 8th Annual Conference on Theory and Applications of Models of Computation (TAMC). LNCS, vol. 6648, pp. 27\u201336. Springer, Berlin (2011)"},{"key":"9678_CR13","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/s10951-009-0123-y","volume":"12","author":"D.P. Bunde","year":"2009","unstructured":"Bunde, D.P.: Power-aware scheduling for makespan and flow. J. Sched. 12, 489\u2013500 (2009)","journal-title":"J. Sched."},{"issue":"1","key":"9678_CR14","volume":"6","author":"H.-L. Chan","year":"2009","unstructured":"Chan, H.-L., Chan, J.W.-T., Lam, T.W., Lee, L.-K., Mak, K.-S., Wong, P.W.H.: Optimizing throughput and energy in online deadline scheduling. ACM Trans. Algorithms 6(1), 10 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"9678_CR15","first-page":"101","volume-title":"Proc. 16th Euromicro Conference of Real-Time Systems","author":"J.-J. Chen","year":"2004","unstructured":"Chen, J.-J., Hsu, H.-R., Chuang, K.-H., Yang, C.-L., Pang, A.-C., Kuo, T.-W.: Multiprocessor energy-efficient scheduling with task migration considerations. In: Proc. 16th Euromicro Conference of Real-Time Systems, pp. 101\u2013108 (2004)"},{"key":"9678_CR16","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/11534273_30","volume-title":"Proc. 9th International Workshop on Algorithms and Data Structures","author":"J.-J. Chen","year":"2005","unstructured":"Chen, J.-J., Kuo, T.-W., Lu, H.-I.: Power-saving scheduling for weakly dynamic voltage scaling devices. In: Proc. 9th International Workshop on Algorithms and Data Structures. LNCS, vol.\u00a03608, pp.\u00a0338\u2013349. Springer, Berlin (2005)"},{"key":"9678_CR17","first-page":"46","volume-title":"Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"E.D. Demaine","year":"2007","unstructured":"Demaine, E.D., Ghodsi, M., Hajiaghayi, M.T., Sayedi-Roshkhar, A.S., Zadimoghaddam, M.: Scheduling to minimize gaps and power consumption. In: Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 46\u201354 (2007)"},{"key":"9678_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garay","year":"1979","unstructured":"Garay, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9678_CR19","first-page":"11","volume-title":"Proc. 21st Annual ACM Symposium on Parallel Algorithms and Architectures","author":"G. Greiner","year":"2009","unstructured":"Greiner, G., Nonner, T., Souza, A.: The bell is ringing in speed-scaled multiprocessor scheduling. In: Proc. 21st Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 11\u201318 (2009)"},{"key":"9678_CR20","doi-asserted-by":"crossref","first-page":"1242","DOI":"10.1137\/1.9781611973099.98","volume-title":"Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Gupta","year":"2012","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling heterogeneous processors isn\u2019t as easy as you think. In: Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1242\u20131253 (2012)"},{"key":"9678_CR21","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"9678_CR22","unstructured":"Intel pressroom. http:\/\/www.intel.com\/pressroom\/kits\/teraflops\/ or http:\/\/download.intel.com\/pressroom\/kits\/Teraflops\/Teraflops_Research_Chip_Overview.pdf"},{"issue":"2","key":"9678_CR23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1067309.1067324","volume":"36","author":"S. Irani","year":"2005","unstructured":"Irani, S., Pruhs, K.: Algorithmic problems in power management. SIGACT News 36(2), 63\u201376 (2005)","journal-title":"SIGACT News"},{"issue":"4","key":"9678_CR24","doi-asserted-by":"crossref","DOI":"10.1145\/1290672.1290678","volume":"3","author":"S. Irani","year":"2007","unstructured":"Irani, S., Shukla, S., Gupta, R.: Algorithms for power savings. ACM Trans. Algorithms 3(4), 41 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9678_CR25","series-title":"LNCS","first-page":"476","volume-title":"Proc. 18th International Symposium on Algorithms and Computation","author":"T.-W. Lam","year":"2007","unstructured":"Lam, T.-W., Lee, L.-K., To, I.K.-K., Wong, P.W.H.: Energy efficient deadline scheduling in two processor systems. In: Proc. 18th International Symposium on Algorithms and Computation. LNCS, vol.\u00a04835, pp.\u00a0476\u2013487. Springer, Berlin (2007)"},{"issue":"11","key":"9678_CR26","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1109\/TPDS.2008.115","volume":"19","author":"T.W. Lam","year":"2008","unstructured":"Lam, T.W., Lee, L.-K., To, I.K.-K., Wong, P.W.H.: Nonmigratory multiprocessor scheduling for response time and energy. IEEE Trans. Parallel Distrib. Syst. 19(11), 1527\u20131539 (2008)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"1","key":"9678_CR27","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/s10951-009-0145-5","volume":"15","author":"T.W. Lam","year":"2012","unstructured":"Lam, T.W., Lee, L.-K., To, I.K.-K., Wong, P.W.H.: Improved multi-processor scheduling for flow time and energy. J. Sched. 15(1), 105\u2013116 (2012)","journal-title":"J. Sched."},{"issue":"1","key":"9678_CR28","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s00224-007-9070-1","volume":"43","author":"K. Pruhs","year":"2008","unstructured":"Pruhs, K., van Stee, R., Uthaisombut, P.: Speed scaling of tasks with precedence constraints. Theory Comput. Syst. 43(1), 67\u201380 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9678_CR29","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9678_CR30","first-page":"374","volume-title":"Proc. 36th Annual Symposium on Foundations of Computer Science","author":"F. Yao","year":"1995","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced CPU energy. In: Proc. 36th Annual Symposium on Foundations of Computer Science, pp. 374\u2013382 (1995)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9678-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9678-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9678-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9678-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,9]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9678"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9678-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,9]]}}}