We study the problem of online peak-demand minimization under energy storage constraints. It is motivated by an increasingly popular scenario where large-load customers utilize energy storage to reduce the peak procurement from the grid, which accounts for up to $90\%$ of their electric bills. The problem is uniquely challenging due to (i) the coupling of online decisions across time imposed by the inventory constraints and (ii) the noncumulative nature of the peak procurement. In this paper, we develop an optimal online algorithm for the problem, attaining the best possible competitive ratio (CR) among all deterministic and randomized algorithms. We show that the optimal CR can be computed in polynomial time, by solving a linear number of linear-fractional problems. More importantly, we generalize our approach to develop an \emph{anytime-optimal} online algorithm that achieves the best possible CR at any epoch, given the inputs and online decisions so far. The algorithm retains the optimal worst-case performance and achieves adaptive average-case performance. Simulation results based on real-world traces show that, under typical settings, our algorithms improve peak reduction by over $19\%$ as compared to baseline alternatives.
翻译:我们研究了在能源储存限制下网上需求需求最小化的问题,其动因是日益流行的情景,即大型载荷客户利用能源储存来减少从电网中采购的峰值,占电费的90美元,这个问题具有独特的挑战性,因为(一) 由于库存限制而在不同时间将在线决定结合起来,以及(二) 高峰采购的非累积性。在本文件中,我们为问题开发了一种最佳在线算法,在所有确定性和随机化的算法中达到最佳的竞争比率(CR)。我们显示,最佳CR可以在多元时计算,解决线性偏向性问题的线性数量。更重要的是,我们推广了我们开发一个在线算法的方法,根据投入和在线决定,在任何地方都能达到最佳的CRR,在任何地方都达到最佳的CR;在本文中,我们开发了一种最佳的在线算法,保留了最坏的情况,并在所有确定性和随机化的算法中达到适应性的平均性表现。根据真实世界的痕迹,我们显示,在典型的环境中,我们的算法比基线上,比19美元改进了峰值。