We consider a problem of supplying electricity to a set of N customers in a smart-grid framework. Each customer requires a certain amount of electrical energy which has to be supplied during the time interval [0, 1]. We assume that each demand has to be supplied without interruption, with possible duration between ℓ and r, which are given system parameters (ℓ ≤ r). At each moment of time, the power of the grid is the sum of all the consumption rates for the demands being supplied at that moment. Our goal is to find an assignment that minimizes the power peak - maximal power over [0, 1] - while satisfying all the demands. To do this first we find the lower bound of optimal power peak. We show that the problem depends on whether or not the pair ℓ, r belongs to a 'good' region G. If it does - then an optimal assignment almost perfectly 'fills' the rectangle time × power = [0, 1] × [0, A] with A being the sum of all the energy demands - thus achieving an optimal power peak A. Conversely, if ℓ, r do not belong to G, we identify the lower bound A > A on the optimal value of power peak and introduce a simple linear time algorithm that-almost-perfectly arranges all the demands in a rectangle [0, A/A] × [0, A] and show that it is asymptotically optimal.

Additional Metadata
Persistent URL dx.doi.org/10.1109/ICC.2013.6655233
Conference 2013 IEEE International Conference on Communications, ICC 2013
Karbasioun, M.M. (Mohammad M.), Shaikhet, G, Kranakis, E, & Lambadaris, I. (2013). Power strip packing of malleable demands in smart grid. Presented at the 2013 IEEE International Conference on Communications, ICC 2013. doi:10.1109/ICC.2013.6655233