Speed Scaling of Tasks with Precedence Constraints

We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem $Pm \mid prec \mid C_{max}$. We extend the standard 3-field notation and denote this problem as $Sm \mid prec, \, energy \mid C_{\max}$. We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem $Qm \mid prec \mid C_{max}$ to obtain a poly-log($m$)-approximation algorithm