Oliver Bodemer
IBM J. Res. Dev
We consider the setting of a device that obtains its energy from a battery and some regenerative source such as a solar cell. We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes, so as to minimize the energy recharge rate of the regenerative source. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We show that, using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is O (1)-competitive with respect to recharge rate. © 2009 Elsevier B.V. All rights reserved.
Oliver Bodemer
IBM J. Res. Dev
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Robert E. Donovan
INTERSPEECH - Eurospeech 2001