Speed scaling for weighted flow time

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

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

    77 Citations (Scopus)


    In addition to the traditional goal of efficiently managing time and space, many computers now need to efficiently manage power usage. For example, 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. These policies must be online since the operating system does not in general have knowledge of the future. In current CMOS based processors, the speed satisfies the well known cube-root-rule, that the speed is approximately the cube root of the power [Mud01, BBS+00]. Thus, in this work, we make the standard generalization that the power is equal to speed to some power a = 1, where one should think of a as being approximately 3 [YDS95, BKP04]. Energy is power integrated over time. The operating system is faced with a dual objective optimization problem as it both wants to conserve energy, and optimize some Quality of Service (QoS) measure of the resulting schedule.
    Original languageEnglish
    Title of host publicationProceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07, New Orleans LA, USA, January 7-9, 2007)
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery, Inc
    ISBN (Print)978-0-898716-24-5
    Publication statusPublished - 2007


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

    Cite this