Optimal Online Algorithms for Peak-Demand Reduction Maximization with Energy Storage

We consider an emerging scenario where large-load customers employ energy storage (e.g., fuel cells) to reduce the peak procurement from the grid, which accounts for up to 90% of their electricity bills. We focus on maximizing the peak-demand reduction, which directly captures the economic benefits of using energy storage for the purpose. While the problem is easy to solve under the (ideal) offline setting where the electricity demands are known beforehand, it turns into a challenging online decision-making problem under the more practical online setting, where the demands are revealed sequentially but one has to make irrevocable discharging decisions without knowing future demands. In this paper, we develop an optimal online algorithm for the problem that achieves the best possible competitive ratio (CR) among all (deterministic and randomized) online algorithms. We solve a linear number of linear-fractional problems to find the best CR in polynomial time. We then extend our algorithm to an adaptive one with improved average-case performance and the same optimal worst-case performance. Simulation results based on real-world traces show that, under typical settings, our algorithms achieve up to 81% peak reduction attained by the optimal offline solution and 20% more peak reduction than baseline alternatives.