Title: Deadline Energy Efficient Scheduling Problems
Speaker: Xin Han
Hong Kong U

Date: Tuesday , March 18, 2008
Time 1:30-2:30PM
Venue: Room 3530, HKUST


Abstract:
We initiate the study of dynamic speed scaling with 
sleep state in the bounded speed model, where a processor 
can vary its speed $s$ between 0 and some maximum $T$,
and the energy is consumed at the rate $s^\alpha + \sigma$ 
for some positive constants $\alpha > 1$ and $\sigma$.

To have zero energy usage, the processor can enter a 
sleep state, but wake-up requires energy. Under this model, 
we consider scheduling jobs with arbitrary work and 
deadlines arriving online, and the objective is to 
maximize the throughput, while using the smallest 
amount of energy.

Previous related work either considers sleep state with
the infinite speed model ($T = \infty$) in SODA03
or assumes no sleep state in SODA07; 
in these cases, online algorithms with optimal throughput 
and $O(1)$-competitive energy usage have been obtained.

This paper presents a new online algorithm to allow
speed scaling and sleep state.
For a speed bounded processor, this algorithm
is 4-competitive for throughput and $O(1)$-competitive for energy
(note that the throughput ratio is optimal);
in the infinite speed model, this algorithm
completes all jobs and has a better energy
ratio than the previous work in SODA03
We also study the underloaded case in the bounded speed model
and show another algorithm that is $(1+\epsilon)$-competitive
for throughput and $O(1)$-competitive for energy.