Dual Techniques for Scheduling on a Machine with Varying Speed
Dual Techniques for Scheduling on a Machine with Varying Speed
复制标题
DOI：
10.1007/978-3-642-39206-1_63
复制
发表时间：
2012-11
期刊：
影响因子：
--
通讯作者：
Nicole Megow;José Verschae
中科院分区：
文献类型：
--
作者：
Nicole Megow;José Verschae
研究了变速机器上的排序问题。假设一个已知的速度函数，我们需要一个具有成本效益的调度解决方案。我们的主要结果是在这种设置下最小化总加权完成时间的多项式时间近似方案(PTAS)。这也意味着对于密切相关的调度问题的PTAS，以最小化广义全局成本函数，即问题。我们结果的关键是对众所周知的二维甘特图中的问题的重新解释：我们不是在时间维度上的标准调度方法，而是在权重维度上构建调度解决方案。这允许对实例和最优解进行结构简化，在此基础上，我们可以将对速度的关注推迟到动态规划框架中的成本评估。我们还考虑了一个动态问题变量，其中对速度的决策是问题的一部分，我们感兴趣的是调度成本和速度调整成本之间的权衡，这通常是能量消耗。我们观察到，最优顺序与能源消耗无关，并且问题可以简化为机器速度固定的设置，从而允许PTAS。此外，对于机器只能以固定数量的离散速度运行的NP-Hard问题变量，我们提供了一个完全多项式时间近似方案。最后，我们展示了我们的结果如何被用来在多台相同的平行机上获得带有交货日期的抢占式作业调度的一个-近似。
We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a polynomial-time approximation scheme (PTAS) for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions, that is, the problem. The key to our results is a reinterpretation of the problem within the well-knowntwo-dimensional Gantt chart: instead of the standard approach of scheduling in thetime dimension, we construct scheduling solutions in theweight dimension. This allows structural simplifications of the instance and optimal solutions, based on which we can defer the concern of speed to the evaluation of cost in a dynamic programming framework. We also consider a dynamic problem variant, where the decision upon the speed is part of the problem and we are interested in the trade-off between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide a fully polynomial-time approximation scheme for the NP-hard problem variant in which the machine can run only at a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines.