1 Introduction

1.1 The power-down problem

We consider a device, which has two power states, ON and OFF, and a number of intermediate states \(\mathcal {I}=\{\text {INT}_{j} | j=1, \ldots , \ell \}\). For example, such a device could be a cell phone, a workstation, an HVAC unit, or a power generation system. If \(\mathcal {I} = \varnothing\), the device is called a two-state device, else it is called an \(\ell + 2\) state device, i.e. ON/OFF plus the number of intermediate states in \(\mathcal {I}\). In the OFF-state the device consumes zero amount of energy (or amount of resource in the case of a power generation system) and the running cost of the device in the ON state is proportional to the time of usage. The intermediate states serve as sleep states, where the running cost is also proportional to time, but at only smaller cost \(r_j \in (0,1)\) per time unit. Thus the cost to remain in \(\text {INT}_{j}\) for time \(\Delta t\) is \(\Delta t \cdot r_i\). There is no cost to switch from ON to OFF or any of the intermediate states. But a fixed power cost of \(a>0\) occurs to switch to ON from OFF and a smaller cost \(a_j \in (0,1)\) occurs to switch to ON from any of the intermediate states \(\text {INT}_{j}\). Table 1 summarizes this system. In this paper we will mainly focus on two- and three-state systems.

Table 1 Costs when running and for switching
Full size table

At any time the device may be in any state but it must be turned to the ON state when service is requested. More precisely, for some \(n \in \mathbb {N}\), let \(t_{1}^{b}, \ldots t_{n}^{b}\) and \(t_{1}^{e}, \ldots t_{n}^{e}\) be non-negative real values with \(t_{1}^{b}< t_{1}^{e}< t_{2}^{b}< t_{2}^{e} \ldots< t_{n}^{b} < t_{n}^{e}\) that represent requests for service \(\mathcal {S}_i\) between begin of service times \(t_{i}^{b}\) and end of the service times \(t_{i}^{e}\) (\(i=1,\ldots ,n\)) which means that at time \(t_{i}^{b}\) the state of the device must be in ON until time \(t_{i}^{e}\). Between requests the device can remain in the ON state, go to the OFF state or any of the intermediate states. If the device goes to an intermediate state for a certain duration, we say it is standing by and refer to this duration as the standby time. The duration from the end of service \(\mathcal {S}_i\) to the beginning of service \(\mathcal {S}_{i+1}\) (i.e. \(t_{i+1}^{b} - t_{i}^{e}\)) is called the waiting time. Clearly, if the waiting time is small, rather than switching off, it may be better stand by in anticipation \(\mathcal {S}_{i+1}\).

It is not known in advance when and how many service requests occur, thus an algorithm has to decide whether to switch states without knowing what the next request will be. Such an algorithm is called online; an online algorithm makes its decisions without knowledge of future input. This is in contrast to on offline algorithm which operates under full knowledge of the entire request sequence in advance. We say that an online algorithm \(\mathcal {A}\) has competitive ratio C for a given request sequence \(\sigma\), if

$$\begin{aligned} {{ cost}}_\mathcal{{A}}(\sigma ) \le C \cdot {{ cost}}_{{{ opt}}}(\sigma ) \end{aligned}$$

where \({{ cost}}_\mathcal{{A}}(\sigma )\) is the cost of \(\mathcal {A}\) to serve \(\sigma\) and \({{ cost}}_{{{ opt}}}(\sigma )\) is the cost of the optimal offline algorithm on that same request sequence. (As mentioned above, for the power-down problem \(\sigma = t_{1}^{b}< t_{1}^{e}< t_{2}^{b}< t_{2}^{e} \ldots< t_{n}^{b} < t_{n}^{e}\) for some n.) If the inequality holds for all possible input sequences, then we say that the online algorithm is C-competitive; furthermore the competitive ratio for a given algorithm \(\mathcal {A}\) is defined as the smallest such C possible. (For a comprehensive overview over online competitive analysis see [14].) The goal is thus to find an online algorithm with competitive ratio best possible, i.e. an online algorithm with the smallest competitive ratio. We refer to such an algorithm as an ‘optimal worst-case competitive ratio algorithm’ denoted here by \(\mathcal {OWCR}\) with the stipulation that we break ties arbitrarily if more that one optimal online algorithm exists.

Under competitive analysis, for the two-state problem, an optimal online algorithm \(\mathcal {OWCR}\) is well known for this problem [18, 24, 25]: \(\mathcal {OWCR}\) switches to ON at a service request. After the service, \(\mathcal {OWCR}\) remains on to stand by for time a. This means that if another service is requested within the standby period, \(\mathcal {OWCR}\) simply remains in state ON. Only if the waiting time is larger than a, will \(\mathcal {OWCR}\) go to OFF after a standby time of a. Algorithm \(\mathcal {OWCR}\) is 2-competitive, which is optimal.

This situation is analogous to the noted ski rental problem [25]. In the ski rental problem a “friend” invites an invitee to go skiing, one can rent skis at cost $r or purchase them at cost $\(a= k\cdot \$ r\), for some \(k \in \mathbb {N}\). Unlike the inviter, the invitee does not know how often they will be invited. Thus the invitee has to decide how often to rent and when to buy. It is easy to see that the best competitive ratio of the invitee cost versus the inviter cost achievable by any online algorithm for the ski rental problem is 2; the strategy is to rent k times before buying. The ski rental problem is analogous to the two-state power-down problem in the following way. Both problems are about when to commit to a higher cost in anticipation of future savings. In the ski-rental problem, this commitment is when buying skis, in the power-down problem the commitment is to accept a (large one-time) switching-on cost next when the system is switched off.

Though \(\mathcal {OWCR}\) has the best possible worst-case competitive ratio this does not mean that it will perform well in most situations. For example, if the service requests \(\mathcal {S}_i\) are infinitesimally short and all \(\mathcal {S}_i\) are spaced far apart, then \(\mathcal {OWCR}\) remains in the ON state for an extra a units for each service. This is quite wasteful as the cost for \(\mathcal {OWCR}\) is 2a (the switching cost and running cost are both a), whereas the optimal offline algorithm “OPT” turns off immediately after each service is finished. OPT pays only the switching cost a (and the infinitesimal running cost). Although \(\mathcal {OWCR}\) does not seem clever at all, under worst-case competitive analysis this algorithm has the best performance, namely a ratio of 2.

Basic concept of our algorithm Since \(\mathcal {OWCR}\) is optimal it appears there is no improvement possible, unless we leave the online competitive model altogether. This is undesirable as described above. Our idea, instead, is to consider algorithms with competitive ratio only worse from best by a small positive constant \(\varepsilon\): such an approach allows for the design of an entire spectrum of algorithms with “almost-best” competitiveness. We call such algorithms \(\varepsilon\)-OPT. In this paper then we present such \(\varepsilon\)-OPT algorithms—algorithms which maintain close to an optimally competitive ratio while additionally performing better for a multitude of instances. The type of algorithms we design react adaptively to fluctuations: they gradually decrease the duration of the standby time when waiting times are large (in a two state system this means longer than a) until the waiting time becomes short again (a value within a for two-states) at which point standby times are reset. Informally this can be described as “decrease and reset” – standby times are successively tapered down in an “off peak” situation when the frequency of requests is low and then reset if the frequency goes up.

We introduce a parameter called “slackness degree,” which represents the frequency of serviced requests and we construct \(\varepsilon\)-OPT algorithms, which have superior competitiveness (i.e. lower than \(2 + \varepsilon\)) in the presence of slackness. The competitive ratio improves when the frequency of requests within any time period is small—something very desirable in practice, while maintaining a guarantee of competitiveness within \(\varepsilon\) of best possible competitiveness in the worst-case. We emphasize that the algorithm is online and, as such, need not know the actual slackness degree.

1.2 Related algorithmic work

