Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 3, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1290672.1290686
Keywords
Variable-speed processor; flow time; online algorithms; competitive analysis; offline algorithms; dynamic programming
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available