Scheduling on a single machine under time-of-use electricity tariffs
Scheduling on a single machine under time-of-use electricity tariffs
复制标题
DOI：
10.1007/s10479-015-2003-5
复制
发表时间：
2015-09
影响因子：
4.8
通讯作者：
K. Fang;Nelson A. Uhan;Fu Zhao;J. Sutherland
中科院分区：
文献类型：
--
作者：
K. Fang;Nelson A. Uhan;Fu Zhao;J. Sutherland
我们考虑在一台机器上调度作业的问题，以最小化在按使用时间电费下处理这些作业的总电力成本。对于所有作业都具有任意功率需求且必须以单一均匀速度处理的匀速情况，我们证明了该问题的非抢占形式在一个常数因子内是不可逼近的，除非。另一方面，当所有工作都有相同的工作量，并且电价遵循所谓的金字塔结构时，我们证明了这个问题可以在多项式时间内得到解决。对于速度可扩展的情形，我们证明了该问题的非抢占形式是强NP-难的，其中可以在速度和功率需求之间权衡的情况下以任意的速度处理作业。我们还针对这种情况提出了不同的近似算法，并在随机生成的实例上测试了这些近似算法的计算性能。此外，对于等速和变速两种情况，我们证明了如何在多项式时间内计算抢占型问题的最优调度。
We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under time-of-use electricity tariffs. For the uniform-speed case, in which all jobs have arbitrary power demands and must be processed at a single uniform speed, we prove that the non-preemptive version of this problem is inapproximable within a constant factor unless. On the other hand, when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure, we show that this problem can be solved in polynomial time. For the speed-scalable case, in which jobs can be processed at an arbitrary speed with a trade-off between speed and power demand, we show that the non-preemptive version of the problem is strongly NP-hard. We also present different approximation algorithms for this case, and test the computational performance of these approximation algorithms on randomly generated instances. In addition, for both the uniform-speed and speed-scaling cases, we show how to compute optimal schedules for the preemptive version of the problem in polynomial time.