{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:57:58Z","timestamp":1750309078431,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,11,1]],"date-time":"2005-11-01T00:00:00Z","timestamp":1130803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2005,11]]},"abstract":"<jats:p>\n            We present an algorithm for scheduling a set of nonrecurrent tasks (or jobs) with FIFO real-time constraints so as to minimize the total energy consumed when the tasks are performed on a dynamically variable voltage processor. Our algorithm runs in linear time and thus, in this case, is an improvement over the classical algorithm of Yao et al. It was inspired by considering the problem as a shortest-path problem. We also propose an algorithm to deal with the case where the processor has only a limited number of clock frequencies. This algorithm gives the optimum schedule with the minimum number of speed changes, which is important when the speed switching overhead cannot be neglected. All our algorithms are linear in the number of tasks if the arrivals and deadlines are sorted and otherwise need\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>N<\/jats:italic>\n            log\n            <jats:italic>N<\/jats:italic>\n            ) time. These complexities are shown to be the best possible. Finally, we extend our results to fluid tasks and to nonconvex cost functions.\n          <\/jats:p>","DOI":"10.1145\/1113830.1113838","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"907-933","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Shortest-path algorithms for real-time scheduling of FIFO tasks with minimal energy use"],"prefix":"10.1145","volume":"4","author":[{"given":"Bruno","family":"Gaujal","sequence":"first","affiliation":[{"name":"INRIA---Trio Team, Montbonnot, France"}]},{"given":"Nicolas","family":"Navet","sequence":"additional","affiliation":[{"name":"INRIA---Trio Team, Vandoeuvre-l\u00e8s-Nancy, France"}]},{"given":"Cormac","family":"Walsh","sequence":"additional","affiliation":[{"name":"INRIA---Maxplus Team, Le Chesnay Cedex, France"}]}],"member":"320","published-online":{"date-parts":[[2005,11]]},"reference":[{"volume-title":"Real-Time Systems Symposium. 95--105","year":"2001","author":"Aydin H., R., M.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","unstructured":"Boissonnat J. and Yvinec M. 1995. G\u00e9om\u00e9trie Algorithmique. Ediscience International.  Boissonnat J. and Yvinec M. 1995. G\u00e9om\u00e9trie Algorithmique. Ediscience International."},{"key":"e_1_2_1_3_1","unstructured":"Es Salhiene M. Fesquet L. and Renaudin M. 2003. Adaptation dynamique de la puissance des syst\u00e8mes embarqu\u00e9s: les syst\u00e8mes asynchrones surclassent les syst\u00e8mes synchrones. In journ\u00e9es d'\u00e9tudes Faible Tension---Faible Consommation (FTFC'03). 51--58.  Es Salhiene M. Fesquet L. and Renaudin M. 2003. Adaptation dynamique de la puissance des syst\u00e8mes embarqu\u00e9s: les syst\u00e8mes asynchrones surclassent les syst\u00e8mes synchrones. In journ\u00e9es d'\u00e9tudes Faible Tension---Faible Consommation (FTFC'03). 51--58."},{"volume-title":"IEEE Workshop on Power Management for Real-Time and Embedded Systems. 11--16","year":"2001","author":"Gruian F.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/288548.289105"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/280756.280894"},{"volume-title":"Scheduling a production line to minimize maximum tardiness. Tech. Rept","author":"Jackson J.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/378420.378429"},{"volume-title":"Workshop on Compiler and Operating Systems for Low-Power.","author":"Moss\u00e8 D.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379074"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.914596"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.309901"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Stankovic J. Spuri M. Ramamritham K. and Buttazo G. 1998. Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publ. Boston MA.   Stankovic J. Spuri M. Ramamritham K. and Buttazo G. 1998. Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms. Kluwer Academic Publ. Boston MA.","DOI":"10.1007\/978-1-4615-5535-3"},{"key":"e_1_2_1_15_1","unstructured":"Yao F. 2003. Complexity of the Yao Demers Shenker algorithm. Private communication.  Yao F. 2003. Complexity of the Yao Demers Shenker algorithm. Private communication."},{"volume-title":"Proceedings of lEEE Annual Foundations of Computer Science. 374--382","author":"Yao F.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/860176.860183"},{"volume-title":"Real-Time Systems Symposium. 235--245","author":"Zhang F.","key":"e_1_2_1_18_1"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113830.1113838","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1113830.1113838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:23Z","timestamp":1750286603000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1113830.1113838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["10.1145\/1113830.1113838"],"URL":"https:\/\/doi.org\/10.1145\/1113830.1113838","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2005,11]]},"assertion":[{"value":"2005-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}