Speed scaling for weighted flow time

N. Bansal, K.R. Pruhs, C. Stein

    Research output: Contribution to journalArticleAcademicpeer-review

    52 Citations (Scopus)
    277 Downloads (Pure)


    Intel's SpeedStep and AMD's PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of the processor to prolong battery life. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. We give an online speed scaling algorithm that is O(1)-competitive for the objective of weighted flow time plus energy. This algorithm also allows us to efficiently construct an O(1)-approximate schedule for minimizing weighted flow time subject to an energy constraint.
    Original languageEnglish
    Pages (from-to)1294-1308
    JournalSIAM Journal on Computing
    Issue number4
    Publication statusPublished - 2009


    Dive into the research topics of 'Speed scaling for weighted flow time'. Together they form a unique fingerprint.

    Cite this