2013/02/15 by Mohammad M. Karbasioun, Karbasioun, Mohammad M., Gennady Shaikhet +5
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1302.3889
arxiv created 2013/02/15 · openalex publication_date 2013/02/15 · arxiv updated 2013/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \it 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.