{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:25:22Z","timestamp":1761895522571,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"publisher","award":["17171 and ANR"],"award-info":[{"award-number":["17171 and ANR"]}],"id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000089","name":"Office of International Science and Engineering","doi-asserted-by":"publisher","award":["OISE-0340752, CCR-0208856 and CCF-0729071"],"award-info":[{"award-number":["OISE-0340752, CCR-0208856 and CCF-0729071"]}],"id":[{"id":"10.13039\/100000089","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining a satisfactory level of performance. One common method for saving energy is to simply suspend the system during idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the article, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy\n            <jats:italic>L<\/jats:italic>\n            to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5<\/jats:sup>\n            )-time algorithm. In addition we provide an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            )-time algorithm for computing the minimum energy schedule when all jobs have unit length.\n          <\/jats:p>","DOI":"10.1145\/2229163.2229170","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:41:09Z","timestamp":1343313669000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Polynomial-time algorithms for minimum energy scheduling"],"prefix":"10.1145","volume":"8","author":[{"given":"Philippe","family":"Baptiste","sequence":"first","affiliation":[{"name":"CNRS, Ecole Polytechnique, France"}]},{"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[{"name":"CNRS, Universit\u00e9 Pierre et Marie Curie, France"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.50"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109598"},{"key":"e_1_2_1_3_1","volume-title":"Scheduling Algorithms","author":"Brucker P.","unstructured":"Brucker , P. 2004. Scheduling Algorithms 4 th Ed., Springer . Brucker, P. 2004. Scheduling Algorithms 4th Ed., Springer.","edition":"4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.010"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248385"},{"key":"e_1_2_1_6_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067324"},{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE). 117","author":"Irani S.","key":"e_1_2_1_8_1","unstructured":"Irani , S. , Shukla , S. , and Gupta , R . 2002. Competitive analysis of dynamic power management strategies for systems with multiple power savings states . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). 117 . Irani, S., Shukla, S., and Gupta, R. 2002. Competitive analysis of dynamic power management strategies for systems with multiple power savings states. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE). 117."},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 37--46","author":"Irani S.","key":"e_1_2_1_9_1","unstructured":"Irani , S. , Shukla , S. , and Gupta , R . 2003a. Algorithms for power savings . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 37--46 . Irani, S., Shukla, S., and Gupta, R. 2003a. Algorithms for power savings. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 37--46."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860180"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/050629434"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:52Z","timestamp":1750236532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229170"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229170","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}