English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Speed Scaling of Tasks with Precedence Constraints

MPS-Authors
/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Pruhs, K., van Stee, R., & Uthaisombut, P. (2008). Speed Scaling of Tasks with Precedence Constraints. Theory of Computing Systems, 43(1), 67-80. doi:10.1007/s00224-007-9070-1.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1D05-C
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.