{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:20Z","timestamp":1750220180111,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Adobe"},{"name":"Amazon"},{"name":"Computing Research Association","award":["CIFellowship"],"award-info":[{"award-number":["CIFellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538582","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"369-380","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Balancing Flow Time and Energy Consumption"],"prefix":"10.1145","author":[{"given":"Sami","family":"Davies","sequence":"first","affiliation":[{"name":"Northwestern University, Evanston, IL, USA"}]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, IL, USA"}]},{"given":"Shirley","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, IL, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9678-7"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.05.023"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.168"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989512"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.suscom.2012.10.003"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612672"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860000088"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109598"},{"key":"e_1_3_2_1_9_1","volume-title":"15th Annual European Symposium, Eilat, Israel, October 8--10, 2007, Proceedings (Lecture Notes in Computer Science","volume":"150","author":"Baptiste Philippe","year":"2007","unstructured":"Philippe Baptiste , Marek Chrobak , and Christoph D\u00fcrr . 2007 . Polynomial Time Algorithms for Minimum Energy Scheduling. In Algorithms - ESA 2007 , 15th Annual European Symposium, Eilat, Israel, October 8--10, 2007, Proceedings (Lecture Notes in Computer Science , Vol. 4698), Lars Arge, Michael Hoffmann, and Emo Welzl (Eds.). Springer, 136-- 150 . https:\/\/doi.org\/10.1007\/978--3--540--75520--3_14 10.1007\/978--3--540--75520--3_14 Philippe Baptiste, Marek Chrobak, and Christoph D\u00fcrr. 2007. Polynomial Time Algorithms for Minimum Energy Scheduling. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8--10, 2007, Proceedings (Lecture Notes in Computer Science, Vol. 4698), Lars Arge, Michael Hoffmann, and Emo Welzl (Eds.). Springer, 136--150. https:\/\/doi.org\/10.1007\/978--3--540--75520--3_14"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024012811536"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00079"},{"key":"e_1_3_2_1_12_1","volume-title":"25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13","author":"Bender Michael A.","year":"2013","unstructured":"Michael A. Bender , David P. Bunde , Vitus J. Leung , Samuel McCauley , and Cynthia A. Phillips . 2013. Efficient scheduling to minimize calibrations . In 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13 , Montreal, QC, Canada - July 23 - 25 , 2013 , Guy E. Blelloch and Berthold V\u00f6cking (Eds.). ACM, 280--287. https:\/\/doi.org\/10.1145\/2486159.2486193 10.1145\/2486159.2486193 Michael A. Bender, David P. Bunde, Vitus J. Leung, Samuel McCauley, and Cynthia A. Phillips. 2013. Efficient scheduling to minimize calibrations. In 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '13, Montreal, QC, Canada - July 23 - 25, 2013, Guy E. Blelloch and Berthold V\u00f6cking (Eds.). ACM, 280--287. https:\/\/doi.org\/10.1145\/2486159.2486193"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-020-00676-1"},{"key":"e_1_3_2_1_14_1","volume-title":"29th International Symposium on Algorithms and Computation, ISAAC 2018","volume":"13","author":"Chan Timothy M.","year":"2018","unstructured":"Timothy M. Chan , Thomas C. van Dijk , Krzysztof Fleszar , Joachim Spoerhase , and AlexanderWolff. 2018 . Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity . In 29th International Symposium on Algorithms and Computation, ISAAC 2018 , December 16 --19 , 2018, Jiaoxi, Yilan, Taiwan (LIPIcs, Vol. 123), Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 61:1--61: 13 . https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.61 10.4230\/LIPIcs.ISAAC.2018.61 Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar, Joachim Spoerhase, and AlexanderWolff. 2018. Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity. In 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16--19, 2018, Jiaoxi, Yilan, Taiwan (LIPIcs, Vol. 123), Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 61:1--61:13. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.61"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings (Lecture Notes in Computer Science","volume":"300","author":"Chang Jessica","year":"2012","unstructured":"Jessica Chang , Harold N. Gabow , and Samir Khuller . 2012 . A Model for Minimizing Active Processor Time. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10--12, 2012 . Proceedings (Lecture Notes in Computer Science , Vol. 7501), Leah Epstein and Paolo Ferragina (Eds.). Springer, 289-- 300 . https:\/\/doi.org\/10.1007\/978--3--642--33090--2_26 10.1007\/978--3--642--33090--2_26 Jessica Chang, Harold N. Gabow, and Samir Khuller. 2012. A Model for Minimizing Active Processor Time. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10--12, 2012. Proceedings (Lecture Notes in Computer Science, Vol. 7501), Leah Epstein and Paolo Ferragina (Eds.). Springer, 289--300. https:\/\/doi.org\/10.1007\/978--3--642--33090--2_26"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-017-0531-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-41672-0_13"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248385"},{"volume-title":"Scheduling for Parallel Processing","author":"Drozdowski Maciej","key":"e_1_3_2_1_19_1","unstructured":"Maciej Drozdowski . 2009. Scheduling for Parallel Processing . Springer . https:\/\/doi.org\/10.1007\/978--1--84882--310--5 10.1007\/978--1--84882--310--5 Maciej Drozdowski. 2009. Scheduling for Parallel Processing. Springer. https:\/\/doi.org\/10.1007\/978--1--84882--310--5"},{"key":"e_1_3_2_1_20_1","volume-title":"14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006, Proceedings (Lecture Notes in Computer Science","volume":"326","author":"D\u00fcrr Christoph","year":"2006","unstructured":"Christoph D\u00fcrr and Mathilde Hurand . 2006 . Finding Total Unimodularity in Optimization Problems Solved by Linear Programs. In Algorithms - ESA 2006 , 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006, Proceedings (Lecture Notes in Computer Science , Vol. 4168), Yossi Azar and Thomas Erlebach (Eds.). Springer, 315-- 326 . https:\/\/doi.org\/10.1007\/11841036_30 10.1007\/11841036_30 Christoph D\u00fcrr and Mathilde Hurand. 2006. Finding Total Unimodularity in Optimization Problems Solved by Linear Programs. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11--13, 2006, Proceedings (Lecture Notes in Computer Science, Vol. 4168), Yossi Azar and Thomas Erlebach (Eds.). Springer, 315--326. https:\/\/doi.org\/10.1007\/11841036_30"},{"key":"e_1_3_2_1_21_1","volume-title":"A QPTAS for stabbing rectangles. CoRR abs\/2107.06571","author":"Eisenbrand Friedrich","year":"2021","unstructured":"Friedrich Eisenbrand , Martina Gallato , Ola Svensson , and Moritz Venzin . 2021. A QPTAS for stabbing rectangles. CoRR abs\/2107.06571 ( 2021 ). arXiv:2107.06571 https:\/\/arxiv.org\/abs\/2107.06571 Friedrich Eisenbrand, Martina Gallato, Ola Svensson, and Moritz Venzin. 2021. A QPTAS for stabbing rectangles. CoRR abs\/2107.06571 (2021). arXiv:2107.06571 https:\/\/arxiv.org\/abs\/2107.06571"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367074"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310531"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015","author":"Jeremy","year":"2015","unstructured":"Jeremy T. Fineman and Brendan Sheridan. 2015. Scheduling Non-Unit Jobs to Minimize Calibrations . In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 , Portland, OR, USA, June 13--15 , 2015 , Guy E. Blelloch and Kunal Agrawal (Eds.). ACM, 161--170. https:\/\/doi.org\/10.1145\/2755573.2755605 10.1145\/2755573.2755605 Jeremy T. Fineman and Brendan Sheridan. 2015. Scheduling Non-Unit Jobs to Minimize Calibrations. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13--15, 2015, Guy E. Blelloch and Kunal Agrawal (Eds.). ACM, 161--170. https:\/\/doi.org\/10.1145\/2755573.2755605"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161017"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.011"},{"key":"e_1_3_2_1_27_1","volume-title":"29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference) (LIPIcs","volume":"15","author":"Grandoni Fabrizio","year":"2021","unstructured":"Fabrizio Grandoni , Tobias M\u00f6mke , and Andreas Wiese . 2021 . Faster (1+)- Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back . In 29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference) (LIPIcs , Vol. 204), Petra Mutzel, Rasmus Pagh, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 49:1--49: 15 . https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.49 10.4230\/LIPIcs.ESA.2021.49 Fabrizio Grandoni, Tobias M\u00f6mke, and Andreas Wiese. 2021. Faster (1+)- Approximation for Unsplittable Flow on a Path via Resource Augmentation and Back. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6--8, 2021, Lisbon, Portugal (Virtual Conference) (LIPIcs, Vol. 204), Petra Mutzel, Rasmus Pagh, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 49:1--49:15. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.49"},{"key":"e_1_3_2_1_28_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (Leibniz International Proceedings in Informatics (LIPIcs)","author":"Khandekar Rohit","year":"2010","unstructured":"Rohit Khandekar , Baruch Schieber , Hadas Shachnai , and Tami Tamir . 2010. Minimizing Busy Time in Multiple Machine Real-time Scheduling . In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 8), Kamal Lodaya and Meena Mahajan (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 169-- 180 . https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS. 2010 .169 10.4230\/LIPIcs.FSTTCS.2010.169 Rohit Khandekar, Baruch Schieber, Hadas Shachnai, and Tami Tamir. 2010. Minimizing Busy Time in Multiple Machine Real-time Scheduling. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 8), Kamal Lodaya and Meena Mahajan (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 169--180. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2010.169"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_44"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-020-00653-8"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210659"},{"key":"e_1_3_2_1_32_1","volume-title":"Analysis of Busy-Time Scheduling on Heterogeneous Machines. In SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures","author":"Liu Mozhengfu","year":"2021","unstructured":"Mozhengfu Liu and Xueyan Tang . 2021 . Analysis of Busy-Time Scheduling on Heterogeneous Machines. In SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures , Virtual Event, USA, 6- -8 July, 2021, Kunal Agrawal and Yossi Azar (Eds.). ACM, 340--350. https:\/\/doi.org\/10.1145\/3409964.3461795 10.1145\/3409964.3461795 Mozhengfu Liu and Xueyan Tang. 2021. Analysis of Busy-Time Scheduling on Heterogeneous Machines. In SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6--8 July, 2021, Kunal Agrawal and Yossi Azar (Eds.). ACM, 340--350. https:\/\/doi.org\/10.1145\/3409964.3461795"},{"key":"e_1_3_2_1_33_1","volume-title":"Third International Workshop, WAOA 2005","author":"Pruhs Kirk","year":"2005","unstructured":"Kirk Pruhs , Rob van Stee , and Patchrawat Uthaisombut . 2005 . Speed Scaling of Tasks with Precedence Constraints. In Approximation and Online Algorithms , Third International Workshop, WAOA 2005 , Palma de Mallorca, Spain, October 6--7 , 2005, Revised Papers (Lecture Notes in Computer Science, Vol. 3879), Thomas Erlebach and Giuseppe Persiano (Eds.). Springer, 307--319. https:\/\/doi.org\/10.1007\/11671411_24 10.1007\/11671411_24 Kirk Pruhs, Rob van Stee, and Patchrawat Uthaisombut. 2005. Speed Scaling of Tasks with Precedence Constraints. In Approximation and Online Algorithms, Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6--7, 2005, Revised Papers (Lecture Notes in Computer Science, Vol. 3879), Thomas Erlebach and Giuseppe Persiano (Eds.). Springer, 307--319. https:\/\/doi.org\/10.1007\/11671411_24"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451075"},{"key":"e_1_3_2_1_35_1","volume-title":"NP-completeness of the Active Time Scheduling Problem. CoRR abs\/2112.03255","author":"Saha Sagnik","year":"2021","unstructured":"Sagnik Saha and Manish Purohit . 2021. NP-completeness of the Active Time Scheduling Problem. CoRR abs\/2112.03255 ( 2021 ). arXiv:2112.03255 https:\/\/arxiv.org\/abs\/2112.03255 Sagnik Saha and Manish Purohit. 2021. NP-completeness of the Active Time Scheduling Problem. CoRR abs\/2112.03255 (2021). arXiv:2112.03255 https:\/\/arxiv.org\/abs\/2112.03255"},{"key":"e_1_3_2_1_36_1","volume-title":"Workshop on Next Generation Real-Time Embedded Systems, NG-RES@HiPEAC 2020","volume":"13","author":"Simon Bertrand","year":"2020","unstructured":"Bertrand Simon , Joachim Falk , Nicole Megow , and J\u00fcrgen Teich . 2020 . Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice . In Workshop on Next Generation Real-Time Embedded Systems, NG-RES@HiPEAC 2020 , January 21, 2020, Bologna, Italy (OASICS , Vol. 77), Marko Bertogna and Federico Terraneo (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1--2: 13 . https:\/\/doi.org\/10.4230\/OASIcs.NG-RES.2020.2 10.4230\/OASIcs.NG-RES.2020.2 Bertrand Simon, Joachim Falk, Nicole Megow, and J\u00fcrgen Teich. 2020. Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. In Workshop on Next Generation Real-Time Embedded Systems, NG-RES@HiPEAC 2020, January 21, 2020, Bologna, Italy (OASICS, Vol. 77), Marko Bertogna and Federico Terraneo (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2:1--2:13. https:\/\/doi.org\/10.4230\/OASIcs.NG-RES.2020.2"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Philadelphia PA USA","acronym":"SPAA '22"},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":36,"alternative-id":["10.1145\/3490148.3538582","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538582","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}