As mentioned above, the tight optimal competitive ratio of the two-state power-down problem is 2; this has been observed in various contexts, see [22, 24, 25, 32]. In that sense the problem is settled and therefore there are no further results. When a probability distribution for the service requests is given, the expected cost is minimized; these algorithms are called probability-based. Such an algorithm utilizes knowledge of the probability distribution and the competitive ratio improves to \(e/(e-1) \approx 1.582\); this bound is tight for probability-based algorithms [22,23,24]. It is important to note that such an algorithm is not defined for arbitrary data and an algorithm designed for a specific distribution will perform poorly for arbitrary request sequences. In contrast, or algorithm performs with close to optimal competitiveness while performing well for a range of sequences which we parameterize using a slackness parameter.

There is a body of work regarding multiple intermediate states as declared in Table 1. Irani et al. [21] show that the ski-rental approach for two state systems can be generalized to multiple states both in the deterministic case using a “lower envelope” techniques resulting in a 2-competitive algorithms as well as in the probability-based situation with tight competitiveness \(e/(e-1)\).

There are customized algorithms for a specific number of intermediate states, see our papers [7] for systems with one extra state, i.e. three-state systems, [8] for systems with finitely many but few states, [6] for systems with a continuous number of states, and our survey paper [9]. More generally, Augustine et al. [10, 11] give an algorithm that, given a system, produces a deterministic strategy whose competitive ratio is arbitrarily close to optimal.

We note that online competitive algorithms for power-down are related to earlier work on “speed-scaling” of CPUs [4, 22]. Furthermore, there is a body of work from the embedded systems community where a number of adaptive strategies were proposed in the literature. In particular, Chung et al. [15] address multiple-state systems in this way.

1.3 Electric power systems and renewable energy management

Power-down mechanisms are common in electronic control, such as power optimization for hand-held devices, laptop computers, work stations and data centers [2, 3, 30, 33]. But the model is also useful to handle power-down phenomena in a future electrical grid, which predominantly relies on renewable energy, see our paper [12] for a survey. In the traditional energy grid, when renewables produce a surplus of energy, such surplus generally does not affect the operation of traditional power plants. Instead, renewables are throttled down or the surplus is simply ignored. But in the future when the majority of power is generated by renewables this is not tenable. Rather, traditional power plant output needs be throttled down or switched off in response to less predictable renewable supplies. Online competitive models have the advantage that little statistical insight is needed. We note that online competitive algorithms were developed to model an emerging internet where requests are not driven by a well-defined distribution but requests which are largely unpredictable. Similarly energy management in a distributed smart grid will benefit from models which are rooted in such online competitive models; for example, network design has been studied extensively in the online competitive setting; see Meyerson [29] for work on dynamic network design.

It could be argued that a game-theoretic approach which assumes an omniscient adversary may not be so realistic for modeling the grid, however this kind of modeling gives performance guarantees in the absence of reliable forecasting. For example, climate scientists have noted unusual weather patterns related to a change in the Arctic Oscillation (OA) and North Atlantic Oscillation (NAO) [19]. Recently, unprecedented winter storms across Texas in February 2021 caused wide-spread power outages [40]. See also Maimó-Far et al. [26] for unpredictability issues around renewables. In order to guarantee a resilient grid, worst-case assumptions must be taken into account.

There is a large body of work on the unit commitment problem in electrical power production, see Padhy [31] for a bibliography, and Huang, Pardalos and Zhang [20] for a comprehensive review of unit commitment problems in electrical power generation. The introduction of renewables has significantly increased the underlying uncertainty in the system, an aspect which has been recognized increasingly in the literature, see Tahanan et al. [1, 36] for a comprehensive survey on recent work and algorithmic techniques. A recent survey on integrating renewables and the unique challenges involved is in [34]. Ben-Tal, Bertsimas, and Brown give models which provide some measure of robustness against distributional variation [13]. However, renewable energy management can benefit from online competitive modeling where algorithms allocate resources in hard to predict circumstances and where reliable distributional assumptions cannot be made.

Budischak et al. [16], for example, model many combinations of renewable electricity sources (inland wind, offshore wind, and photovoltaics) with electrochemical storage (batteries and fuel cells), incorporated into a large grid system. One of the components available to manage variable generation is (limited) fossil backup where conventional power is cycled as needed to fill gaps. More precisely, cycling refers to the operation of electric generating units at varying load levels, including on/off, load following, and minimum load operation, in response to changes in system load [28]. There are technical limits and costs associated with cycling conventional power plants. Van den Bergh and Delarue [38] point out the importance of including full cycling costs in unit commitment scheduling. They also discuss the different ways of quantifying various types of cycling costs, such as direct start costs, indirect start costs, forced outage costs, ramping costs and efficiency costs. Very recently, de Mars et al. [17] have estimated the impact of variable renewable energy on base-load cycling in the UK and it is expected that such impact will only be larger in the future. As a result there are numerous studies on the costs of cycling itself [27, 35, 38, 41], including Integrated Solar Combined Cycle Power Plants [5]. We also mention a recent study conducted at Sandia National Laboratories, which described implications of power plant idling and cycling on water use intensity [37]

Cycling costs can be avoided by the obvious method of not cycling a unit and that may include staying on at a loss and we are modeling this tradeoff by abstracting the problem as a power-down problem in the online competitive setting. While we are mainly concerned with decrease and reset techniques in the two-state situation (Sects. 3 and 4) our method can be adapted to situations where there is partial load operation [38], i.e. where there are “intermediate states” other than on/off (Sect. 5).

1.4 Organization of the paper

Though we have described the general problem earlier in the introduction we give a concise statement of the two-state problem (and further notations) in Sect. 2. Section 3 presents the decrease and reset algorithm and gives the concept of slackness degree. We study the competitive ratio under this concept. In Sect. 4 we analyze the cost performance of the decrease and reset algorithm using queueing theory. After deriving the model, we run the model with specific parameters. Furthermore, we report results of experiments conducted using Monte Carlo simulation in order to validate the results obtained through the analysis. We also compare our approach to a number of simplified reset algorithms. The decrease and reset concept can be generalized to systems with more than two states, i.e. systems with intermediate states. We discuss the use of the decrease and reset approach in a three state system in Sect. 5. We conclude and give further outlook in Sect. 6.

2 Problem statement

We now define our system in detail. In this paper we consider a device or system with infinite capacity that has two states, an ON-state and an OFF-state (simply ON and OFF), for which we design a control algorithm for changing between ON and OFF.

Let \(t_{1}^b,\ldots , t_{n}^b,t_{1}^e,\ldots , t_{n}^e\) be non-negative real values that represent the service times \(t\_^b\) and end-of-service times \(t\_^e\) for n requests and which satisfy \(0 \le t_{1}^b< t_{1}^e< t_{2}^b< t_{2}^e< \cdots< t_{n}^b < t_{n}^e\). The input for this problem is given as \(\sigma = \langle (t_{1}^s, t_{1}^e), (t_{2}^s,t_{2}^e),\ldots ,(t_{n}^s, t_{n}^e) \rangle\). For this input, the device must be kept ON between times \(t_{i}^s\) and \(t_{i}^e\) for each \(i = 1,\ldots ,n\).

The state of the device can be switched at an arbitrary time. There is no cost for switching from ON to OFF, while there is a switching cost \(a\,(> 0)\) when switching from OFF to ON. For keeping the ON-state, it takes running cost of one unit per unit time.

The strategy of the optimal offline algorithm (OPT) for this problem is clear: If the period between the current request and next one is less than a, the device is kept ON. Otherwise, it is turned off immediately. Therefore OPT’s total cost for the input \(\sigma = \langle (t_{1}^b, t_{1}^e), (t_{2}^b, t_{2}^e),\ldots ,(t_{n}^b, t_{n}^e) \rangle\) is \(a + \sum _{i=1}^n (t_{i}^e - t_{i}^b) + \sum _{i=1}^{n-1} \min \{t_{i+1}^b-t_{i}^e, a\}\).

For some i-th request \((t_i^s, t_i^e)\), we consider the sum of the i-th running cost and the next (\(i+1\))-th switching cost. Let ALG be any algorithm. Let u be the period between the end of the request and the start of the next request (i.e., \(u = t_{i+1}^s - t_i^e\)). Then the optimal offline algorithm pays \(t_i^e - t_i^s + \min \{u, a\}\). If ALG turns the device off after \(v\,(< u)\) standby time, the cost is \(t_i^e - t_i^s + v + a\). Otherwise, it must pay \(t_i^e - t_i^s + u\). In each case, the smaller \(t_i^e - t_i^s\) is, the worse the competitive ratio becomes. Therefore, from the standpoint of competitive analysis, it is enough to consider that usage times of the device (i.e., \(t_i^e - t_i^s\) for each i) are tiny. We call this the short-job assumption. On the basis of the above discussion, we redefine this problem as follows:

