期刊
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷 37, 期 4, 页码 1266-1282出版社
SPRINGER
DOI: 10.1007/s10878-018-0352-0
关键词
Energy efficient scheduling; Speed scaling; Network flows; Convex programming
资金
- French Agency for Research under the DEFIS program TODO [ANR-09-EMER-010]
- GDR du CNRS, RO
- European Research Council [691672]
- German Research Foundation [AL464/9-1]
We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in O(nf(n)logU) time, where n is the number of jobs, U is the range of all possible values of processors' speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据