We consider a problem of scheduling electric power demands in a smart-grid framework. Our model consists of n energy requirements {Ai, ℓi, ri}n 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 Ai 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.

Additional Metadata
Persistent URL dx.doi.org/10.1109/ICC.2013.6654919
Conference 2013 IEEE International Conference on Communications, ICC 2013
Citation
Shaikhet, G, Karbasioun, M.M. (Mohammad M.), Kranakis, E, & Lambadaris, I. (2013). Asymptotic convex optimization for packing random malleable demands in smart grid. Presented at the 2013 IEEE International Conference on Communications, ICC 2013. doi:10.1109/ICC.2013.6654919