Journal Article

Decrease and reset for power-down

Bein, Wolfgang, Kawahara, Jun, Ito, Hiro, Andro-Vasko, James, Kasahara, Shoji

2023

Overview

We consider the classical power management problem: There is a system or “device” which has two states—ON and OFF—and one has to develop a control algorithm for changing between these states as to minimize cost (energy or some other hybrid cost) when given a sequence of service requests. We analyze this problem in terms of online competitive analysis to obtain worst-case guarantees. Although an optimal 2-competitive algorithm exists, that algorithm does not result in good performance in many practical situations, especially in case the device is not used frequently. To take the frequency of device usage into account, we construct an algorithm based on the concept of “slackness degree”. Then by relaxing the worst-case competitive ratio of our online algorithm to 2+ε, where ε is an arbitrary small constant, we make the algorithm flexible to slackness. The algorithm thus automatically tunes itself to slackness degree and gives better performance than the optimal 2-competitive algorithm for real world inputs. In addition to worst-case competitive ratio analysis, a queueing model analysis is given and computer simulations are reported, confirming that the performance of the algorithm is high. We show how the approach can be generalized to a situation where the system has a number of intermediate states. Our model can be used to facilitate renewable energy integration into the electrical grid and we highlight that an online competitive approach can yield techniques for grid resiliency.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Competition / Control algorithms / Control theory / Cost analysis / Power management / Queueing / Renewable energy