Speed scaling with a solar cell

N. Bansal, H.L. Chan, K.R. Pruhs

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    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. 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 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.
    Original languageEnglish
    Title of host publicationAlgorithmic Aspects in Information and Management (4th International Conference, AAIM 2008, Shanghai, China, June 23-25, 2008. Proceedings)
    EditorsR. Fleischer, J. Xu
    Place of PublicationBerlin
    ISBN (Print)978-3-540-68865-5
    Publication statusPublished - 2008

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Speed scaling with a solar cell'. Together they form a unique fingerprint.

    Cite this