{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:20:10Z","timestamp":1772119210019,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T00:00:00Z","timestamp":1750809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T00:00:00Z","timestamp":1750809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We consider the problem of energy-efficient scheduling across multiple processors with a power-down mechanism. In this setting a set of\n                    <jats:italic>n<\/jats:italic>\n                    jobs with individual release times, deadlines, and processing volumes must be scheduled across\n                    <jats:italic>m<\/jats:italic>\n                    parallel processors while minimizing the consumed energy. When idle, each processor can be turned off to save energy, while turning it on requires a fixed amount of energy. For the special case of a single processor, the greedy Left-to-Right algorithm [1] guarantees an approximation factor of 2. We generalize this simple greedy policy to the case of\n                    <jats:inline-formula>\n                      <jats:tex-math>$$m \\ge 1$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    processors running in parallel and show that the energy costs are still bounded by\n                    <jats:inline-formula>\n                      <jats:tex-math>$$2 {{\\,\\textrm{OPT}\\,}}+ P$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:tex-math>$${{\\,\\textrm{OPT}\\,}}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the energy consumed by an optimal solution and\n                    <jats:inline-formula>\n                      <jats:tex-math>$$P &lt; {{\\,\\textrm{OPT}\\,}}$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is the total processing volume. Our algorithm has a running time of\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\mathcal {O}(n f \\log d)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:italic>d<\/jats:italic>\n                    is the difference between the last deadline and the earliest release time, and\n                    <jats:italic>f<\/jats:italic>\n                    is the running time of a maximum flow calculation in a network of\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\mathcal {O}(n)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    nodes.\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10226-x","type":"journal-article","created":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T07:29:26Z","timestamp":1750836566000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Greedy Minimum-Energy Scheduling"],"prefix":"10.1007","volume":"69","author":[{"given":"Gunther","family":"Bidlingmaier","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,25]]},"reference":[{"key":"10226_CR1","unstructured":"Irani, S., Shukla, S.K., Gupta, R.K.: Algorithms for power savings. In: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pp. 37\u201346. ACM\/SIAM, (2003). http:\/\/dl.acm.org\/citation.cfm?id=644108.644115"},{"key":"10226_CR2","doi-asserted-by":"crossref","unstructured":"Baptiste, P.: Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. In: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm. SODA \u201906, pp. 364\u2013367. Society for Industrial and Applied Mathematics, USA (2006)","DOI":"10.1145\/1109557.1109598"},{"key":"10226_CR3","doi-asserted-by":"crossref","unstructured":"Baptiste, P., Chrobak, M., D\u00fcrr, C.: Polynomial time algorithms for minimum energy scheduling. In: European Symposium on Algorithms, pp. 136\u2013150. Springer (2007)","DOI":"10.1007\/978-3-540-75520-3_14"},{"key":"10226_CR4","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Ghodsi, M., Hajiaghayi, M.T., Sayedi-Roshkhar, A.S., Zadimoghaddam, M.: Scheduling to minimize gaps and power consumption. In: Proceedings of the nineteenth annual acm symposium on parallel algorithms and architectures. SPAA \u201907, pp. 46\u201354. Association for Computing Machinery, New York, NY, USA (2007). https:\/\/doi.org\/10.1145\/1248377.1248385","DOI":"10.1145\/1248377.1248385"},{"key":"10226_CR5","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Garg, N., Kumar, G., Kumar, N.: Parallel machine scheduling to minimize energy consumption. In: Proceedings of the thirty-first annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201920, pp. 2758\u20132769. Society for Industrial and Applied Mathematics, USA (2020)","DOI":"10.1137\/1.9781611975994.168"},{"key":"10226_CR6","doi-asserted-by":"publisher","unstructured":"Antoniadis, A., Kumar, G., Kumar, N.: Skeletons and Minimum Energy Scheduling. In: Ahn, H.-K., Sadakane, K. (eds.) 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 212, pp. 51\u201315116. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.51. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/15484","DOI":"10.4230\/LIPIcs.ISAAC.2021.51"},{"issue":"3","key":"10226_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10951-016-0492-y","volume":"20","author":"M Chrobak","year":"2017","unstructured":"Chrobak, M., Feige, U., Hajiaghayi, M.T., Khanna, S., Li, F., Naor, S.: A greedy approximation algorithm for minimum-gap scheduling. J. of Scheduling 20(3), 279\u2013292 (2017). https:\/\/doi.org\/10.1007\/s10951-016-0492-y","journal-title":"J. of Scheduling"},{"key":"10226_CR8","doi-asserted-by":"publisher","unstructured":"Chrobak, M., Golin, M., Lam, T.-W., Nogneng, D.: Scheduling with gaps: New models and algorithms. In: Proceedings of the 9th international conference on algorithms and complexity - Volume 9079. CIAC 2015, pp. 114\u2013126. Springer, Berlin, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-319-18173-8_8","DOI":"10.1007\/978-3-319-18173-8_8"},{"key":"10226_CR9","doi-asserted-by":"publisher","unstructured":"Chen, J.-J., Kao, M.-J., Lee, D.T., Rutter, I., Wagner, D.: Online Dynamic Power Management with Hard Real-Time Guarantees. In: Mayr, E.W., Portier, N. (eds.) 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 226\u2013238. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.226","DOI":"10.4230\/LIPIcs.STACS.2014.226"},{"key":"10226_CR10","doi-asserted-by":"publisher","unstructured":"Liang, Y.-C., Iwama, K., Liao, C.-S.: Improving the Bounds of the Online Dynamic Power Management Problem. In: Bae, S.W., Park, H. (eds.) 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 248, pp. 28\u201312816. Schloss Dagstuhl\u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2022.28","DOI":"10.4230\/LIPIcs.ISAAC.2022.28"},{"key":"10226_CR11","doi-asserted-by":"publisher","unstructured":"Yao, F., Demers, A., Shenker, S.: A scheduling model for reduced cpu energy. In: Proceedings of IEEE 36th annual foundations of computer science, pp. 374\u2013382 (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492493","DOI":"10.1109\/SFCS.1995.492493"},{"key":"10226_CR12","doi-asserted-by":"publisher","unstructured":"Albers, S., Antoniadis, A.: Race to idle: New algorithms for speed scaling with a sleep state. ACM Trans. Algorithms 10(2) (2014) https:\/\/doi.org\/10.1145\/2556953","DOI":"10.1145\/2556953"},{"key":"10226_CR13","doi-asserted-by":"crossref","unstructured":"Antoniadis, A., Huang, C.-C., Ott, S.: A fully polynomial-time approximation scheme for speed scaling with sleep state. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201915, pp. 1102\u20131113. Society for Industrial and Applied Mathematics, USA (2015)","DOI":"10.1137\/1.9781611973730.74"},{"key":"10226_CR14","doi-asserted-by":"publisher","unstructured":"Albers, S.: On energy conservation in data centers. ACM Trans. Parallel Comput. 6(3) (2019). https:\/\/doi.org\/10.1145\/3364210","DOI":"10.1145\/3364210"},{"key":"10226_CR15","doi-asserted-by":"publisher","unstructured":"Albers, S., Quedenfeld, J.: Optimal algorithms for right-sizing data centers. ACM Trans. Parallel Comput. 9(4) (2022). https:\/\/doi.org\/10.1145\/3565513","DOI":"10.1145\/3565513"},{"key":"10226_CR16","doi-asserted-by":"publisher","unstructured":"Albers, S., Quedenfeld, J.: Algorithms for energy conservation in heterogeneous data centers. Theor. Comput. Sci. 896(C), 111\u2013131 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.10.009","DOI":"10.1016\/j.tcs.2021.10.009"},{"key":"10226_CR17","doi-asserted-by":"publisher","unstructured":"Angel, E., Bampis, E.: Low complexity scheduling algorithm minimizing the energy for tasks with agreeable deadlines. In: Proceedings of the 10th Latin American International Conference on Theoretical Informatics. LATIN\u201912, pp. 13\u201324. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29344-3_2","DOI":"10.1007\/978-3-642-29344-3_2"},{"key":"10226_CR18","doi-asserted-by":"publisher","unstructured":"Brauner, N., Kovalyov, M.Y., Quilliot, A., Toussaint, H.: No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines. Comput. Oper. Res. 132(C) (2025). https:\/\/doi.org\/10.1016\/j.cor.2021.105315","DOI":"10.1016\/j.cor.2021.105315"},{"key":"10226_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-031-49815-2_5","volume-title":"Approximation and Online Algorithms","author":"G Bidlingmaier","year":"2023","unstructured":"Bidlingmaier, G.: Greedy minimum-energy scheduling. In: Byrka, J., Wiese, A. (eds.) Approximation and Online Algorithms, pp. 59\u201373. Springer, Cham (2023)"},{"key":"10226_CR20","doi-asserted-by":"publisher","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals Discrete Math. 5, 287\u2013326 (1979). https:\/\/doi.org\/10.1016\/S0167-5060(08)70356-X","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"10226_CR21","doi-asserted-by":"publisher","unstructured":"Brucker, P.: Scheduling Algorithms vol. 47 (2004). https:\/\/doi.org\/10.2307\/3010416","DOI":"10.2307\/3010416"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10226-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10226-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10226-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T05:21:09Z","timestamp":1759296069000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10226-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,25]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10226"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10226-x","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4351647\/v1","asserted-by":"object"}]},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,25]]},"assertion":[{"value":"3 June 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"27"}}