Power-aware scheduling for makespan and flow
The proliferation of mobile computing devices has made power management an important problem. One tool these devices have is the ability to conserve energy by operating more slowly. For example, many modern processors can reduce their clock speed, enabling them to operate at a lower voltage. Similarly, wireless devices can transmit more slowly, enabling them to use a coding scheme with lower rate and reduce their transmission power. Scheduling where the system can save energy by slowing down gives a tradeoff between energy consumption and schedule quality.
In this talk, I will summarize known results and describe offline algorithms for the bicriteria problems of minimizing energy and either makespan or total flow. The main result is a linear-time algorithm for uniprocessor makespan that computes all non-dominated solutions. An extension of that algorithm does the same for multiprocessors running equal-work jobs. The technique also gives an arbitrarily-good approximation for minimizing the total flow of equal-work jobs on a multiprocessor. Finally, I show that it is NP-hard to minimize makespan on a multiprocessor with arbitrary jobs and impossible to exactly minimize total flow on a uniprocessor with equal-work jobs.