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. We consider both uniform-speed and speed-scalable machine environments. For the uniform-speed case, we prove that this problem is strongly NP-hard, and in fact inapproximable within a constant factor, unless P = NP. We also propose an exact polynomial-time algorithm for this problem when all the jobs have the same workload and the electricity prices follow a so-called pyramidal structure. 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 this problem is strongly NP-hard. In addition, we present different approximation algorithms for this case and test the computational performance of these approximation algorithms on randomly generated instances.
Citation
Annals of Operations Research, available online first, September 2015. DOI: 10.1007/s10479-015-2003-5