  


Scheduling on a single machine under timeofuse electricity tariffs
Kan Fang (zjumathgmail.com) Abstract: We consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under timeofuse electricity tariffs. We consider both uniformspeed and speedscalable machine environments. For the uniformspeed case, we prove that this problem is strongly NPhard, and in fact inapproximable within a constant factor, unless P = NP. We also propose an exact polynomialtime algorithm for this problem when all the jobs have the same workload and the electricity prices follow a socalled pyramidal structure. For the speedscalable case, in which jobs can be processed at an arbitrary speed with a tradeoff between speed and power demand, we show that this problem is strongly NPhard. 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; timeofuse 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/s1047901520035 Download: Entry Submitted: 04/10/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  