Let \(t_1, \ldots , t_n\) be non-negative real values satisfying \(0 \le t_1< \cdots < t_n\) representing the time of service of the device for n requests. An input is given as \(\sigma = \langle t_1, t_2, \ldots , t_n \rangle\). We do nothing if the state is ON at \(t_i\) (\(i = 1,\ldots , n\)), and should turn a device ON if it is OFF at that time.

For a given input \(\sigma = \langle t_1,t_2, \ldots , t_n \rangle\) (n may be \(\infty\)), the action of an algorithm is determined by a sequence \(\langle w_1,w_2, \ldots , w_n \rangle\), where \(w_i\) is standby time after ith request is leaving. In other words, the problem is how to determine \(w_i\) from \(\langle t_1,t_2,\ldots ,t_i \rangle\). For each \(i = 2,\ldots ,n\), let \(u_{i} = t_{i} - t_{i-1}\) be an idle period. OPT’s cost for this redefined problem is \(\text {OPT}(\sigma ) = a + \sum _{i=1}^{n-1} \min \{t_{i+1}-t_{i}, a\}\). We denote ALG’s cost for input \(\sigma\) by \(\text {ALG}(\sigma )\) and the competitive ratio of ALG for \(\sigma\) by \(\mathcal {R}_{\text { ALG}}(\sigma ) = \text {ALG}(\sigma )/\text {OPT}(\sigma )\). Let \(\Sigma\) be the set of whole inputs \(\sigma\). For a subset \(\Sigma ' \subseteq \Sigma\), we define \(\mathcal {R}_{\text { ALG}}(\Sigma ')\) = \(\sup _{\sigma \in \Sigma '}\mathcal {R}_{\text { ALG}}(\sigma )\). And we represent \(\mathcal {R}_{\text { ALG}}\) = \(\mathcal {R}_{\text { ALG}}(\Sigma )\), which is the (worst-case) competitive ratio of ALG.

3 The decrease and rest approach

3.1 Decrease and reset algorithm (DRA)

We propose an algorithm which decreases the standby time gradually when the frequency of the device usage becomes low.

Decrease and Reset Algorithm (DRA)

Let \(x_1,x_2,\ldots ,\) be an infinite non-increasing sequence of non-negative values. In DRA, \(w_i = x_{f(i)}\) such that

$$\begin{aligned} f(i) = \left\{ \begin{array}{ll} f(i-1) + 1 &{} \quad \text {if}\ u_{i} \ge a\ \text {and}\ i\ne 1, \\ 1 &{} \quad \text {otherwise}.\\ \end{array} \right. \end{aligned}$$

If \(x_i=a\) for all i, DRA is equivalent to OWCR. Setting \(x_i\) be larger than a is clearly wasteful, and hence we consider cases such that \(x_i \le a\) for all \(i=1,2,\ldots\). From a simple observation we see that \(x_1\) gives a lower bound of \(\mathcal {R}_{\text { DRA}}\):

Observation 1

\(\mathcal {R}_{\text { DRA}} \ge 1+ a/x_1\).

Proof

Let m be an integer. For an input \(\sigma =\langle x_1,2x_1,\ldots ,mx_1 \rangle\), OPT’s total cost is \(a + (m-1)x_1\) and DRA’s total cost is \(m(a+x_1)\). Thus the competitive ratio of them is the following:

$$\begin{aligned} \mathcal {R}_{\text { DRA}} \ge \mathcal {R}_{\text { DRA}}(\sigma ) = \frac{m(a+x_1)}{a+(m-1)x_1} {\mathop {\rightarrow }\limits ^{(m \rightarrow \infty )}} 1+\frac{a}{x_1}. \end{aligned}$$

□

From this observation, it follows that \(x_1\) cannot be much smaller than a, otherwise \(\mathcal {R}_{\text { DRA}}\) becomes very large. In other words, if the difference between a and \(x_1\) is small, the effect to \(\mathcal {R}_{\text { DRA}}\) is not so large. Thus we relax the worst-case competitive ratio from 2 to \(2+\varepsilon\) for small \(\varepsilon > 0\), i.e., we let \(x_1 = a/(1+\varepsilon )\).

The above observation is easily extended to the other values \(x_2,x_3,\ldots ,\) as follows.

Observation 2

For any integer k,

$$\begin{aligned} \mathcal {R}_{\text { DRA}} \ge \frac{ka + \sum _{i=1}^k x_i}{(k-1)a + x_{k}}. \end{aligned}$$

Proof

Let m be an integer and \(t_1,t_2,\ldots ,t_{mk}\) be a sequence such that

\(t_1 = a\) and if \(i = 1 \ \text {mod}\ k\) then \(t_i = t_{i-1}+ x_k\), otherwise \(t_i = t_{i-1} + a\). For input \(\sigma =\langle t_1,t_2,\ldots ,t_{mk} \rangle\), DRA sets \(w_i = x_{g(i)}\) for all i, where \(g(i) = ((i - 1)\ \text {mod}\ k) + 1\). OPT’s total cost is \(a+m(k-1)a + (m-1)x_{k}\) and DRA’s total cost is \(mka + m\sum _{i=1}^k x_i\). Thus the competitive ratio of them is the following:

$$\begin{aligned} \mathcal {R}_{\text { DRA}} \ge \mathcal {R}_{\text { DRA}}(\sigma ) = \frac{mka + m\sum _{i=1}^k x_i}{a+m(k-1)a + (m-1)x_{k}} {\mathop {\rightarrow }\limits ^{(m \rightarrow \infty )}} \frac{ka + \sum _{i=1}^k x_i}{(k-1)a + x_{k}} . \end{aligned}$$

So this observation is satisfied. □

Our upper bound of the competitive ratio is \(2+\varepsilon\), and thus, the following inequalities must be satisfied for every \(k=1,2,\ldots\):

$$\begin{aligned} \frac{ka + \sum _{i=1}^k x_i}{(k-1)a + x_{k}} \le 2 + \varepsilon . \end{aligned}$$

Solving this equation for \(x_k\), we have

$$\begin{aligned} x_{k} \ge \frac{1}{1+\varepsilon }\left( (2+\varepsilon )a + \sum _{i=1}^{k-1} x_i \right) - ka. \end{aligned}$$

By elementary induction, we obtain

$$\begin{aligned} x_{k} \ge -\varepsilon \left( \frac{2+\varepsilon }{1+\varepsilon }\right) ^{k}a+(1+\varepsilon )a . \end{aligned}$$
(1)

This is a necessary condition for keeping the competitive ratio less than or equal to \(2+\varepsilon\). But this condition is not sufficient to guarantee optimality within the \(\varepsilon\) bound. We propose next an algorithm that sets exact values for \(x_2,x_3,\ldots ,\) to guarantee optimality within the \(\varepsilon\) bound.

3.2 How to set the coefficients for “optimality”

Before turning to this problem, we need to define what “optimal” means here. Our motivation is to give a better algorithm for slack systems. Thus we introduce a measure, “slackness degree” for representing the slackness of input sequences. For an input sequence \(\sigma = \langle t_1,t_2,\ldots ,t_n \rangle\), request i is called a busy request if \(u_i \le a\) or a slack request, otherwise. The first request is neither busy nor slack one. We denote the number of slack requests in \(\sigma\) by \(s(\sigma )\), and that of busy requests in \(\sigma\) by \(b(\sigma )\).

Definition 1

For an input \(\sigma\), if \(s(\sigma )/b(\sigma ) \ge d \ (b(\sigma )\ne 0)\) for a real number \(d \ge 0\), \(\sigma\) is called d-slack. The slackness degree \(d(\sigma )\) is defined as the maximum d such that \(\sigma\) is d-slack.

The slackness degree describes how busy the inputs are. Clearly if \(d(\sigma )\) is larger, \(\sigma\) has more slack. We will optimize DRA under the assumption that an input is d-slack without knowing the value of d.

We consider asymptotic performance, and assume that \(\sigma\) is large enough. In other words \(\sigma\) has a sufficient number of busy requests, i.e., \(b(\sigma ) = \omega (1)\) if \(b(\sigma ) \ne 0\).

Note that for \(b(\sigma )=0\) (i.e., all arrivals are slack), we can easily get the upper bound of the competitive ratio of \(1+\frac{\sum _{i=1}^{|\sigma |}x_i}{|\sigma |a}\), which is close to 1 when \(|\sigma |\) is large and \(\lim _{i \rightarrow \infty } x_i = 0\). This case is so particular that we ignore it in the following. We will show that it is sufficient to consider inputs which end with a busy request:

For a detailed analysis, let us separate an input \(\sigma = \langle t_1,t_2, \ldots , t_n \rangle\) into some (\(b(\sigma )\) or \(b(\sigma )+1\)) blocks as follows. Assume that \(t_{b_{1}},t_{b_{2}},\ldots ,t_{b_{b(\sigma )}}\) \((0 \le b_1< b_2< \cdots < b_{b(\sigma )} \le n)\) are the busy requests in \(\sigma\). The blocks are defined as \(B_1 = \{t_1,\ldots ,t_{b_1}\}\), \(B_2 = \{t_{b_{1}+1},\ldots ,t_{b_2}\}\), \(\ldots \,\), \(B_{b(\sigma )} = \{t_{b_{b(\sigma )-1}+1},\ldots ,t_{b_{b(\sigma )}}\}\). If \(b_{b(\sigma )} < n\), then \(B_{b(\sigma )+1} =\{t_{b_{b(\sigma )}+1},\ldots ,t_n\}\) also exists. For analyzing the worst-case competitive ratio we will show that the final block \(B_{b(\sigma )+1}\) can be ignored even if it exists. Let \(\beta (\sigma )\) be the number of blocks in \(\sigma\). (Then \(\beta (\sigma ) = b(\sigma )\) or \(b(\sigma )+1\).) Let \(s(B_{i})\) be the number of slack requests in block \(B_i\).

Lemma 1

If \(s(B_{b(\sigma )}) \le s(B_{b(\sigma )+1})-2\) holds, then \(\mathcal {R}_{\text { DRA}}(\sigma ) \le \mathcal {R}_{\text { DRA}}(\sigma ')\), where \(\sigma '\) is obtained from \(\sigma\) by exchanging \(t_{b_{b(\sigma )}}\) with \(t_{b_{b(\sigma )}+1}\), i.e., \(\sigma ' = \langle t_1,\ldots ,\) \(t_{b_{b(\sigma )}-1},\) \(t_{b_{b(\sigma )}+1},\) \(t_{b_{b(\sigma )}},t_{b_{b(\sigma )}+2},\ldots ,t_n \rangle\). (Note that \(t_{b_{b(\sigma )}+1}\) is a slack request from \(s(B_{b(\sigma )})\) \(( \ge 2)\).)

Proof

The competitive ratio of DRA for \(\sigma '\) is

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\sigma ') = \frac{DRA(\sigma )-x_{s\left( B_{b(\sigma )+1}\right) }+x_{s\left( B_{b(\sigma )}\right) +2}}{OPT(\sigma )-x_{s\left( B_{b(\sigma )}\right) +1}+x_{s\left( B_{b(\sigma )}\right) +2}}. \end{aligned}$$

Since \(x_1,x_2,\ldots\) is a non-increasing sequence and \(s(B_{b(\sigma )}) \le s(B_{b(\sigma )+1})-2\), \(x_{s(B_{b(\sigma )})+2} \ge x_{s(B_{b(\sigma )+1})}\) and \(x_{s(B_{b(\sigma )})+1} \ge x_{s(B_{b(\sigma )})+2}\) hold. Thus we get

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\sigma ') = \frac{DRA(\sigma )-x_{s\left( B_{b(\sigma )+1}\right) }+x_{s\left( B_{b(\sigma )}\right) +2}}{OPT(\sigma )-x_{s\left( B_{b(\sigma )}\right) +1}+x_{s\left( B_{b(\sigma )}\right) +2}} \ge \frac{DRA(\sigma )}{OPT(\sigma )} = \mathcal {R}_{\text { DRA}}(\sigma ). \end{aligned}$$

□

Lemma 2

For any \(d \ge 0\) and sufficiently long inputs, there exists an input which finishes with a busy request and gives the worst competitive ratio in the same slackness degree d.

Proof

By Lemma 1 for a d-slack input \(\sigma\) we can shift the last busy request later as long as the last two blocks satisfy \(s(B_{b(\sigma )}) \le s(B_{b(\sigma )+1})-2\) without decreasing the competitive ratio (Operation 1). We can clearly exchange the two subsequences in \(\sigma\) which begin with a slack request and end with a busy request without changing the competitive ratio (Operation 2).

When we apply Operation 1 and Operation 2 for a sufficiently long input \(\sigma\) repeatedly and let the result be \(\sigma ^{*}\), which is d-slack and gives the worst competitive ratio, approximately we can assume that \(\sigma ^{*}\) finishes with a busy request. □

Lemma 3

For any input \(\sigma\), if each \(x_i\) satisfies inequality (1) then \(\mathcal {R}_{\text { DRA}}(\sigma ) \le 2+\varepsilon\).

Proof

In Observations 1 and 2, the given input is clearly the worst for the competitive ratio among one-block input \(\sigma\) (i.e., \(\sigma\) includes one busy requests at the end) and the slackness degree is fixed. This means \(\mathcal {R}_{\text { DRA}} \le 2+\varepsilon\) for any one-block input. From Lemma 2, \(\mathcal {R}_{\text { DRA}} \le 2+\varepsilon\) for any long enough input. □

Lemma 4

For a sufficiently long input \(\sigma\), if \(\sigma\) is d-slack \((d>0)\) and \(x_1,x_2,\ldots\) \(\ (x_i \le a)\) satisfy inequality (1), the following inequality holds:

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\sigma ) \le 1+\frac{1}{d}+\frac{\sum _{i=1}^{\infty } x_i}{ad}. \end{aligned}$$
(2)

And the equality holds for \(d \ge h-1\) where \(h = \min \{i \,|\, x_i = 0\}\).

Proof

To analyze the worst-case input, we define \(\sigma (k)\) as an input in which one busy request arrives after \((k-1)\) slack requests, where \(k=1,2,\ldots ,\) is any positive integer. Then we find that all the worst-case input instances are described as the combination of \(\sigma (k)\) by Lemma 2. Let the combination of them be \(\sigma _{w}\), which can be represented by a sequence of \(\sigma (\cdot )\), i.e., \(\sigma _{w} = \sigma ({f(1)})\sigma ({f(2)})\cdots \sigma ({f(n)})\) where \(n = b(\sigma _{w})\), and each f(i) is a positive integer \((i=1,\ldots ,n)\).

Against this input, DRA must pay the switching cost for all the requests. The cost of DRA for \(\sigma _{w}\) is \(a + \sum _{i=1}^{n}\left\{ \sum _{j=1}^{f(i)} (x_{j} + a)\right\} +x_1\). OPT keeps the ON-state during \(x_{f(i)}\) for the last input in each \(\sigma (f(i))\) and switches to OFF immediately for the other inputs. The cost is \(a+\sum _{i=1}^{n}x_{f(i)} + \sum _{i=1}^{n}(f(i)-1)a\). Therefore the competitive ratio is

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\sigma _{w})= & {} \frac{a + \sum _{i=1}^{n}\left( \sum _{j=1}^{f(i)} (x_{j} + a)\right) +x_1}{a+\sum _{i=1}^{n}x_{f(i)} + \sum _{i=1}^{n}(f(i)-1)a} \\\le & {} \frac{a+ \sum _{i=1}^{n}\sum _{j=1}^{f(i)-1}x_{j} + \sum _{i=1}^{n}f(i)a+x_1}{a+\sum _{i=1}^{n}(f(i)-1)a} \\\le & {} \frac{a + n\sum _{i=1}^{\infty }x_i +\sum _{i=1}^{n}(f(i)-1)a + an + x_1}{a+\sum _{i=1}^{n}(f(i)-1)a}. \end{aligned}$$

Since \(\sum _{i=1}^{n}(f(i)-1)/n = s(\sigma _{w})/b(\sigma _{w}) \ge d\) and \(\sigma _{w}\) is d-slack, we have

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\sigma ) \le \mathcal {R}_{\text { DRA}}(\sigma _{w})&\le 1+\frac{\sum _{i=1}^{\infty }x_i + a + x_1/n}{a/n + ad} \\&{\mathop {\rightarrow }\limits ^{(n \rightarrow \infty )}}1+\frac{1}{d}+\frac{\sum _{i=1}^{\infty } x_i}{ad}. \end{aligned}$$

The inequalities are tight when \(\sum _{i=1}^n x_{f(i)} =0\), and such input exists only when \(\sum _{i=1}^{n}f(i)/n \ge h\). Thus for a sufficiently long input when \(d \ge h-1\), we find that the bound is tight. □

Note that even for 0-slack inputs \((s(\sigma )=0)\), if \(x_1,x_2,\ldots\) satisfy (1), the competitive ratio is guaranteed to be \(2+\varepsilon\) according to Observation 1.

We get the upper bound of the worst competitive ratio with parameter d. To minimize it, we should minimize each \(x_i\) such that they satisfy (1).

Theorem 1

We set the coefficients \(x_i\) as \(x_i = \max \{-\varepsilon \left( (2+\varepsilon )/(1+\varepsilon )\right) ^{i}a+(1+\varepsilon )a,\ 0\}\). Then for any sufficiently long d-slack input \(\sigma\), DRA guarantees the following competitive ratio:

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\Sigma _{d}) = \min \left\{ 1+\frac{1}{d}+\frac{\sum _{i=1}^{h-1} x_i}{ad},\ 2+\varepsilon \right\} , \end{aligned}$$
(3)

where \(\Sigma _d\) is the set of sufficiently long d-slack inputs, and \(h = \lfloor (\log (1+\varepsilon )-\log \varepsilon )/\) \((\log (2+\varepsilon )-\log (1+\varepsilon )) \rfloor +1\).

Proof

Let h be defined as in Lemma 4. Then the value of h is obtained as shown above. From Lemmas 4 and 3 we get

$$\begin{aligned} \mathcal {R}_{\text { DRA}}(\Sigma _{d}) \le \min \left\{ 1+\frac{1}{d}+\frac{\sum _{i=1}^{\infty } x_i}{ad},\ 2+\varepsilon \right\} . \end{aligned}$$

To optimize the competitive ratio we should minimize each \(x_i\) in range of satisfying inequality (1). So we get

$$\begin{aligned} x_i = \left\{ \begin{array}{ll} \displaystyle -\varepsilon \left( \frac{2+\varepsilon }{1+\varepsilon }\right) ^{i}a +(1+\varepsilon )a &{} \quad \text {if}\ i < h \text {,} \\ 0 &{} \quad \text {otherwise}. \end{array} \right. \end{aligned}$$
(4)

This means \(\sum _{i=1}^{\infty } x_i = \sum _{i=1}^{h-1} x_i\).

Furthermore, from Lemma 4, when \(d \ge h-1\) there are inputs which hold the equation in (2) tightly. On the other hand, from Lemma 3, when \(d < h-1\), there are inputs such that DRA uses only \(x_1,\dots ,x_d\) (i.e., they satisfy (1) tightly.) and then achieve \(2+\varepsilon\)-competitive ratio tightly. Therefore we obtain the desired equation (3). □

From this, we will call the DRA satisfying the condition of Theorem 1 the optimal DRA (ODRA).

Corollary 1

For the value that \(0< \varepsilon <0.2\),

$$\begin{aligned} \mathcal {R}_{\text { ODRA}} \le \min \left\{ 1+\frac{(1+\varepsilon )^2 + 2(1+\varepsilon )\log \frac{1}{\varepsilon }}{d},\ 2+\varepsilon \right\} . \end{aligned}$$

We also get such a heuristic bound, but skip the details of proof. If \(d \rightarrow \infty\) then \(\mathcal {R}_{\text {ODRA}} \rightarrow 1\). Therefore we confirm that the competitive ratio is close to 1 when the frequency of requests within any time period is small enough.

4 Queueing analysis

4.1 Analysis

In this section, we analyze the cost performance of DRA using queueing theory. We consider a huge space in a public building, called a system hereafter. Customers arrive at the system, stay for a while, and then leave the system. An on-off device is equipped with the system. At first, the device is turned off, and then turned on if the first customer arrives at the system. The device is kept on as long as there exists at least one customer in the system. When all customers leave the system, the device is turned off according to DRA whose coefficients \(\{x_i: i=1,2,\ldots \}\) are given by (4). In the following, we say the system is in ON (resp. OFF) state when the device is on (resp. off).

We assume that customers arrive at the system according to a Poisson process with rate \(\lambda\). The sojourn time of a customer is independently and identically distributed (i.i.d.) with a general distribution with mean \(1/\mu\). As we mentioned before, the system capacity is infinity. Then the system we consider here is an M/G/\(\infty\) queueing model.

In the M/G/\(\infty\) model, the busy period is defined as the time interval during which the number of customers in the system is greater than zero, while in the idle period, no customers are in the system. For analytical simplicity, we assume that the system is in equilibrium at time 0, and that the first busy period starts at time 0. Let \(B_n\) and \(I_n\) denote the nth busy period of the system and the nth idle period, respectively. Note that both busy periods and idle periods are i.i.d., and hence independent of n. The mean busy period and the mean idle period of the M/G/\(\infty\) system are given by

$$\begin{aligned} E[B_n] = {e^\rho -1 \over \lambda } \left( \equiv E[B] \right) ,\quad E[I_n] = {1\over \lambda } \left( \equiv E[I]\right) , \end{aligned}$$
(5)

respectively, where \(\rho =\lambda /\mu\). We define the nth cycle as the time interval consisting of \(B_n\) and \(I_n\).

The power control process under DRA with coefficients (4) evolves as follows. When the first busy period \(B_1\) starts, the initial power cost a is required. During the busy period, the power cost per unit time is one. When \(B_1\) ends, the system is kept ON state for the standby time of \(x_1\). Note that \(x_1\) is the power cost of the first idle period \(I_1\). If \(I_1 > a\), the next standby time for \(I_2\) is set to \(x_2\). If \(I_1 \le a\), then the standby time for \(I_2\) is initialized to \(x_1\). Similarly, if \(I_1>a\) and \(I_2>a\), then the the standby time for \(I_3\) is set to \(x_3\), while if \(I_1>a\) and \(I_2\le a\), the standby time for \(I_3\) is initialized to \(x_1\), and so on. In the following, the time interval from the beginning of the busy period with \(x_1\) standby time to the end of the idle period which is smaller than a is referred to as the reset interval.

Let L (\(\ge 1\)) denote the number of cycles in a reset interval. Consider the amount of power consumption during a reset interval. When the number of cycles in the reset interval is \(L=k\), the amount of power consumption is given by the power consumption for k busy periods and k standby times. Let \(T_k\) denote the total amount of power consumption of the reset interval consisting of k cycles. We obtain

$$\begin{aligned} T_k = \left\{ \begin{array}{ll} \sum _{i=1}^{k-1}x_i + I_k\cdot 1_{\left\{ I_k\le x_k \right\} } + x_k \cdot 1_{\left\{ x_k \le I_k\le a\right\} }, &{} k=1,2,\ldots , h -1,\\ \sum _{i=1}^{ h -1} x_i, &{} k\ge h , \end{array}\right. \end{aligned}$$

where \(1_\chi\) is the indicator function of event \(\chi\). Then we have the following lemma.

Lemma 5

The mean of the total amount of power consumption of a reset interval \(E[T_L]\) is given by

$$\begin{aligned} E[T_L]=\; & {} \epsilon a(2+\epsilon )e^{-\lambda a}\left( 1-e^{-\lambda a}\right) ^{h -2} \nonumber \\&-\epsilon a(2+\epsilon )\left( 1-e^{-\lambda a}\right) {(2+\epsilon )e^{-\lambda a}\over 1+\epsilon -(2+\epsilon )e^{-\lambda a}} \left\{ 1-\left( {2+\epsilon \over 1+\epsilon }\cdot e^{-\lambda a}\right) ^{h -2} \right\} \nonumber \\&+(1+\epsilon )a\cdot {e^{-\lambda a} \over 1-e^{-\lambda a}}\left\{ 1-(h -1)e^{-\lambda a(h -2)}+(h -2)e^{-\lambda a(h -1)}\right\} \nonumber \\&+{1\over \lambda }\cdot {1-e^{-\lambda a(h -1)}\over 1-e^{-\lambda a}} - \sum _{k=1}^{ h -1}e^{-\lambda a(k-1)}\left( {1\over \lambda } e^{-\lambda x_k} + x_k e^{-\lambda a} \right) \nonumber \\&+ \left[ \epsilon a(2+\epsilon )\left\{ 1-\left( {2+\epsilon \over 1+\epsilon } \right) ^{h -1} \right\} + (1+\epsilon )a(h -1)\right] \cdot e^{-\lambda a(h -1)}. \end{aligned}$$
(6)

Proof

Note that the event \(\{L=k\}\) (\(k=1,2,\ldots\)) is such that the first to (\(L-1\))st idle periods are greater than a and the Lth idle period is smaller than or equal to a. Define the following joint probability density function

$$\begin{aligned} \pi _k (y)dy=\Pr \left\{ L=k, y<I_k\le y+dy\right\} ,\quad k=1,2,\ldots . \end{aligned}$$
(7)

From the Poisson arrival assumption, we obtain

$$\begin{aligned} \pi _k (y)dy=e^{-\lambda a(k-1)}\cdot \lambda e^{-\lambda y}dy, \quad k=1,2,\ldots . \end{aligned}$$
(8)

Let W(k) denote the total amount of power consumption for a reset interval which consists of k cycles. W(k) is given by

$$\begin{aligned} W(k) = (k-1)a + a\cdot 1_{\left\{ x_{k}<I_k\le a\right\} }+ \sum _{i=1}^kB_i + T_k. \end{aligned}$$

Taking the mean of W(L) yields

$$\begin{aligned} E[W(L)]= & {} E\left[ a(L-1) + a\cdot 1_{\{x_{k}<I_k\le a\}} + \sum _{i=1}^LB_i + T_L \right] \nonumber \\= & {} a\left( E[L]-1\right) + aE\left[ 1_{\{x_{k}<I_k\le a\}}\right] + E[L]E[B] + E[T_L]. \end{aligned}$$
(9)

From (8), E[L] is obtained as

$$\begin{aligned} E[L]= & {} \sum _{k=1}^\infty k \Pr \{L=k\} \nonumber \\= & {} \sum _{k=1}^\infty k \int _0^a \pi _k (y) dy \nonumber \\= & {} \sum _{k=1}^\infty k e^{-\lambda a(k-1)}\left( 1-e^{-\lambda a}\right) \nonumber \\= & {} {1\over 1-e^{-\lambda a}}. \end{aligned}$$
(10)

We also have

$$\begin{aligned} E[1_{\{x_{k}< I_k \le a\}}]= & {} \sum _{k=1}^\infty \int _{x_k}^a e^{-\lambda a(k-1)}\lambda e^{-\lambda x}dx \nonumber \\= & {} \sum _{k=1}^{ h -1} e^{-\lambda \{a(k-1)+x_k\}} - {e^{-\lambda a}-e^{-\lambda a( h -1)}\over 1-e^{-\lambda a}}. \end{aligned}$$
(11)

\(E[T_L]\) is expressed as

$$\begin{aligned} E[T_L]= & {} \sum _{k=1}^\infty \int _0^a \left\{ \sum _{i=1}^{k-1}x_i + y\cdot 1_{\{I_k \le x_k\}} + x_k \cdot 1_{\{x_k \le I_k \le a\}}\right\} \pi _k(y)dy \nonumber \\= & {} \sum _{k=2}^{ h -1}\left( \sum _{i=1}^{k-1}x_i\right) e^{-\lambda a(k-1)}\left( 1-e^{-\lambda a}\right) + \sum _{k=1}^{ h -1}\int _0^{x_k} y\cdot \lambda e^{-\lambda y} \cdot e^{-\lambda a(k-1)} dy \nonumber \\&+ \sum _{k= h }^\infty \left( \sum _{i=1}^{k-1}x_i\right) e^{-\lambda a(k-1)}\left( 1-e^{-\lambda a}\right) + \sum _{k=1}^{h-1} \int _{x_k}^a x_k \cdot \lambda e^{-\lambda y} \cdot e^{-\lambda a(k-1)} dy. \end{aligned}$$
(12)

Substituting (4) into (12) yields (6). □

Let \(Q_\mathrm{DRA}\) denote the mean power-consumption cost per unit time. Then we obtain the following theorem.

Theorem 2

\(Q_\mathrm{DRA}\) is given by

$$\begin{aligned} Q_\mathrm{DRA}= {1\over e^\rho }\left[ \lambda a\left\{ \left( 1-e^{-\lambda a}\right) \cdot \sum _{k=1}^{ h -1}e^{-\lambda \{a(k-1)+x_k\}} + e^{-\lambda a( h -1)}\right\} + e^\rho -1 + \lambda \left( 1-e^{-\lambda a}\right) E[T_L] \right] , \end{aligned}$$
(13)

where \(E[T_L]\) is given by (6).

Proof

Let R denote the reset interval. Using L, the number of cycles in a reset interval, we obtain

$$\begin{aligned} R = \sum _{n=1}^L \left( B_n+I_n\right) , \end{aligned}$$

where \(B_n\) and \(I_n\) are the nth busy period and nth idle period, respectively. Note that \(\{B_n\}\) and \(\{I_n\}\) are independent.

Suppose \(L=k\). Let \(I_n^*(s)\) denote the Laplace-Stieltjes transform (LST) of \(I_n\). Since \(I_n\) for \(n=1,2,\ldots ,k-1\) is greater than a and \(I_k\) is smaller than or equal to a, \(I_n^*(s)\) is yielded as

$$\begin{aligned} I_n^*(s) = \left\{ \begin{array}{ll} {\lambda \over s+\lambda } e^{-(s+\lambda )a}, &{} n=1,2,\ldots ,k-1,\\ {\lambda \over s+\lambda } \left( 1-e^{-(s+\lambda )a}\right) , &{} n=k. \end{array} \right. \end{aligned}$$
(14)

We define \(I^*(k,s)\) as

$$\begin{aligned} I^*(k,s) = \int _0^\infty e^{-sx} \Pr \left\{ L=k, x< \sum _{n=1}^k I_n \le x+dx\right\} \end{aligned}$$

\(I^*(k,s)\) is the LST of the total idle period of the reset interval which consists of k cycles. Using \(I_n^*(s)\), we obtain

$$\begin{aligned} I^*(k,s) = \prod _{n=1}^k I_n^*(s) = \left( {\lambda \over s+\lambda }\right) ^k e^{-(s+\lambda )a(k-1)} \left( 1-e^{-(s+\lambda )a}\right) . \end{aligned}$$
(15)

Then, the mean amount of idle periods in a reset interval is given by

$$\begin{aligned} E\left[ \sum _{n=1}^L I_n\right] = \sum _{k=1}^\infty \left( -{d\over ds}I^*(k,s)\right) _{s=0} = {1\over \lambda \left( 1-e^{-\lambda a}\right) }. \end{aligned}$$
(16)

The mean amount of busy periods in a reset cycle is yielded as

$$\begin{aligned} E\left[ \sum _{n=1}^L B_n\right] = \sum _{k=1}^\infty k E[B] e^{-\lambda a(k-1)}\left( 1-e^{-\lambda a}\right) = {e^\rho -1 \over \lambda \left( 1-e^{-\lambda a}\right) }, \end{aligned}$$
(17)

where \(\rho =\lambda /\mu\).

Finally, the mean reset interval E[R] is given by

$$\begin{aligned} E[R] = E\left[ \sum _{n=1}^L B_n\right] + E\left[ \sum _{n=1}^L I_n \right] = {e^\rho \over \lambda \left( 1-e^{-\lambda a}\right) }. \end{aligned}$$
(18)

Now consider the mean power consumption per unit time, \(Q_\mathrm{DRA}\). Note that reset intervals are i.i.d., and that the amount of power consumption during the reset interval is also i.i.d. Therefore, we have \(Q_\mathrm{DRA} = E[W(L)]/E[R]\) from the renewal-reward theorem [39]. From (9), (10), (11) and (17), we obtain (13). □

4.2 Simplified reset algorithms

It may be advantageous to consider simplified variants of DRA; such algorithms may have worse competitive ratio, but still may work well on average. We consider here the following family of algorithms: Given parameter k let

  • ALG(k) be the DRA algorithm where \(x_1=x_2=\cdots =x_k=a\), \(x_{k+1}=x_{k+2}=\cdots =0\).

The worst-case competitive ratio of ALG(k) is \(2+\frac{1}{k}\), which can be obtained easily. In what follows we consider three cases:

  1. (a)

    \(ALG(\infty )\) (all \(x_i\) are equal to a)

  2. (b)

    ALG(1)

  3. (c)

    ALG(10).

Note that \(ALG(\infty )\) is equal to OWCR.

Let \(Q_{\xi }\) denote the mean of the power-consumption cost per unit time when the algorithm of \(\xi \in \{OPT, ALG(\infty ),{} ALG(1), ALG(10)\}\) is employed. \(Q_{\xi }\)’s can be derived in a straightforward manner, and we obtain

$$\begin{aligned} Q_{{{\text{OPT}}}} & = 1 - e^{{ - (a\lambda + \rho )}} , \\ Q_{{{\text{ALG}}(\infty )}} & = 1 + (a\lambda - 1)e^{{ - (a\lambda + \rho )}} , \\ Q_{{{\text{ALG}}(1)}} & = 1 + 2(a\lambda - 1)e^{{ - (a\lambda + \rho )}} - (a\lambda - 1)e^{{ - (2a\lambda + \rho )}} , \\ Q_{{{\text{ALG}}(10)}} & = 1 + (a\lambda - 1)e^{{ - (a\lambda + \rho )}} + (a\lambda - 1)e^{{ - (ka\lambda + \rho )}} - (a\lambda - 1)e^{{ - ((k + 1)a\lambda + \rho )}} . \\ \end{aligned}$$

In Table 3 we display competitive ratios of \(ALG(\infty )\), ALG(1), ALG(10), as well as ODRA for \(\epsilon =0.1, 0.01\) and 0.001 given different degrees of slackness. We use the basic set of parameters shown in Table 2 and calculated the average power consumption per unit time of each algorithm and the competitive ratio with \(Q_{\mathrm {opt}}\).

Table 2 Basic parameters
Full size table
Table 3 Analytical results of competitive ratios
Full size table

Next, we conducted experiments of Monte Carlo simulation in order to validate the results obtained through the analysis. Our simulation program was written in C. For each parameter setting, we performed 100 different simulation runs, each one consisting of 100000 arrival events. Then, \(\widehat{Q}_\xi\) \((\xi \in\) \(\{\text {OPT}, \text {ALG}(\infty ),\) \(\text {ALG(1), ALG(10), ODRA}\})\), the estimate of \(Q_\xi\), was calculated by taking the average of the 100 simulation results.

Table 4 Simulation results of competitive ratios
Full size table

From Tables 3 and 4 we observe that the differences between the analysis and the simulations ratios are extremely small, which is summarized in Table 5.

We mention that there are two natural algorithms, namely the algorithm “always-on”, which always continues to standby in the on state, and the algorithm “always-off”, which switches off immediately after each request. However, both of these algorithms are not competitive.

Table 5 Difference between analysis and simulation
Full size table

4.3 Analysis of results

We now provide further analysis of the algorithms in the previous subsection. It is noted that in Sect. 2 “Problem Statement” the power-down problem was formalized under the “short-job assumption” and this assumption was used in Sect. 3 to develop the DRA approach. Figure (1a) depicts competitive ratios of the algorithms over \(\rho\) in the case where the value of a is large relative to the mean sojourn time \(1/\mu\) (cf. Table 2), thus modeling the “short-job assumption”. To this end, in Fig. 1a we have \(a=10\), \(1/\mu = 1\) and \(\epsilon = 0.1\).

Fig. 1
figure 1

Competitiveness of algorithms

Full size image

Comparing \(ALG(\infty )\), ALG(10), ALG(1), and ODRA, it is clear that ODRA outperforms both \(ALG(\infty )\) and ALG(10) for small values of \(\rho\). When \(\rho\) becomes larger, the differences among all the algorithms decrease to the point where there is almost no difference. It is important to recall that we desire the algorithms to be close to optimally-competitive even for worst-case request sequence instances. While ALG(1) performs quite well, its worst-case competitive ratio is 3. Only ODRA combines a close-to-optimal worst-case competitiveness with good competitiveness across all values of \(\rho\). Finally, observe the values in the third column of Table 6 which gives averages (i.e. the integrals of the curves): Indeed, ODRA exhibits the smallest average, though—as discussed—this is not its most significant feature.

Figure 1b shows the effect of tightening the value of \(\epsilon\) for ODRA. To obtain a better worst-case guarantee ODRA gives up competitiveness across ranges of \(\rho\) when the value of \(\epsilon\) is chosen to be smaller. Thus there is a tradeoff between the demand on how close to optimality the algorithm in the worst-case should be, and what its overall competitiveness is.

Finally, Fig. 1c, d show characteristics for \(a=3\) and \(a=1\). As is expected, the competitiveness behavior is similar, though competitiveness is somewhat better for small values of \(\rho\).

Table 6 Average competitiveness
Full size table

5 Systems with intermediate states

The use of multiple intermediate states, sometimes called “sleep states” affords better competitiveness; see our papers [7] for systems with one extra state, i.e. three-state systems, [8] for systems with finitely many but few states, [6] for systems with a continuous number of states, and our survey paper [9]. In this section we focus on three-state systems; for simplicity we assume that \(a=1\) and consider one extra state \(\text {INT}_{1}\) with standby cost \(s_1\) and switching cost \(a_1\), as in Table 1. As shown in [7] for \(s_1=0.6\) and \(a_1=0.4\), for example, the competitive ratio \(\mathcal {R}\) for this system is 1.8. (The values \(s_1=0.6\) and \(a_1=0.4\) are significant, as among all parameter values \(s_1\) and \(a_1\) for \(\text {INT}_{1}\) this choice gives the lowest competitiveness.) Whereas for a two state system \(\mathcal {OWCR}\) switches to OFF after time a=1 to obtain ratio 2, for this three-state system the \(\mathcal {OWCR}\) switches to \(\text {INT}_{1}\) after idle time \(x_1 = 0.9037\) and to OFF after idle time \(x_2 = 1\). Just as in the two-state case, \(\mathcal {OWCR}\) does not result in good performance in many practical situations, especially in case the device is not used frequently. We will now describe how the DRA approach can be adapted to a system with three states (see also Table 7).

Table 7 Three State Taper Down Values for \(s_1= 0.6\) and \(a_1= 0.4\), \(\mathcal {R} = 1.8\)
Full size table

Let \(u_1, u_2, u_2,...\) be an infinite sequence of standby times in the ON state and let \(q_1, q_2, q_3,...\) be an infinite sequence of standby times in the INT state. So \(u_i\) is the duration of the machine in the ON state and \(q_i\) is the duration in the INT state and after \(u_i + q_i\) time units the machine switches to the OFF state. Since this will be a three state machine, there are two switch times when we have the worst-case cost which occurs immediately at the switch times. Assuming competitive ratio \(\mathcal {R}\) we utilize two equations that we will use to compute these times.

$$\begin{aligned}&\frac{\sum _{i=1}^{k-1}(u_i + s_1q_i + 1) + u_k + a_1}{\sum _{i=1}^{k-1}1 + u_k} = \mathcal {R} + \epsilon \end{aligned}$$
(19)
$$\begin{aligned}&\frac{\sum _{i=1}^{k-1}(u_i + s_1q_i + 1) + u_k + s_1q_k + 1}{\sum _{i=1}^{k-1}1 + u_k + q_k} = \mathcal {R} + \epsilon \end{aligned}$$
(20)

Equation (19) is used to compute \(u_k\) after \(k-1\) slack requests, and that \(u_k\) value is used to compute \(q_k\) in Eq. (20). In the two equations, it is assumed that for state INT, \(s_1+a_1\ge 1\), which can be seen by the offline cost since constants a and d are absent in the offline cost. Similarly to the 2 state DRA, we increase the competitive ratio by a small constant \(\epsilon\), and we attempt to taper the standby duration of the ON and INT state after every slack request, a request that occurs after \(u_i + q_i\), and the durations reset back to \(u_1\) and \(q_1\) otherwise. We substitute \(R = \mathcal {R} + \epsilon\) and we solve for \(u_k\) and \(q_k\), we get

$$\begin{aligned} u_k&= \max \bigg \{\frac{R(k - 1) - \sum _{i=1}^{k-1}(u_i + s_1q_i + 1) - a_1}{1 - R}, 0\bigg \} \end{aligned}$$
(21)
$$\begin{aligned} q_k&= \max \bigg \{\frac{R(k - 1) + u_k(R - 1) - \sum _{i=1}^{k-1}(u_i + s_1q_i + 1) - 1}{s_1- R},0\bigg \} \end{aligned}$$
(22)

Since the value of \(u_k\) from (21) is needed to compute the value of \(q_k\) in (22), if we assume that \(u_k > 0\) to get:

$$\begin{aligned} q_k = \frac{1-a_1}{R-s_1} \end{aligned}$$
(23)

So \(q_k\) does not taper down as long as \(u_k > 0\). Initially, only the duration of the ON state will taper after each slack request while the duration of the machine in state INT does not change. When \(u_k = 0\), several slack requests have arrived consecutively, and then the value of \(q_k\) will begin tapering down. We will obtain a closed form for \(u_k\), as was done for the two state system. We can derive (19) to have

$$\begin{aligned} \sum _{i=1}^{k-1}u_i + s_1\sum _{i=1}^{k-1}q_i - (1-R)u_k = (R-1)(k-1)-a_1\end{aligned}$$
(24)

Since we know that if any \(u_i > 0\), then the values for \(q_i\) will never taper down so we can substitute \(q_i = \frac{1-a_1}{R-s_1}\) and then we have

$$\begin{aligned} \sum _{i=1}^{k}u_i - Ru_k = (R-1)k - R + (R - s_1k)\frac{1-a_1}{R-s_1} \end{aligned}$$
(25)

Now we can simply substitute \(k = k - l\) in (25) to have

$$\begin{aligned} \sum _{i=1}^{k-1}u_i - Ru_{k-1} = (R-1)(k-1) - R + \left( R - s_1(k-1)\right) \frac{1-a_1}{R-s_1} \end{aligned}$$
(26)

If we subtract (26) from (25) we have the following recurrence

$$\begin{aligned} (1-R)u_k +Ru_{k-1} = (R-1) - s_1\frac{1-a_1}{R-s_1} \end{aligned}$$
(27)

Let us substitute the right hand side to \(\phi = (R-1) - s_1\frac{1-a_1}{R-s_1}\)

$$\begin{aligned} u_k - \phi = \frac{R}{R-1}(u_{k-1} - \phi ) \end{aligned}$$
(28)

In (28), we can see that \((R)/(R-1)\) is multiplied k times so we can rewrite (28)

$$\begin{aligned} u_k - \phi = \bigg (\frac{R}{R-1} \bigg )^{k-1} (u_1 - \phi ) \end{aligned}$$
(29)

From Eq. (21) from the last section, we can compute \(u_1 = d / (R-1)\), substitution that for \(u_1\) we obtain

$$\begin{aligned} u_k = \max \bigg \{\bigg ( \frac{R}{R-1}\bigg )^{k-1} (a_1/(R-1) - \phi ) + \phi , 0\bigg \} \end{aligned}$$
(30)

For all \(i < l\) if \(u_i > 0\), then we know that \(q_i\) does not change, let l be an index such that \(u_l = 0\) and \(u_{l-1} > 0\), which can be computed from (30), so the index l is the first instance such that the duration becomes zero, in which this case the value of \(q_l \le q_{l-1}\) and this holds for all indices larger than l. So we will derive a formula for the tapering values for \(q_k\), similar to how we derived the formula for \(u_k\), we will start by deriving (20) by replacing k with l

$$\begin{aligned} \sum _{i=1}^{l}u_i + s_1\sum _{i=1}^{l}q_i - Ru_l - Rq_l = R(l-1)-l \end{aligned}$$
(31)

As done earlier, we will substitute \(l = l-1\)

$$\begin{aligned} \sum _{i=1}^{l-1}u_i + s_1\sum _{i=1}^{l-1}q_i - Ru_{l-1} - Rq_{l-1} = R(l-2)-l + 1 \end{aligned}$$
(32)

Once again we subtract (31) from (32)

$$\begin{aligned} u_l + s_1q_l + R\left( u_{l-1} - u_l\right) + R\left( q_{l-1} - q_l\right) = R - 1 \end{aligned}$$
(33)

So as we assumed before, \(u_l = 0\) so we make that substitution into (33)

$$\begin{aligned}&s_1q_l + Ru_{l-1} + R\left( q_{l-1} - q_l\right) = R - 1 \nonumber \\&q_l = \frac{R-1-R\left( u_{l-1}+q_{l-1}\right) }{s_1- r} \end{aligned}$$
(34)

This \(q_l\) from (34), will be used to solve the recurrence for \(q_l\) values. In order to derive this formula, we will begin with (33) which was obtained by subtracting (31) from (32). We will substitute l for t and \(t \ge l\), so we have

$$\begin{aligned} s_1q_{t} + Rq_{t-1} - Rq_{t} = R - 1 \end{aligned}$$
(35)

The difference between (35) and (33) is that in this case both \(u_t = 0\) and \(u_{t-1} = 0\) since \(t > l\) in which at this point \(u_l = 0\) and \(u_{l+1} = 0\) must be true and \(t > l\) so \(u_t = 0\) and \(u_{t-1} = 0\) must be true as well. Now when we solve for \(q_t\), we have the following recurrence

$$\begin{aligned} q_{t} = \frac{R-1}{s_1-R} + \bigg (\frac{R}{R-a}\bigg )q_{t-1} \end{aligned}$$
(36)

Let us substitute \(\chi = \frac{R}{R-s_1}\), when we solve the recurrence we have

$$\begin{aligned} q_{t} = \max \bigg \{\chi ^{t-l}q_l + \bigg (\frac{R-1}{s_1-R}\bigg ) \Bigg ( \frac{\chi ^{t-l}-1}{\chi - 1}\Bigg ), 0\bigg \} \end{aligned}$$
(37)

6 Conclusions and outlook

With the proliferation of IT devices and the adoption of a smart grid powered by renewables, power-down methods are becoming increasingly relevant. The decrease and reset approach affords close to optimal performance while guaranteeing good performance over a large spectrum of request types. The different types of analysis employed in this paper show that the decrease and reset approach achieves significant improvements for power-down problems. We suggest that decrease and reset should be used in practice across various applications but especially in the context of the electrical grid. To ensure resiliency of a majority-renewables grid our work on the power-down problem demonstrates that online competitive analysis and methods from game theory can be useful tools for existing and future modeling. Further work is under way to see how decrease and reset approach can be adapted to various multi-state systems.

We could further refine our approach by utilizing a budget-based method which keeps a tally of gains and losses as requests are processed. This approach would be similar conceptually to decrease and reset in terms of how the system tapers down, but the adjusted wait times in the budget-based approach would calculate the switch time to be even more cost efficient.