{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:44:32Z","timestamp":1742935472917,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031215339"},{"type":"electronic","value":"9783031215346"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":382,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We review algorithmic techniques for energy conservation in processing environments handling big data sets. Firstly, we address dynamic speed scaling, where processors can run at variable speed\/frequency. The goal is to use the speed spectrum of the processors so as to minimize energy consumption while providing a desired service. Here we focus on multi-processor platforms with heterogeneous CPUs. Secondly, we examine power-down mechanisms where idle devices can be transitioned into low-power standby and sleep states. We consider power-down mechanisms in massively parallel systems, where the components have to coordinate their active and idle periods. In particular we focus on data centers with homogeneous as well as heterogeneous servers.<\/jats:p>","DOI":"10.1007\/978-3-031-21534-6_11","type":"book-chapter","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:02:53Z","timestamp":1673985773000},"page":"196-212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Energy-Efficient Scheduling"],"prefix":"10.1007","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"unstructured":"The Advanced Configuration and Power Interface. The latest specification 6.3 (2019) is available e.g. at UEFI.org","key":"11_CR1"},{"unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications. Prentice Hall (1993)","key":"11_CR2"},{"issue":"5","key":"11_CR3","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/1735223.1735245","journal-title":"Commun. ACM"},{"doi-asserted-by":"publisher","unstructured":"Albers, S.: On energy conservation in data centers. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 35\u201344 (2017). https:\/\/doi.org\/10.1145\/3087556.3087560","key":"11_CR4","DOI":"10.1145\/3087556.3087560"},{"issue":"3","key":"11_CR5","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/3364210","volume":"6","author":"S Albers","year":"2019","unstructured":"Albers, S.: On energy conservation in data centers. ACM Trans. Parallel Comput. 6(3), 13:1-13:26 (2019). https:\/\/doi.org\/10.1145\/3364210","journal-title":"ACM Trans. Parallel Comput."},{"issue":"7","key":"11_CR6","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1016\/j.jcss.2015.03.001","volume":"81","author":"S Albers","year":"2015","unstructured":"Albers, S., Antoniadis, A., Greiner, G.: On multi-processor speed scaling with migration. J. Comput. Syst. Sci. 81(7), 1194\u20131209 (2015). https:\/\/doi.org\/10.1016\/j.jcss.2015.03.001","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Albers, S., Bampis, E., Letsios, D., Lucarelli, G., Stotz, R.: Scheduling on power-heterogeneous processors. In: Proceeding of the 12th American Symposium on Theoretical Informatics, LATIN, pp. 41\u201354 (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_4","key":"11_CR7","DOI":"10.1007\/978-3-662-49529-2_4"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ic.2017.09.013","volume":"257","author":"S Albers","year":"2017","unstructured":"Albers, S., Bampis, E., Letsios, D., Lucarelli, G., Stotz, R.: Scheduling on power-heterogeneous processors. Inf. Comput. 257, 22\u201333 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.09.013","journal-title":"Inf. Comput."},{"doi-asserted-by":"publisher","unstructured":"Albers, S., Quedenfeld, J.: Optimal algorithms for right-sizing data centers. In: Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. 363\u2013372 (2018). https:\/\/doi.org\/10.1145\/3210377.3210385","key":"11_CR9","DOI":"10.1145\/3210377.3210385"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.3390\/challe6010117","volume":"6","author":"ASG Andrae","year":"2015","unstructured":"Andrae, A.S.G., Edler, T.: On global electricity usage of communication technology: trends to 2030. Challenges 6(1), 117\u2013157 (2015). https:\/\/doi.org\/10.3390\/challe6010117","journal-title":"Challenges"},{"issue":"6","key":"11_CR11","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10951-015-0452-y","volume":"19","author":"E Angel","year":"2015","unstructured":"Angel, E., Bampis, E., Chau, V., Letsios, D.: Throughput maximization for speed scaling with agreeable deadlines. J. Sched. 19(6), 619\u2013625 (2015). https:\/\/doi.org\/10.1007\/s10951-015-0452-y","journal-title":"J. Sched."},{"issue":"4","key":"11_CR12","doi-asserted-by":"publisher","first-page":"1266","DOI":"10.1007\/s10878-018-0352-0","volume":"37","author":"E Angel","year":"2018","unstructured":"Angel, E., Bampis, E., Kacem, F., Letsios, D.: Speed scaling on parallel processors with migration. J. Comb. Optim. 37(4), 1266\u20131282 (2018). https:\/\/doi.org\/10.1007\/s10878-018-0352-0","journal-title":"J. Comb. Optim."},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-662-49529-2_6","volume-title":"LATIN 2016: Theoretical Informatics","author":"A Antoniadis","year":"2016","unstructured":"Antoniadis, A., Barcelo, N., Nugent, M., Pruhs, K., Schewior, K., Scquizzato, M.: Chasing convex bodies and functions. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 68\u201381. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_6"},{"doi-asserted-by":"publisher","unstructured":"Antoniadis, A., Garg, N., Kumar, G., Kumar, N.: Parallel machine scheduling to minimize energy consumption. In: Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2758\u20132769 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.168","key":"11_CR14","DOI":"10.1137\/1.9781611975994.168"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-319-89441-6_13","volume-title":"Approximation and Online Algorithms","author":"A Antoniadis","year":"2018","unstructured":"Antoniadis, A., Schewior, K.: A tight lower bound for online convex optimization with switching costs. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 164\u2013175. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89441-6_13"},{"issue":"4","key":"11_CR16","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/1721654.1721672","volume":"53","author":"M Armbrust","year":"2010","unstructured":"Armbrust, M., et al.: A view of cloud computing. Commun. ACM 53(4), 50\u201358 (2010). https:\/\/doi.org\/10.1145\/1721654.1721672","journal-title":"Commun. ACM"},{"issue":"5","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1499","DOI":"10.1137\/05063787X","volume":"37","author":"J Augustine","year":"2008","unstructured":"Augustine, J., Irani, S., Swamy, C.: Optimal power-down strategies. SIAM J. Comput. 37(5), 1499\u20131516 (2008). https:\/\/doi.org\/10.1137\/05063787X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10951-016-0500-2","volume":"21","author":"E Bampis","year":"2016","unstructured":"Bampis, E., Kononov, A., Letsios, D., Lucarelli, G., Sviridenko, M.: Energy-efficient scheduling and routing via randomized rounding. J. Sched. 21(1), 35\u201351 (2016). https:\/\/doi.org\/10.1007\/s10951-016-0500-2","journal-title":"J. Sched."},{"doi-asserted-by":"publisher","unstructured":"Bampis, E., Letsios, D., Lucarelli, G.: Speed-scaling with no preemptions. In: Proceeding of the 25th International Symposium on Algorithms and Computation, ISAAC, pp. 259\u2013269 (2014). https:\/\/doi.org\/10.1007\/978-3-319-13075-0_21","key":"11_CR19","DOI":"10.1007\/978-3-319-13075-0_21"},{"doi-asserted-by":"publisher","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R., Pruhs, K., Schewior, K., Stein, C.: A 2-competitive algorithm for online convex optimization with switching costs. In: Proceedings 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX, pp. 96\u2013109 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.96","key":"11_CR20","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.96"},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/1206035.1206038","volume":"54","author":"N Bansal","year":"2007","unstructured":"Bansal, N., Kimbrel, T., Pruhs, K.: Speed scaling to manage energy and temperature. J. ACM 54(1), 3:1-3:39 (2007). https:\/\/doi.org\/10.1145\/1206035.1206038","journal-title":"J. ACM"},{"issue":"12","key":"11_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1109\/MC.2007.443","volume":"40","author":"LA Barroso","year":"2007","unstructured":"Barroso, L.A., H\u00f6lzle, U.: The case for energy-proportional computing. IEEE Comput. 40(12), 33\u201337 (2007). https:\/\/doi.org\/10.1109\/MC.2007.443","journal-title":"IEEE Comput."},{"doi-asserted-by":"publisher","unstructured":"Bingham, B.D., Greenstreet, M.R.: Computation with energy-time trade-offs: models, algorithms and lower-bounds. In: IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA, pp. 143\u2013152 (2008). https:\/\/doi.org\/10.1109\/ISPA.2008.127","key":"11_CR23","DOI":"10.1109\/ISPA.2008.127"},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1109\/COMST.2015.2481183","volume":"18","author":"M Dayarathna","year":"2016","unstructured":"Dayarathna, M., Wen, Y., Fan, R.: Data center energy consumption modeling: a survey. IEEE Commun. Surv. Tutorials 18(1), 732\u2013794 (2016). https:\/\/doi.org\/10.1109\/COMST.2015.2481183","journal-title":"IEEE Commun. Surv. Tutorials"},{"issue":"3","key":"11_CR25","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1287\/mnsc.32.3.341","volume":"32","author":"A Federgruen","year":"1986","unstructured":"Federgruen, A., Groenevelt, H.: Preemptive scheduling of uniform machines by ordinary network flow techniques. Manag. Sci. 32(3), 341\u2013349 (1986). https:\/\/doi.org\/10.1287\/mnsc.32.3.341","journal-title":"Manag. Sci."},{"issue":"6","key":"11_CR26","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10951-016-0484-y","volume":"20","author":"E Feuerstein","year":"2016","unstructured":"Feuerstein, E., et al.: Minimizing worst-case and average-case makespan over scenarios. J. Sched. 20(6), 545\u2013555 (2016). https:\/\/doi.org\/10.1007\/s10951-016-0484-y","journal-title":"J. Sched."},{"doi-asserted-by":"publisher","unstructured":"Giannakopoulos, Y., Koutsoupias, E., Lazos, P.: Online market intermediation. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 47:1\u201347:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.47","key":"11_CR27","DOI":"10.4230\/LIPIcs.ICALP.2017.47"},{"issue":"4","key":"11_CR28","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"TF Gonzalez","year":"1976","unstructured":"Gonzalez, T.F., Sahni, S.: Open shop scheduling to minimize finish time. J. ACM 23(4), 665\u2013679 (1976). https:\/\/doi.org\/10.1145\/321978.321985","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling heterogeneous processors isn\u2019t as easy as you think. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, Kyoto, Japan, 17\u201319 January 2012, pp. 1242\u20131253 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.98","key":"11_CR29","DOI":"10.1137\/1.9781611973099.98"},{"doi-asserted-by":"publisher","unstructured":"Gupta, A., Krishnaswamy, R., Pruhs, K.: Scalably scheduling power-heterogeneous processors. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP, pp. 312\u2013323 (2010). https:\/\/doi.org\/10.1007\/978-3-642-14165-2_27","key":"11_CR30","DOI":"10.1007\/978-3-642-14165-2_27"},{"key":"11_CR31","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.comcom.2014.02.008","volume":"50","author":"WV Heddeghem","year":"2014","unstructured":"Heddeghem, W.V., et al.: Trends in worldwide ICT electricity consumption from 2007 to 2012. Comput. Commun. 50, 64\u201376 (2014). https:\/\/doi.org\/10.1016\/j.comcom.2014.02.008","journal-title":"Comput. Commun."},{"issue":"2","key":"11_CR32","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/1067309.1067324","journal-title":"SIGACT News"},{"issue":"4","key":"11_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1290672.1290678","volume":"3","author":"S Irani","year":"2007","unstructured":"Irani, S., Shukla, S.K., Gupta, R.: Algorithms for power savings. ACM Trans. Algorithms 3(4), 41 (2007). https:\/\/doi.org\/10.1145\/1290672.1290678","journal-title":"ACM Trans. Algorithms"},{"key":"11_CR34","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1038\/d41586-018-06610-y","volume":"561","author":"N Jones","year":"2018","unstructured":"Jones, N.: How to stop data centres from gobbling up the world\u2019s electricity. Nature 561, 163\u2013166 (2018). https:\/\/doi.org\/10.1038\/d41586-018-06610-y","journal-title":"Nature"},{"doi-asserted-by":"publisher","unstructured":"Lin, M., Wierman, A., Andrew, L.L.H., Thereska, E.: Dynamic right-sizing for power-proportional data centers. In: Proceedings 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, pp. 1098\u20131106 (2011). https:\/\/doi.org\/10.1109\/INFCOM.2011.5934885","key":"11_CR35","DOI":"10.1109\/INFCOM.2011.5934885"},{"doi-asserted-by":"publisher","unstructured":"Lin, M., Wierman, A., Andrew, L.L.H., Thereska, E.: Online dynamic capacity provisioning in data centers. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, Allerton, pp. 1159\u20131163 (2011). https:\/\/doi.org\/10.1109\/Allerton.2011.6120298","key":"11_CR36","DOI":"10.1109\/Allerton.2011.6120298"},{"issue":"5","key":"11_CR37","doi-asserted-by":"publisher","first-page":"1378","DOI":"10.1109\/TNET.2012.2226216","volume":"21","author":"M Lin","year":"2013","unstructured":"Lin, M., Wierman, A., Andrew, L.L.H., Thereska, E.: Dynamic right-sizing for power-proportional data centers. IEEE\/ACM Trans. Netw. 21(5), 1378\u20131391 (2013). https:\/\/doi.org\/10.1109\/TNET.2012.2226216","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"2","key":"11_CR38","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"},{"doi-asserted-by":"publisher","unstructured":"Yao, F.F., Demers, A.J., Shenker, S.: A scheduling model for reduced CPU energy. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS, pp. 374\u2013382 (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492493","key":"11_CR39","DOI":"10.1109\/SFCS.1995.492493"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21534-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:04:09Z","timestamp":1673985849000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21534-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031215339","9783031215346"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21534-6_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"18 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}