Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

Speed Scaling for Weighted Flow Time

2009; Society for Industrial and Applied Mathematics; Volume: 39; Issue: 4 Linguagem: Inglês

10.1137/08072125x

ISSN

1095-7111

Autores

Nikhil Bansal, Kirk Pruhs, Clifford Stein,

Tópico(s)

Parallel Computing and Optimization Techniques

Resumo

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.

Referência(s)