Asymptotic convex optimization for packing random malleable demands in smart grid

We consider a problem of scheduling electric power demands in a smart-grid framework. Our model consists of n energy requirements {A_i, ℓ_i, r_i}ⁿ_i=1, needed to be scheduled in time interval [0,1]. Here Ai is the amount of energy, while ℓ_i and n are respectively, the left and right constraints on the length of the time period, during which A_i has to be supplied without interruption. The triples are assumed to be i.i.d. random vectors, with A distributed according to some general distribution G, and pair (ℓ, r) distributed uniformly in the region {0 ≤ ℓ_i ≤ r ≤ 1}. Our goal is to find a scheduling policy minimizing the power peak - maximal power over [0,1] - and/or the operational convex cost of the system while satisfying all the demands. The problem becomes very complicated as the number n of demands increases. To address this issue, we consider an asymptotic approach, in which the average amount of energy in each demand is inversely proportional to n, thus keeping the total scheduled amount stable. In this paper we first introduce lower bounds for both types of costs and then introduce a scheduling algorithm, asymptotically optimal in the sense that its cost converges to a corresponding lower bound almost surely, as n increases to infinity. Moreover, the algorithm is on-line (each demand is scheduled at the time its parameters become known) and has fully linear running time.