Speed scaling for weighted flow time

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

    Research output: Contribution to journalArticleAcademicpeer-review

    45 Citations (Scopus)
    170 Downloads (Pure)

    Abstract

    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
    Volume39
    Issue number4
    DOIs
    Publication statusPublished - 2009

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

    Cite this