期刊
ANNALS OF OPERATIONS RESEARCH
卷 238, 期 1-2, 页码 199-227出版社
SPRINGER
DOI: 10.1007/s10479-015-2003-5
关键词
Scheduling; Time-of-use tariff; Electricity cost; Dynamic speed scaling; Approximation algorithm
资金
- Div Of Chem, Bioeng, Env, & Transp Sys
- Directorate For Engineering [1512217] Funding Source: National Science Foundation
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 P = NP. 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据