Throughput maximization for speed scaling with agreeable deadlines
Throughput maximization for speed scaling with agreeable deadlines
复制标题
DOI：
10.1007/s10951-015-0452-y
复制
发表时间：
2013-05
影响因子：
2
通讯作者：
Eric Angel;E. Bampis;Vincent Chau;Dimitrios Letsios
中科院分区：
文献类型：
--
作者：
Eric Angel;E. Bampis;Vincent Chau;Dimitrios Letsios
我们研究了以下的节能调度问题。给定一组作业，这些作业必须由单个处理器调度，处理器的速度可以动态变化。每个作业都以处理需求（工作）、发布日期和截止日期为特征。我们也有一个不能超过的能量预算，我们的目标是最大限度地提高吞吐量（即按时完成的工作数量）。我们证明了当所有作业具有相同的发布日期时，通过动态规划可以最优地解决问题，其中pi是作业加工需求的总和。对于具有可接受的截止日期的更一般的情况，可以对每个作业进行排序，因此，我们提出了一种实时运行的最优动态规划算法。此外，我们考虑加权情况，其中每个作业也与一个权重相关联，我们感兴趣的是最大化加权吞吐量（即按时完成的作业的总权重）。对于这种情况，我们表明，即使所有作业都具有相同的发布日期，问题在普通意义上也会变得困难，并且我们为合适的实例提出了伪多项式时间算法。
We study the following energy-efficient scheduling problem. We are given a set ofnjobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each jobis characterized by a processing requirement (work), a release date, and a deadline. We are also given a budget of energyEwhich must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming intime when all jobs have the same release date, wherePis the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every, it holds thatand, we propose an optimal dynamic programming algorithm which runs intime. In addition, we consider the weighted case where every jobis also associated with a weightand we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.