Energy-efficient Algorithms for Flow Time Minimization. Albers, S. & Fujiwara, H. ACM Trans. Algorithms, 2007.
Paper doi abstract bibtex We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.
@article{albers_energy-efficient_2007-1,
title = {Energy-efficient {Algorithms} for {Flow} {Time} {Minimization}},
volume = {3},
issn = {1549-6325},
url = {http://doi.acm.org/10.1145/1290672.1290686},
doi = {10.1145/1290672.1290686},
abstract = {We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.},
urldate = {2014-09-30TZ},
journal = {ACM Trans. Algorithms},
author = {Albers, S. and Fujiwara, H.},
year = {2007},
keywords = {Variable-speed processor, competitive analysis, dynamic programming, flow time, offline algorithms, online algorithms}
}
Downloads: 0
{"_id":"Ftz85wGPL8QmQH6wj","bibbaseid":"albers-fujiwara-energyefficientalgorithmsforflowtimeminimization-2007","downloads":0,"creationDate":"2016-12-19T20:50:58.275Z","title":"Energy-efficient Algorithms for Flow Time Minimization","author_short":["Albers, S.","Fujiwara, H."],"year":2007,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","title":"Energy-efficient Algorithms for Flow Time Minimization","volume":"3","issn":"1549-6325","url":"http://doi.acm.org/10.1145/1290672.1290686","doi":"10.1145/1290672.1290686","abstract":"We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.","urldate":"2014-09-30TZ","journal":"ACM Trans. Algorithms","author":[{"propositions":[],"lastnames":["Albers"],"firstnames":["S."],"suffixes":[]},{"propositions":[],"lastnames":["Fujiwara"],"firstnames":["H."],"suffixes":[]}],"year":"2007","keywords":"Variable-speed processor, competitive analysis, dynamic programming, flow time, offline algorithms, online algorithms","bibtex":"@article{albers_energy-efficient_2007-1,\n\ttitle = {Energy-efficient {Algorithms} for {Flow} {Time} {Minimization}},\n\tvolume = {3},\n\tissn = {1549-6325},\n\turl = {http://doi.acm.org/10.1145/1290672.1290686},\n\tdoi = {10.1145/1290672.1290686},\n\tabstract = {We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this article we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable-speed processor so as to minimize the total cost consisting of the energy consumption and the total flow time of all jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the article is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.},\n\turldate = {2014-09-30TZ},\n\tjournal = {ACM Trans. Algorithms},\n\tauthor = {Albers, S. and Fujiwara, H.},\n\tyear = {2007},\n\tkeywords = {Variable-speed processor, competitive analysis, dynamic programming, flow time, offline algorithms, online algorithms}\n}\n\n","author_short":["Albers, S.","Fujiwara, H."],"key":"albers_energy-efficient_2007-1","id":"albers_energy-efficient_2007-1","bibbaseid":"albers-fujiwara-energyefficientalgorithmsforflowtimeminimization-2007","role":"author","urls":{"Paper":"http://doi.acm.org/10.1145/1290672.1290686"},"keyword":["Variable-speed processor","competitive analysis","dynamic programming","flow time","offline algorithms","online algorithms"],"downloads":0,"html":""},"search_terms":["energy","efficient","algorithms","flow","time","minimization","albers","fujiwara"],"keywords":["variable-speed processor","competitive analysis","dynamic programming","flow time","offline algorithms","online algorithms"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}