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.
Annals of Operations Research, available online first, September 2015. DOI: 10.1007/s10479-015-2003-5