Competitive Prediction-Aware Online Algorithms for Energy Generation Scheduling in Microgrids

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+O(frac1w)), 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.