Energy-conscious Single Machine Scheduling Problem Under Time-of-use Electricity Tariffs

Energy shortage and environmental problems have become a bottleneck for social growth in many countries.Electricity is one of the main types of energy used in manufacturing industry(Park et al.,2009).The uneven electricity demand brings about prohibitive costs and large CO2 emissions for electricity providers.To deal with this issue,electricity providers usually use time-of-use(TOU)tariffs,in which electricity prices may vary from hour to hour throughout a day,to reshape the demand curve so as to reduce the on-peak load.Additionally,TOU tariffs scheme also provides an opportunity for electricity users to save electricity costs(Fang et al.,2014).This paper addresses an energy-conscious single machine scheduling problem under time-of-use.The key issue is to assign a set of jobs to available time periods with different electricity prices so as to minimize the total electricity cost required for processing the jobs.The main contribution of this work is two-fold.First,a new continuous-time mixed-integer linear programming(MILP)model is proposed for the problem.Second,an efficient greedy insertion heuristic is developed.In the proposed heuristic,the jobs are inserted into the available time periods one after another in non-increasing order of their electricity consumption rates and each job is inserted into the time period(s)with minimum electricity cost.A real-life case study from a Chinese company reveals that the total electricity cost can be reduced by about 30% with the proposed algorithm.Computational experiment on randomly generated instances also demonstrates that our algorithm can yield high-quality solutions with low electricity costs within dozens of seconds for large-scale single machine scheduling problems with 5000 jobs.The algorithm can be applied by production managers to scheduling jobs on a single machine under TOU electricity tariffs to save electricity costs.