On multi-processor speed scaling with migration ?
We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. We study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor. We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time, given any convex non-decreasing power function. In contrast to a previously known strategy, our algorithm does not resort to linear programming. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. [15] for the single processor setting. Here we concentrate on power functions P(s)=s? P ( s ) = s ? , where s  is the processor speed and ?>1 ? > 1 is a constant.
energy efficiency offline algorithm online algorithm flow computation competitive analysis