论文标题
微电网上能源生成计划的竞争性预测在线算法
Competitive Prediction-Aware Online Algorithms for Energy Generation Scheduling in Microgrids
论文作者
论文摘要
在存在不确定的未来信息的情况下，在线决策在许多问题域中都很丰富。在微电网的能源发电计划的关键问题中，考虑到间歇性可再生生成和波动的需求，需要决定何时在廉价的启动成本和更高的按需外部网格之间切换能源供应。在不了解未来输入的情况下，竞争性的在线算法具有吸引力，因为它们为最佳离线解决方案提供了最佳保证。但是，实际上，在有限的时间窗口中通常可以预测未来的输入，例如，风向产生，并且可以利用以进一步提高在线算法的竞争力。在本文中，我们利用预测窗口中的信息结构来设计一种新颖的预测在线算法，用于微电网中的能源生成计划。对于这个重要问题，我们的算法达到了迄今为止的最佳竞争比率，最多是$ 3-2/（1+ \ Mathcal {o}（\ frac {1} {w}）），其中$ w $是预测窗口大小。我们还表征了竞争比率的非平凡的下限，并表明我们的算法的竞争比率仅为$ 9 \％$ $，当时有几个小时的预测。基于现实世界痕迹的仿真结果证实了我们的理论分析，并突出了我们新的预测意识设计的优势。
Online decision-making in the presence of uncertain future information is abundant in many problem domains. In the critical problem of energy generation scheduling for microgrids, one needs to decide when to switch energy supply between a cheaper local generator with startup cost and the costlier on-demand external grid, considering intermittent renewable generation and fluctuating demands. Without knowledge of future input, competitive online algorithms are appealing as they provide optimality guarantees against the optimal offline solution. In practice, however, future input, e.g., wind generation, is often predictable within a limited time window, and can be exploited to further improve the competitiveness of online algorithms. In this paper, we exploit the structure of information in the prediction window to design a novel prediction-aware online algorithm for energy generation scheduling in microgrids. Our algorithm achieves the best competitive ratio to date for this important problem, which is at most $3-2/(1+\mathcal{O}(\frac{1}{w})),$ where $w$ is the prediction window size. We also characterize a non-trivial lower bound of the competitive ratio and show that the competitive ratio of our algorithm is only $9\%$ away from the lower bound, when a few hours of prediction is available. Simulation results based on real-world traces corroborate our theoretical analysis and highlight the advantage of our new prediction-aware design.
