hide
Free keywords:
-
Abstract:
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.
