Optimization Online


Scheduling on a single machine under time-of-use electricity tariffs

Kan Fang (zjumath***at***gmail.com)
Nelson A. Uhan (uhan***at***usna.edu)
Fu Zhao (fzhao***at***purdue.edu)
John W. Sutherland (jwsuther***at***purdue.edu)

Abstract: 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.

Keywords: scheduling; time-of-use tariff; electricity cost; dynamic speed scaling; approxima- tion algorithm

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization

Citation: Annals of Operations Research, available online first, September 2015. DOI: 10.1007/s10479-015-2003-5


Entry Submitted: 04/10/2014
Entry Accepted: 04/10/2014
Entry Last Modified: 10/17/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society