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.
|Title of host publication||e-Energy 2021 : Proceedings of the 2021 12th ACM International Conference on Future Energy Systems|
|Place of Publication||New York|
|Publisher||Association for Computing Machinery|
|Number of pages||11|
|Publication status||Published - Jun 2021|
|Event||12th ACM International Conference on Future Energy Systems (e-Energy 2021) - Virtual, Virtual, Online, Italy|
Duration: 28 Jun 2021 → 2 Jul 2021
|Conference||12th ACM International Conference on Future Energy Systems (e-Energy 2021)|
|Period||28/06/21 → 2/07/21|
Bibliographical noteThe work presented in this paper was supported in part by a Start-up Grant (Project No. 9380118) from City University of Hong Kong.
- Energy storage management
- peak-demand charge
- online competitive algorithms