.png){kind=icon}
.png){kind=icon}
Return
A Note on Multiprocessor Speed Scaling with Precedence Constraints
.png){kind=icon}
PRE
AI
DOI：10.1145/2612669.2612672.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the problem of scheduling a set of jobs, under precedence constraints, on a set of speed scalable parallel processors. The goal is to minimize the makespan of the schedule, i.e. the time at which the last job finishes its execution, without violating a given energy budget. This situation finds applications in computer devices whose lifetime depends on a limited battery efficiency. In order to handle the energy consumption we use the energy model introduced in [Yao et al., FOCS'95], which captures the intuitive idea that the higher is the processor's speed the higher is the energy consumption. We propose a (2- 1/m)- approximation algorithm improving the best known poly-log(m)-approximation algorithm for the problem [Pruhs et al., TOCS 2008], where m is the number of the processors. We also extend the simple idea used for the above problem, in order to propose a generalized framework that finds applications to other scheduling problems in the speed scaling setting.
Keywords:
Speed scaling
Scheduling
Approximation algorithms
Convex programming
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
P
IF:
0
Papers:
1.8K
Citations:
0