Offline preemptive scheduling of power demands to minimize peak power in smart grids

We consider the scheduling of flexible electric loads in a smart grid so as to minimize peak power demand. Specifically, we focus on the case when the loads are preemptable, their power requirement and duration are known in advance, and they have the same earliest start time and the same deadline. Our main results are (a) when power requests are scheduled preemptively, the peak power demand can be reduced by up to 50% relative to when these requests are scheduled non-preemptively, (b) preemptive scheduling to minimize peak power demand is NP-hard, (c) schedules with minimum peak power demand may be constructed using integer linear programming, and (d) the next-fit decreasing height heuristic may be used to quickly obtain schedules whose peak power demand is at most two times that of the optimal schedule when all jobs are preemptable and at most three times the optimal when only some jobs are preemptable. Experimental results for the integer linear program and the heuristic are also presented. Our experiments indicate a significant reduction in peak power when preemption is exploited. For example, on our data sets recharging collections of electric and plug-in hybrid vehicles without preemption required up to 26% more peak power than when this was done preemptively.