Throughput Maximization in the Speed-Scaling Setting
Throughput Maximization in the Speed-Scaling Setting
复制标题
速度扩展设置中的吞吐量最大化
DOI：
10.4230/lipics.stacs.2014.53
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Vincent Chau
中科院分区：
文献类型：
--
作者：
Eric Angel;E. Bampis;Vincent Chau
为我们提供了一组N作业和一个可以动态变化其速度的单个处理器。 J_J的每个作业的特征是其处理要求（WORK）P_J，其发布日期R_J和其截止日期D_J。
我们还获得了能源E的预算，我们研究了最大化吞吐量的调度问题（即按时完成的工作数量）。虽然在多项式时间内解决了先发制的能量最小化问题[Yao等，focs'95]，但最大化吞吐量的问题的复杂性一直保持开放。我们通过提供动态的编程算法来部分回答这个问题，该算法解决了伪多项式时间中的问题。虽然我们的结果表明问题并不是NP坚强的，但在多项式时间内是否可以解决该问题仍然是一个具有挑战性的开放问题。我们的算法也可以适应解决问题的加权版本，其中每个作业都与权重W_J关联，目标是最大化按时完成的作业的权重之和。
We are given a set of n jobs and a single processor that can vary its speed dynamically. Each job J_j is characterized by its processing requirement (work) p_j, its release date r_j and its deadline d_j.
We are also given a budget of energy E and we study the scheduling problem of maximizing the throughput (i.e. the number of jobs that are completed on time). While the preemptive energy minimization problem has been solved in polynomial time [Yao et al., FOCS'95], the complexity of the problem of maximizing the throughput remained open until now. We answer partially this question by providing a dynamic programming algorithm that solves the problem in pseudo-polynomial time. While our result shows that the problem is not strongly NP-hard, the question of whether the problem can be solved in polynomial time remains a challenging open question. Our algorithm can also be adapted for solving the weighted version of the problem where every job is associated with a weight w_j and the objective is the maximization of the sum of the weights of the jobs that are completed on time.