Optimal Asynchronous Dynamic Policies in Energy-Efficient Data Centers

Abstract

In this paper, we apply a Markov decision process to find the optimal asynchronous dynamic policy of an energy-efficient data center with two server groups. Servers in Group 1 always work, while servers in Group 2 may either work or sleep, and a fast setup process occurs when the server’s states are changed from sleep to work. The servers in Group 1 are faster and cheaper than those of Group 2 so that Group 1 has a higher service priority. Putting each server in Group 2 to sleep can reduce system costs and energy consumption, but it must bear setup costs and transfer costs. For such a data center, an asynchronous dynamic policy is designed as two sub-policies: The setup policy and the sleep policy, both of which determine the switch rule between the work and sleep states for each server in Group 2. To find the optimal asynchronous dynamic policy, we apply the sensitivity-based optimization to establish a block-structured policy-based Markov process and use a block-structured policy-based Poisson equation to compute the unique solution of the performance potential by means of the RG-factorization. Based on this, we can characterize the monotonicity and optimality of the long-run average profit of the data center with respect to the asynchronous dynamic policy under different service prices. Furthermore, we prove that a bang–bang control is always optimal for this optimization problem. We hope that the methodology and results developed in this paper can shed light on the study of more general energy-efficient data centers.

1. Introduction

Over the last two decades considerable attention has been given to studying energy- efficient data centers. On the one hand, as the number and size of data centers increase rapidly, energy consumption becomes one main part of the operating costs of data centers. On the other hand, data centers have become a fundamental part of the IT infrastructure in today’s Internet services, in which a huge number of servers are deployed in each data center such that the data centers can provide cloud computing environments. Therefore, finding optimal energy-efficient policies and designing optimal energy-efficient mechanisms are always interesting, difficult, and challenging in the energy-efficient management of data centers. Readers may refer to recent excellent survey papers, such as Masanet et al. [1], Zhang et al. [2], Nadjahi et al. [3], Koot and Wijnhoven [4], Shirmarz and Ghaffari [5], Li et al. [6], and Harchol-Balter [7].

Barroso and Hölzle [8] demonstrated that many data centers were designed to handle peak loads effectively, but this directly caused a significant number of servers (approximately 20%) in the data centers to be idle because no work was done in the off-peak period. Although the idle servers do not provide any services, they still continue to consume a notable amount of energy, which is approximately 70% of the servers working in the on-peak period. Therefore, it is necessary and useful to design an energy-efficient mechanism for specifically dealing with idle servers. In this case, a key technique, the energy-efficient states of “Sleep” or “Off” were introduced such that the idle servers can take the sleep or off state, which always consumes less energy, in which the sleep state consumes very little energy, while the energy consumption of the off state is zero. See Kuehn and Mashaly [9] for more interpretation. To analyze the energy-efficient states, thus far, some queueing systems either with server energy-efficient states (e.g., work, idle, sleep, and off) or with server control policies (e.g., vacation, setup, and N-policy) have been developed in the study of energy-efficient data centers. Important examples include the survey papers by Gandhi [10] and Li et al. [6], and the research papers by Gandhi et al. [11,12,13], Maccio and Down [14,15], Phung-Duc [16] and Phung-Duc and Kawanishi [17].

It is always necessary to design an optimal energy-efficient mechanism for data centers. To do this, several static optimization methods have been developed using two basic approaches. The first is to construct a suitable utility function for a performance-energy trade-off or a performance cost with respect to the synchronous optimization of different performance measures, for example, reducing energy consumption, reducing system response time, and improving quality of service. The second is to minimize the performance cost by means of some optimal methods, including linear programming, nonlinear programming, and integer programming. Gandhi et al. [12] provided two classes of the performance-energy trade-offs: (a) ERWS, the weighted sum ${\beta }_1\mathbf{E}\left[R\right]+{\beta }_2\mathbf{E}\left[E\right]$ of the mean response time $\mathbf{E}\left[R\right]$ and the mean power cost $\mathbf{E}\left[E\right]$, where ${\beta }_1,{\beta }_2\ge 0$ are weighted coefficients; (b) ERP, the product $\mathbf{E}\left[R\right]\mathbf{E}\left[E\right]$ of the mean response time and the mean power cost. See Gandhi et al. [12] and Gandhi [10] for systematical research. Maccio and Down [14] generalized the ERP to a more general performance cost function that considers the expected cycle rate. Gebrehiwot et al. [18] made some interesting generalizations of the ERP and ERWS by introducing multiple intermediate sleep states. Additionally, Gebrehiwot et al. [19,20] generalized the FCFS queue of the data center with multiple intermediate sleep states to the processor-sharing discipline and to the shortest remaining processing time (SRPT) discipline, respectively. In addition, Mitrani [21,22] provided another interesting method to discuss the data center of N identical servers that contain m reserves, while the idle or work of the servers is controlled by an up threshold U and a down threshold D. He established a new performance cost $C=c_1\mathbf{E}\left[L\right]+c_2\mathbf{E}\left[S\right]$ and provided expressions for the average numbers $\mathbf{E}\left[L\right]$ and $\mathbf{E}\left[S\right]$, so that the performance cost C can be optimized with respect to the three key parameters m, U, and D.

To date, little work has been done on applications of Markov decision processes (MDPs) to find the optimal dynamic control policies of energy-efficient data centers. Readers may refer to recent publications for details, among which Kamitsos et al. [23] constructed a discrete-time MDP and proved that the optimal sleep energy-efficient policy is simply hysteretic, so that it has a double threshold structure. Note that such an optimal hysteretic policy follows Hipp and Holzbaur [24] and Lu and Serfozo [25]. For policy optimization and dynamic power management for electronic systems or equipment, the MDPs and stochastic network optimization were developed from five different perspectives: (a) the discrete-time MDPs by Yang et al. [26]; (b) the continuous-time MDPs by Ding et al. [27]; (c) stochastic network optimization by Liang et al. [28]; (d) the sensitivity-based optimization by Xia and Chen [29], Xia et al. [30], and Ma et al. [31]; and (e) the deep reinforcement learning by Chi et al. [32].

The purpose of this paper is to apply continuous-time MDPs to set up optimal dynamic energy-efficient policies for data centers, in which the sensitivity-based optimization is developed to find the optimal solution. Note that the sensitivity-based optimization is greatly refined from the MDPs by dealing with the Poisson equation by means of some novel tools, for instance, performance potential and performance difference. To date, the sensitivity-based optimization has also been sufficiently related to the Markov reward processes (see Li [33]), thus, it is an effective method for the performance optimization of many practical systems (see an excellent book by Cao [34] for more details). The sensitivity-based optimization theory has been applied to performance optimization in many practical areas. For example, in energy-efficient data centers by Xia et al. [35]; inventory rationing by Li et al. [36]; the blockchain selfish mining by Ma and Li [37]; and in finance by Xia [38].

The main contributions of this paper are threefold. The first contribution is to apply the sensitivity-based optimization (and the MDPs) to study a more general energy-efficient data center with key practical factors, for example, a finite buffer, a fast setup process, and transferring some incomplete service jobs to the idle servers in Group 1 or to the finite buffer, if any. Although practical factors will not increase any difficulty in performance evaluation (e.g., modeling by means of queueing systems or Markov processes, also see Gandhi [10] for more details), they can largely cause substantial difficulties and challenges in finding optimal dynamic energy-efficient policies and, furthermore, in determining threshold-type policies by using the sensitivity-based optimization. For instance, the finite buffer makes the policy-based Markov process appear as the two-dimensional block-structured Markov process from the one-dimensional birth–death process given in Ma et al. [31] and Xia et al. [35].

Note that this paper has two related works: Ma et al. [31] and Xia et al. [35], and it might be necessary to set up some useful relations between this paper and each of the two papers. Compared with Ma et al. [31], this paper considers more practical factors in the energy-efficient data centers such that the policy-based Markov process is block-structured, which makes solving the block-structured Poisson equation more complicated. Compared with Xia et al. [35], this paper introduces a more detailed cost and reward structure, which makes an analysis of the monotonicity and optimality of dynamic energy-efficient policies more difficult and challenging. Therefore, this paper is a necessary and valuable generalization of Ma et al. [31] and Xia et al. [35] through extensively establishing the block-structured policy-based Markov processes, which in fact are the core part of the sensitivity-based optimization theory and its applications in various practical systems.

The second contribution of this paper is that it is the first to find an optimal asynchronous dynamic policy in the study of energy-efficient data centers. Note that the two groups of servers in the data center have “the setup actions from the sleep state to the work state” and “the close actions from the work state to the sleep state”, thus, we follow the two action steps to form an asynchronous dynamic policy, which is decomposed into two sub-policies: the setup policy (or the setup action) and the sleep policy (or the close action). Crucially, one of the successes of this paper is to find the optimal asynchronous dynamic policy from many asynchronous dynamic policies by means of the sensitivity-based optimization. To date, it has still been very difficult and challenging in the MDPs.

The third contribution of this paper is to provide a unified framework for applying the sensitivity-based optimization to study the optimal asynchronous dynamic policy of the energy-efficient data center. For such a more complicated energy-efficient data center, we first establish a policy-based block-structured Markov process as well as a more detailed cost and reward structure, and provide an expression for the unique solution to the block-structured Poisson equation by means of the RG-factorization. Then, we show the monotonicity of the long-run average profit with respect to the setup and sleep policies and the asynchronous policy, respectively. Based on this, we find the optimal asynchronous policy when the service price is higher (or lower) than a key threshold. Finally, we indicate that the optimal control is a bang–bang control. Such a structure of the optimal asynchronous energy-efficient policy reduces the search space, which is a significant reduction of the optimization complexity and effectively alleviates the curse of the dimensionality of MDPs. Therefore, the optimal asynchronous dynamic policy is the threshold-type in the energy-efficient data center. Note that the optimality of the threshold-type policy can realize a large reduction for the search space, thus, the optimal threshold-type policy is of great significance to solve the mechanism design problem of energy-efficient data centers. Therefore, the methodology and results developed in this paper provide new highlights for understanding dynamic energy-efficient policy optimization and mechanism design in the study of more general data centers.

The organization of this paper is as follows. In Section 2, we give a problem description for an energy-efficient data center with more practical factors. In Section 3, we establish a policy-based continuous-time block-structured Markov process and define a suitable reward function with respect to both states and policies of the Markov process. In Section 4, we set up a block-structured Poisson equation and provide an expression for its unique solution by means of the RG-factorization. In Section 5, we study a perturbation realization factor of the policy-based continuous-time block-structured Markov process for the asynchronous dynamic policy, and analyze how the service price impacts on the perturbation realization factor. In Section 6, we discuss the monotonicity and optimality of the long-run average profit of the energy-efficient data center with respect to the asynchronous policy. Based on this, we can give the optimal asynchronous dynamic policy of the energy-efficient data center. In Section 7, if the optimal asynchronous dynamic policy is the threshold-type, then we can compute the maximal long-run average profit of the energy-efficient data center. In Section 8, we give some concluding remarks. Finally, three appendices are given, both for the state-transition relation figure of the policy-based block-structured continuous-time Markov process and for the block entries of its infinitesimal generator.

2. Model Description

In this section, we provide a problem description for setting up and optimizing an asynchronous dynamic policy in an energy-efficient data center with two groups of different servers, a finite buffer, and a fast setup process. Additionally, we provide the system structure, operational mode, and mathematical notations in the energy-efficient data center.

Server groups: The data center contains two server groups: Groups 1 and 2, each of which is also one interactive subsystem of the data center. Groups 1 and 2 have $m_1$ and $m_2$ servers, respectively. Servers in the same group are homogeneous, while those in different groups are heterogeneous. Note that Group 1 is viewed as a base-line group whose servers are always at the work state even if some of them are idle, the purpose of which is to guarantee a necessary service capacity in the data center. Hence, each server in Group 1 always works regardless of whether it has a job or not, so that it must consume an amount of energy at any time. In contrast, Group 2 is regarded as a reserved group whose servers may either work or sleep so that each of the $m_2$ servers can switch its state between work and sleep. If one server in Group 2 is at the sleep state, then it consumes a smaller amount of energy than the work state, as maintaining only the sleep state requires very little energy.

A finite buffer: The data center has a finite buffer of size $m_3$. Jobs must first enter the buffer, and then they are assigned to the groups (Group 1 is prior to Group 2) and subsequently to the servers. To guarantee that the float service capacity of Group 2 can be fully utilized when some jobs are taken from the buffer to Group 2, we assume that $m_3\ge m_2$, i.e., the capacity of the buffer must be no less than the server number of Group 2. Otherwise, if there are more jobs waiting in the buffer, the jobs transferred from Group 2 to the buffer will be lost.

Arrival processes: The arrivals of jobs at the data center are a Poisson process with arrival rate $\lambda$. If the buffer is full, then any arriving job has to be lost immediately. This leads to an opportunity cost $C_5$ per unit of time for each lost job due to the full buffer.

Service processes: The service times provided by each server in Groups 1 and 2 are i.i.d. and exponential with service rates ${\mu }_1$ and ${\mu }_2$, respectively. We assume that ${\mu }_1\ge {\mu }_2,$ which makes the prior use of servers in Group 1. The service discipline of each server in the data center is First Come First Serve (FCFS). If a job finishes its service at a server, then it immediately leaves the system. At the same time, the data center can obtain a fixed service reward (or service price) $R$ from the served job.

Once a job enters the data center for its service, it has to pay holding costs per unit of time $C_2^{\left(1\right)},C_2^{\left(2\right)}$, and $C_2^{\left(3\right)}$ in Group 1, Group 2, and the buffer, respectively. We assume that $C_2^{\left(1\right)}\le C_2^{\left(2\right)}$ also guarantees the prior use of servers in Group 1. Therefore, to support the service priority, each server in Group 1 is not only faster but also cheaper than that in Group 2.

Switching between work and sleep: To save energy, the servers in Group 2 can switch between the work and sleep states. On the one hand, if there are more jobs waiting in the buffer, then Group 2 sets up and turns on some sleeping servers. This process usually involves a setup cost $C_3^{\left(1\right)}.$ However, the setup time is very short as it directly begins from the sleep state and it can be ignored. On the other hand, if the number of jobs in Group 2 is smaller, then the working servers are switched to the sleep state, while the incomplete-service jobs are transferred to the buffer and served as the arriving ones.

Transfer rules: (1) To Group 1. Based on the prior use of servers in Group 1, if a server in Group 1 becomes idle and there is no job in the buffer, then an incomplete-service job (if it exists) in Group 2 must immediately be transferred to the idle server in Group 1. Additionally, the data center needs to pay a transferred cost $C_4$ to the transferred job.

(2) To the buffer. If some servers in Group 2 are closed to the sleep state, then those jobs in the servers closed at the sleep state are transferred to the buffer, and a transferred cost $C_3^{\left(2\right)}$ is paid by the data center.

To keep the transferred jobs that can enter the buffer, we need to control the new jobs arriving at the buffer. If the sum of the job number in the buffer and the job number in Group 2 is equal to $m_3$, then the newly arriving jobs must be lost immediately.

Power Consumption: The power consumption rates $P_{1,W}$ and $P_{2,W}$ are for the work states of servers in Groups 1 and 2, respectively, while $P_{2,S}$ is only for the sleep state of a server in Group 2. Note that each server in Group 1 does not have the sleep state and it is clear that $P_{1,S}=0$. We assume that $0<P_{2,S}<$ $P_{2,W}$. There is no power consumption for keeping the jobs in the buffer. $C_1$ is the power consumption price per unit of the power consumption rate and per unit of time.

Independence: We assume that all the random variables in the data center defined above are independent.

Finally, to aid reader understanding, the data center, together with its operational mode and mathematical notations, is depicted in Figure 1.

Table 1. Cost notation in the data center.

Cost	Necessary Interpretation
$C_1$	The power consumption price
$C_2^{\left(1\right)}$	The holding cost for a job in Group 1 per unit of sojourn time
$C_2^{\left(2\right)}$	The holding cost for a job in Group 2 per unit of sojourn time
$C_2^{\left(3\right)}$	The holding cost for a job in the buffer per unit of sojourn time
$C_3^{\left(1\right)}$	The setup cost for a server switching from the sleep state to the work state
$C_3^{\left(2\right)}$	The transferred cost for a incomplete-service job returning to the buffer
$C_4$	The transferred cost for a job in Group 2 is transferred to Group 1
$C_5$	The opportunity cost for each lost job
R	The service price from the served job

summarizes some notations involved in the model. This will be helpful in our later study.

In the remainder of this section, it might be useful to provide some comparison of the above model assumptions with those in Ma et al. [31] and in Xia et al. [35].

Remark 1.

(1) Compared with our previous paper [31], this paper considers several new practical factors, such as a finite buffer, a fast setup process, and a job transfer rule. The new factors make our MDP modeling more practical and useful in the study of energy-efficient data centers. Although the new factors do not increase any difficulty in performance evaluation through modeling by means of queueing systems or Markov processes, they can cause substantially more difficulties and challenges in finding optimal dynamic energy-efficient policies and, furthermore, in determining threshold-type policies by using the sensitivity-based optimization. Note that the difficulties mainly grow out of establishing the policy-based block-structured Markov process and solving the block-structured Poisson equation. On this occasion, we have simplified the above model descriptions: for example, the setup is immediate, the jobs can be transferred without delay either between the slow and fast servers or between the slow servers and the buffer, the jobs must be transferred as soon as the fast server becomes free, the finite buffer space is reserved for jobs in progress, and so on.

(2) For the energy-efficient data center operating with some buffer, it is seen from Figure A3 in Appendix B that the main challenge of our work is to focus on how to describe the policy-based block-structured Markov process. Obviously, (a) if there are more than two groups of servers, then it is easy to check that the policy-based Markov process will become multi-dimensional so that its analysis is very difficult; (b) if the buffer is infinite, then we have to deal with the policy-based block-structured Markov process with infinitely many levels, for which the discussion and computation are very complicated.

Remark 2.

Compared with Xia et al. [35], this paper introduces a more detailed cost and reward structure, which makes analysis for the monotonicity and optimality of the dynamic energy-efficient policies more difficult and challenging. Therefore, many cost and reward factors make the MDP analysis and the sensitivity-based optimization more complicated.

3. Optimization Model Formulation

In this section, for the energy-efficient data center, we first establish a policy-based continuous-time Markov process with a finite block structure. Then, we define a suitable reward function with respect to both states and policies of the Markov process. Note that this will be helpful and useful for setting up a MDP to find the optimal asynchronous dynamic policy in the energy-efficient data center.

3.1. A Policy-Based Block-Structured Continuous-Time Markov Process

The data center in Figure 1 shows Group 1 of $m_1$ servers, Group 2 of $m_2$ servers, and a buffer of size $m_3$. We need to introduce both “states” and “policies” to express the stochastic dynamics of this data center. Let $N_1\left(t\right),N_2\left(t\right)$, and $N_3\left(t\right)$ be the numbers of jobs in Group 1, Group 2, and the buffer, respectively. Therefore, $\left(N_1\left(t\right),N_2\left(t\right),N_3\left(t\right)\right)$ is regarded as a state of the data center at time t. Let all the cases of such a state $\left(N_1\left(t\right),N_2\left(t\right),N_3\left(t\right)\right)$ form a set as follows:

$${\Omega =\Omega }_0\cup {\Omega }_1\cup {\Omega }_2\cup {\cdots \cup \Omega }_{m_2}\cup {\Omega }_{m_2+1}\cup {\Omega }_{m_2+2},$$

where

$$\begin{array}{cc}\hfill {\Omega }_0& =\left\{\left(0,0,0\right),\left(1,0,0\right),\dots ,\left(m_1,0,0\right)\right\},\hfill \\ \hfill {\Omega }_1& =\left\{\left(m_1,0,1\right),\left(m_1,0,2\right),\dots ,\left(m_1,0,m_3\right)\right\},\hfill \\ \hfill {\Omega }_2& =\left\{\left(m_1,1,0\right),\left(m_1,1,1\right),\dots ,\left(m_1,1,m_3-1\right)\right\},\hfill \\ & ⋮\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ \hfill {\Omega }_{m_2}& =\left\{\left(m_1,m_2-1,0\right),\left(m_1,m_2-1,1\right),\dots ,\left(m_1,m_2-1,m_3-m_2+1\right)\right\},\hfill \\ \hfill {\Omega }_{m_2+1}& =\left\{\left(m_1,m_2,0\right),\left(m_1,m_2,1\right),\dots ,\left(m_1,m_2,m_3-m_2\right)\right\},\hfill \\ \hfill {\Omega }_{m_2+2}& =\left\{\left(m_1,m_2,m_3-m_2+1\right),\left(m_1,m_2,m_3-m_2+2\right),\dots ,\left(m_1,m_2,m_3\right)\right\}.\hfill \end{array}$$

For a state $\left(n_1,n_2,n_3\right),$ it is seen from the model description that there are four different cases: (a) By using the transfer rules, if $n_1=0,1,\dots ,m_1-1$, then $n_2=n_3=0;$ if either $n_2\ne 0$ or $n_3\ne 0$, then $n_1=m_1$. (b) If $n_1=m_1$ and $n_2=0,$ then the jobs in the buffer can increase until the waiting room is full, i.e., $n_3=1,2,\dots ,m_3.$ (c) If $n_1=m_1$ and $n_2=1,2,\dots ,m_2-1,$ then the total numbers of jobs in Group 2 and the buffer are no more than the buffer size, i.e., $n_2+n_3\le m_3.$ (d) If $n_1=m_1$ and $n_2=m_2,$ then the jobs in the buffer can also increase until the waiting room is full, i.e., $n_3=1,2,\dots ,m_3.$

Now, for Group 2, we introduce an asynchronous dynamic policy, which is related to two dynamic actions (or sub-policies): from sleep to work (setup) and from work to sleep (close). Let $d_{n_1,n_2,n_3}^W$ and $d_{n_1,n_2,n_3}^S$ be the numbers of working servers and of sleeping servers in Group 2 at State $\left(n_1,n_2,n_3\right)$, respectively. By observing the state set $\Omega$, we call ${\mathit{d}}^W$ and ${\mathit{d}}^S$ the setup policy (i.e., from sleep to work) and the sleep policy (i.e., from work to sleep), respectively.

Note that the servers in Group 2 can only be set up when all of them are idle, while we cannot simultaneously have the setup policy (${\mathit{d}}^W$) because the servers in Group 2 are always affected by the sleep policy (${\mathit{d}}^S$) if they still work for some jobs. This is what we call asynchronous dynamic policies. Here, we consider the control optimization of the total system. For such sub-policies, we provide an interpretation of four different cases as follows:

(1) In ${\Omega }_0,$ if $n_1=0,1,\dots ,m_1-1$, then $n_2=n_3=0$ due to the transfer rule. Thus, there are no jobs in Group 2 or in the buffer, so that no policy in Group 2 is used;

(2) In ${\Omega }_1,$ the states will affect how to use the setup policy. If $n_1=m_1$, $n_2=0$, $n_3=1,2,\dots ,m_3,$ then $d_{m_1,0,n_3}^W$ is the number of working servers in Group 2 at State $\left(m_1,0,n_3\right)$. Note that some of the slow servers need to first start, so that some jobs in the buffer can enter the activated slow servers, thus, $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,m_2\right\}$, each of which can possibly take place under an optimal dynamic policy;

(3) From ${\Omega }_2$ to ${\Omega }_{m_2+1},$ the states will affect how to use the sleep policy. If $n_1=m_1$, $n_2=1,2,\dots ,m_2$, $n_3=0,1,\dots ,m_3-n_2,$ then $d_{m_1,n_2,n_3}^S$ is the number of sleeping servers in Group 2 at State $\left(m_1,n_2,n_3\right).$ We assume that the number of sleeping servers is no less than $m_2-n_2$. Note that the sleep policy is independent of the work policy. Once the sleep policy is set up, the servers without jobs must enter the sleep state. At the same time, some working servers with jobs are also closed to the sleep state, and the jobs in those working servers are transferred to the buffer. It is easy to see that $d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\};$

(4) In ${\Omega }_{m_2+2},$ if $n_1=m_1$ and $n_2=m_2$, then $n_3$ may be any element in the set $\left\{m_3 - m_2 + 1,\right.$$\left.m_3 - m_2 + 2,\dots ,m_3\right\},$ it is clear that $n_2+n_3>m_3.$

Our aim is to determine when or under what conditions an optimal number of servers in Group 2 switch between the sleep state and the work state such that the long-run average profit of the data center is maximal. From the state space $\Omega$, we define an asynchronous dynamic energy-efficient policy $\mathit{d}$ as

$$\mathit{d}={\mathit{d}}^W⊠{\mathit{d}}^S,$$

(1)

where ${\mathit{d}}^W$ and ${\mathit{d}}^S$ are the setup and sleep policies, respectively; ‘⊠’ denotes that the policies ${\mathit{d}}^W$ and ${\mathit{d}}^S$ occur asynchronously; and

$$\begin{array}{cc}\hfill {\mathit{d}}^W& =\left(d_{m_1,0,1}^W,d_{m_1,0,2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \\ \hfill {\mathit{d}}^S& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,1,m_3-1}^S; d_{m_1,2,0}^S,d_{m_1,2,1}^S,\dots ,d_{m_1,2,m_3-2}^S;\dots ;\right.\hfill \\ & \hspace{1em}\left.d_{m_1,m_2,0}^S,d_{m_1,m_2,1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right).\hfill \end{array}$$

Note that ${\mathit{d}}^W$ is related to the fact that if there is no job in Group 2 at the initial time, then all the servers in Group 2 are at the sleep state. Once there are jobs in the buffer, we quickly set up some servers in Group 2 such that they enter the work state to serve the jobs. Similarly, we can understand the sleep policy ${\mathit{d}}^S.$ In the state subset ${\bigcup }_{i=2}^{m_2+2}{\Omega }_i,$ it is seen that the setup policy ${\mathit{d}}^W$ will not be needed because some servers are kept at the work state.

For all the possible policies $\mathit{d}$ given in (1), we compose a policy space as follows:

$$\begin{array}{cc}\hfill \mathcal{D}& :=\left\{\mathit{d}={\mathit{d}}^W⊠{\mathit{d}}^S:d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,m_2\right\} \mathrm{for} 1\le n_3\le m_3;\right.\hfill \\ & \hspace{1em}\left.d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\} \mathrm{for} \left(m_1,n_2,n_3\right)\in {\Omega }_2\cup {\Omega }_3\cup \cdots \cup {\Omega }_{m_2+1}\right\}.\hfill \end{array}$$

Let ${\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right)={\left(N_1\left(t\right),N_2\left(t\right),N_3\left(t\right)\right)}^{\left(\mathit{d}\right)}$ for any given policy $\mathit{d}\in \mathcal{D}$. Then $\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\}$ is a policy-based block-structured continuous-time Markov process on the state space $\Omega$ whose state transition relations are given in Figure A3 in Appendix B (we provide two simple special cases to understand such a policy-based block-structured continuous-time Markov process in Appendix A). Based on this, the infinitesimal generator of the Markov process $\left\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\right\}$ is given by

$${\mathbf{Q}}^{\left(\mathit{d}\right)}=\left(\begin{array}{cccccccc}{Q}_{0,0}& Q_{0,1}& & & & & & \\ Q_{1,0}& Q_{1,1}& Q_{1,2}& Q_{1,3}& Q_{1,4}& \cdots & Q_{1,m_2+1}& \\ Q_{2,0}& Q_{2,1}& Q_{2,2}& & & & & \\ & Q_{3,1}& Q_{3,2}& Q_{3,3}& & & & \\ & Q_{4,1}& Q_{4,2}& Q_{4,3}& Q_{4,4}& & & \\ & ⋮& ⋮& ⋮& ⋮& \ddots & & \\ & Q_{m_2+1,1}& Q_{m_2+1,2}& Q_{m_2+1,3}& Q_{m_2+1,4}& \cdots & Q_{m_2+1,m_2+1}& Q_{m_2+1,m_2+2}\\ & & & & & & Q_{m_2+2,m_2+1}& Q_{m_2+2,m_2+2}\end{array}\right),$$

(2)

where every block element $Q_{i,j}$ depends on the policy $\mathit{d}$ (for simplification of description, here we omit “$\mathit{d}$”) and it is expressed in Appendix C.

It is easy to see that the infinitesimal generator ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ has finite states, and it is irreducible with ${\mathbf{Q}}^{\left(\mathit{d}\right)}\mathit{e}=\mathbf{0}$, thus, the Markov process ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ is a positive recurrent. In this case, we write the stationary probability vector of the Markov process $\left\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\right\}$ as

$${\mathbf{\pi }}^{\left(\mathit{d}\right)}=\left({\pi }_0^{\left(\mathit{d}\right)},{\pi }_1^{\left(\mathit{d}\right)},\dots ,{\pi }_{m_2+2}^{\left(\mathit{d}\right)}\right), \mathit{d}\in \mathcal{D},$$

(3)

where

$$\begin{array}{cc}\hfill {\mathbf{\pi }}_0^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(0,0,0\right),{\pi }^{\left(\mathit{d}\right)}\left(1,0,0\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,0\right)\right),\hfill \\ \hfill {\mathbf{\pi }}_1^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(m_1,0,1\right),{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,2\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,m_3\right)\right),\hfill \\ \hfill {\mathbf{\pi }}_2^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(m_1,1,0\right),{\pi }^{\left(\mathit{d}\right)}\left(m_1,1,1\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,1,m_3-1\right)\right),\hfill \\ & ⋮\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ \hfill {\mathbf{\pi }}_{m_2}^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2-1,0\right),{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2-1,1\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2-1,m_3-m_2+1\right)\right),\hfill \\ \hfill {\mathbf{\pi }}_{m_2+1}^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,0\right),{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,1\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2\right)\right),\hfill \\ \hfill {\mathbf{\pi }}_{m_2+2}^{\left(\mathit{d}\right)}& =\left({\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2+1\right),{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2+2\right),\dots ,{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3\right)\right).\hfill \end{array}$$

Note that the stationary probability vector ${\mathbf{\pi }}^{\left(\mathit{d}\right)}$ can be obtained by means of solving the system of linear equations ${\mathbf{\pi }}^{\left(\mathit{d}\right)}{\mathbf{Q}}^{\left(\mathit{d}\right)}=\mathbf{0}$ and ${\mathbf{\pi }}^{\left(\mathit{d}\right)}\mathit{e}=1,$ where $\mathit{e}$ is a column vector of the ones with a suitable size. To this end, the RG-factorizations play an important role in our later computation. Note that some computational details are given in Chapter 2 in Li [33].

Now, we use UL-type RG-factorization to compute the stationary probability vector ${\mathbf{\pi }}^{\left(\mathit{d}\right)}$ as follows. For $0\le i,j\le k$ and $0\le k\le m_2+2$, we write

$$Q_{i,j}^{\left[\le k\right]}=Q_{i,j}+\stackrel{m_2+2}{\sum _{n=k+1}}{Q}_{i,n}^{\left[\le n\right]}{\left\{-Q_{n,n}^{\left[\le n\right]}\right\}}^{-1}{Q}_{n,j}^{\left[\le n\right]}.$$

Clearly, $Q_{i,j}^{\left[\le m_2+2\right]}=Q_{i,j}$ and $Q_{i,j}^{\left[\le 0\right]}=Q_{i,j}^{\left[0\right]}$. Let

$$\begin{array}{cc}{U}_n^{\left(\mathit{d}\right)}=Q_{n,n}^{\left[\le n\right]},\hfill & 0\le n\le m_2+2,\hfill \\ R_{i,j}^{\left(\mathit{d}\right)}=Q_{i,j}^{\left[\le j\right]}{\left(-U_j^{\left(\mathit{d}\right)}\right)}^{-1},\hfill & 0\le i<j\le m_2+2,\hfill \end{array}$$

and

$$\begin{array}{cc}{G}_{i,j}^{\left(\mathit{d}\right)}={\left(-U_i^{\left(\mathit{d}\right)}\right)}^{-1}{Q}_{i,j}^{\left[\le i\right]},\hfill & 0\le j<i\le m_2+2.\hfill \end{array}$$

Then the UL-type RG-factorization is given by

$${\mathbf{Q}}^{\left(\mathit{d}\right)}=\left(I-{\mathbf{R}}_U^{\left(\mathit{d}\right)}\right)\left(I-{\mathbf{U}}_D^{\left(\mathit{d}\right)}\right)\left(I-{\mathbf{G}}_L^{\left(\mathit{d}\right)}\right),$$

where

$${\mathbf{R}}_U^{\left(\mathit{d}\right)}=\left(\begin{array}{cccccc}0& R_{0,1}^{\left(\mathit{d}\right)}& R_{0,2}^{\left(\mathit{d}\right)}& \cdots & R_{0,m_2+1}^{\left(\mathit{d}\right)}& R_{0,m_2+2}^{\left(\mathit{d}\right)}\\ & 0& R_{1,2}^{\left(\mathit{d}\right)}& \cdots & R_{1,m_2+1}^{\left(\mathit{d}\right)}& R_{1,m_2+2}^{\left(\mathit{d}\right)}\\ & & 0& \ddots & ⋮& ⋮\\ & & & 0& R_{m_2,m_2+1}^{\left(\mathit{d}\right)}& R_{m_2,m_2+2}^{\left(\mathit{d}\right)}\\ & & & & 0& R_{m_2+1,m_2+2}^{\left(\mathit{d}\right)}\\ & & & & & 0\end{array}\right),$$

$${\mathbf{U}}_D^{\left(\mathit{d}\right)}=\mathrm{diag}\left(U_0^{\left(\mathit{d}\right)},U_1^{\left(\mathit{d}\right)},\dots ,U_{m_2+1}^{\left(\mathit{d}\right)},U_{m_2+2}^{\left(\mathit{d}\right)}\right)$$

and

$${\mathbf{G}}_L^{\left(\mathit{d}\right)}=\left(\begin{array}{cccccc}0& & & & & \\ G_{1,0}^{\left(\mathit{d}\right)}& 0& & & & \\ G_{2,0}^{\left(\mathit{d}\right)}& G_{2,1}^{\left(\mathit{d}\right)}& 0& & & \\ G_{3,0}^{\left(\mathit{d}\right)}& G_{3,1}^{\left(\mathit{d}\right)}& G_{3,2}^{\left(\mathit{d}\right)}& 0& & \\ ⋮& ⋮& ⋮& \ddots & \ddots & \\ G_{m_2+2,0}^{\left(\mathit{d}\right)}& G_{m_2+2,1}^{\left(\mathit{d}\right)}& G_{m_2+2,2}^{\left(\mathit{d}\right)}& \cdots & G_{m_2+2,m_2+1}^{\left(\mathit{d}\right)}& 0\end{array}\right).$$

By using Theorem 2.9 of Chapter 2 in Li [33], the stationary probability vector of the Markov process ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ is given by

$$\left\{\begin{array}{c}{\mathbf{\pi }}_0^{\left(\mathit{d}\right)}={\tau }^{\left(\mathit{d}\right)}{x}_0^{\left(\mathit{d}\right)},\hfill \\ {\mathbf{\pi }}_k^{\left(\mathit{d}\right)}={\displaystyle \sum _{i=0}^{k-1}}{\mathbf{\pi }}_i^{\left(\mathit{d}\right)}{R}_{i,k}^{\left(\mathit{d}\right)},\hspace{1em}1\le k\le m_2+2,\hfill \end{array}\right.$$

where $x_{0 }^{\left(\mathit{d}\right)}$ is the stationary probability vector of the censored Markov chain $U_0^{\left(\mathit{d}\right)}$ to level 0, and the positive scalar ${\tau }^{\left(\mathit{d}\right)}$ is uniquely determined by ${\displaystyle \sum _{k=0}^{m_2+2}}{\mathbf{\pi }}_k^{\left(\mathit{d}\right)}\mathit{e}=1.$

Remark 3.

The RG-factorizations provide a unified, constructive and algorithmic framework for the numerical computation of many practical stochastic systems. It can be applied to provide effective solutions for the block-structured Markov processes, and are shown to be also useful for the optimal design and dynamical decision-making of many practical systems. See more details in Li [33].

The following theorem provides some useful observations on some special policies ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$, in which the special policies will have no effect on the infinitesimal generator ${\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}$ or the stationary probability vector ${\mathbf{\pi }}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}$.

Theorem 1.

Suppose that two asynchronous energy-efficient policies ${\mathit{d}}^{W_1}⊠{\mathit{d}}^S,{\mathit{d}}^{W_2}⊠{\mathit{d}}^S\in \mathcal{D}$ satisfy one of the following two conditions: $\left(a\right)$ for each $n_3=1,2,\dots ,m_2$, if $d_{m_1,0,n_3}^{W_1}\in \left\{n_3,n_3+1,\dots ,m_2\right\}$, then we take $d_{m_1,0,n_3}^{W_2}$ as any element of the set $\left\{1,2,\dots ,m_2\right\}$; $\left(b\right)$ for each $n_3=m_2+1,m_2+2,\dots ,m_3,$ if $d_{m_1,0,n_3}^{W_1}\in \left\{1,2,\dots ,m_2\right\}$, then we take $d_{m_1,0,n_3}^{W_2}=d_{m_1,0,n_3}^{W_1}.$ Under both such conditions, we have

$${\mathbf{Q}}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}={\mathbf{Q}}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)}, {\mathbf{\pi }}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}={\mathbf{\pi }}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)}.$$

Proof of Theorem 1.

It is easy to see from (2) that all the levels of the matrix ${\mathbf{Q}}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}$ are the same as those of the matrix ${\mathbf{Q}}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)}$, except level 1. Thus, we only need to compare level 1 of the matrix ${\mathbf{Q}}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}$ with that of the matrix ${\mathbf{Q}}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)}$.

For the two asynchronous energy-efficient policies ${\mathit{d}}^{W_1}⊠{\mathit{d}}^S,{\mathit{d}}^{W_2}⊠{\mathit{d}}^S\in \mathcal{D}$ satisfying the conditions (a) and (b), by using $1_{\left\{d_{m_1,0,n_3}^W\ge n_3\right\}}$ in (2), it is clear that for $n_3=1,2,\dots ,m_2$, if $d_{m_1,0,n_3}^{W_1},d_{m_1,0,n_3}^{W_2}\in \left\{n_3,n_3+1,\dots ,m_2\right\}$, then

$$1_{\left\{d_{m_1,0,n_3}^{W_1}\ge n_3\right\}}=1_{\left\{d_{m_1,0,n_3}^{W_2}\ge n_3\right\}}.$$

Thus, it follows from (2) that $Q_{1,k}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}=Q_{1,k}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)},k=1,2,\dots ,m_2+1.$ This also gives that ${\mathbf{Q}}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}={\mathbf{Q}}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)},$ and thus ${\mathbf{\pi }}^{\left({\mathit{d}}^{W_1}⊠{\mathit{d}}^S\right)}={\mathbf{\pi }}^{\left({\mathit{d}}^{W_2}⊠{\mathit{d}}^S\right)}.$ This completes the proof. □

Note that Theorem 1 will be necessary and useful for analyzing the policy monotonicity and optimality in our later study. Furthermore, see the proof of Theorem 4.

Remark 4.

This paper is the first to introduce and consider the asynchronous dynamic policy in the study of energy-efficient data centers. We highlight the impact of the two asynchronous sub-policies: the setup and sleep policies on the long-run average profit of the energy-efficient data center.

3.2. The Reward Function

For the Markov process ${\mathbf{Q}}^{\left(\mathit{d}\right)}$, now we define a suitable reward function for the energy-efficient data center.

Based on the above costs and price notations in Table 1, a reward function with respect to both states and policies is defined as a profit rate (i.e., the total revenues minus the total costs per unit of time). Therefore, according to the impact of the asynchronous dynamic policy on the profit rate, the reward function at State $\left(n_1,n_2,n_3\right)$ under policy $\mathit{d}$ is divided into four cases as follows:

Case (a): For $n_1=0,1,\dots ,m_1$ and $n_2=n_3=0$, the profit rate is not affected by any policy, and we have

$$f\left(n_1,0,0\right)=R{n}_1{\mu }_1-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1-n_1{C}_2^{\left(1\right)}.$$

(4)

Note that in Case (a), there is no job in Group 2 or in the buffer. Thus, it is clear that each server in Group 2 is at the sleep state.

However, in the following two cases (b) and (c), since there are some jobs either in Group 2 or in the buffer, the policy $\mathit{d}$ will play a key role in opening (i.e., setup) or closing (i.e., sleep) some servers of Group 2 to save energy efficiently.

Case (b): For $n_1=m_1$, $n_2=0$ and $n_3=1,2,\dots ,m_3,$ the profit rate is affected by the setup policy ${\mathit{d}}^W$, we have

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^W\right)}\left(m_1,0,n_3\right)& =R{m}_1{\mu }_1-\left[m_1{P}_{1,W}+d_{m_1,0,n_3}^W{P}_{2,W}+\left(m_2-d_{m_1,0,n_3}^W\right)P_{2,S}\right]C_1\hfill \\ & -\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right]-d_{m_1,0,n_3}^W{C}_3^{\left(1\right)}-\lambda 1_{\left\{n_1=m_1,n_2=0,n_3=m_3\right\}}{C}_5,\hfill \end{array}$$

(5)

where $1_{\{·\}}$ is an indicator function whose value is 1 when the event is in $\{·\}$, otherwise its value is 0.

Case (c): For $n_1=m_1$, $n_2=1,2,\dots ,m_2$ and $n_3=0,1,\dots ,m_3-n_2$, the profit rate is affected by the sleep policy ${\mathit{d}}^S$, we have

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)& =R\left[m_1{\mu }_1+\left(m_2-d_{m_1,n_2,n_3}^S\right){\mu }_2\right]\hfill \\ & \hspace{1em}-\left[m_1{P}_{1,W}+d_{m_1,n_2,n_3}^S{P}_{2,S}+\left(m_2-d_{m_1,n_2,n_3}^S\right)P_{2,W}\right]C_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]-\left[n_2-\left(m_2-d_{m_1,n_2,n_3}^S\right)\right]C_3^{\left(2\right)}\hfill \\ & -m_1{\mu }_1{1}_{\left\{n_2>0,n_3=0\right\}}{C}_4-\lambda 1_{\left\{n_1=m_1,n_2+n_3=m_3\right\}}{C}_5.\hfill \end{array}$$

(6)

Note that the job transfer rate from Group 2 to Group 1 is given by $n_1{\mu }_1{1}_{\{n_2>0,n_3=0\}}$. If $0\le n_1\le m_1-1$, then $n_2=0$ and $n_1{\mu }_1{1}_{\{n_2>0,n_3=0\}}{C}_4=0$. If $n_1=m_1$ and $n_2=0$, then $n_1{\mu }_1{1}_{\{n_2>0,n_3=0\}}{C}_4=0$. If $n_1=m_1,1\le n_2\le m_2$ and $n_3=0$, then $n_1{\mu }_1{1}_{\{n_2>0,n_3=0\}}{C}_4=m_1{\mu }_1{C}_4$.

Case (d): For $n_1=m_1$, $n_2=m_2$ and $n_3=m_3-m_2+1,m_3-m_2+2,\dots ,m_3$, the profit rate is not affected by any policy, we have

$$\begin{array}{cc}\hfill f\left(m_1,m_2,n_3\right)& =R\left(m_1{\mu }_1+m_2{\mu }_2\right)-\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+m_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]-\lambda 1_{\left\{n_1=m_1,n_2=m_2,n_3=m_3\right\}}{C}_5.\hfill \end{array}$$

(7)

We define a column vector composed of the elements $f\left(n_1,n_2,n_3\right)$, $f^{\left({\mathit{d}}^W\right)}\left(n_1,n_2,n_3\right)$ and $f^{\left({\mathit{d}}^S\right)}\left(n_1,n_2,n_3\right)$ as

$${\mathit{f}}^{\left(\mathit{d}\right)}={\left({\left({\mathit{f}}_0\right)}^T,{\left({\mathit{f}}_1^{\left({\mathit{d}}^W\right)}\right)}^T,{\left({\mathit{f}}_2^{\left({\mathit{d}}^S\right)}\right)}^T,\dots ,{\left({\mathit{f}}_{m_2+1}^{\left({\mathit{d}}^S\right)}\right)}^T,{\left({\mathit{f}}_{m_2+2}\right)}^T\right)}^T,$$

(8)

where

$$\begin{array}{cc}\hfill {\mathit{f}}_0& ={\left(f\left(0,0,0\right),f\left(1,0,0\right),\dots ,f\left(m_1,0,0\right)\right)}^T,\hfill \\ \hfill {\mathit{f}}_1^{\left({\mathit{d}}^W\right)}& ={\left(f^{\left({\mathit{d}}^W\right)}\left(m_1,0,1\right),f^{\left({\mathit{d}}^W\right)}\left(m_1,0,2\right),\dots ,f^{\left({\mathit{d}}^W\right)}\left(m_1,0,m_3\right)\right)}^T,\hfill \\ \hfill {\mathit{f}}_2^{\left({\mathit{d}}^S\right)}& ={\left(f^{\left({\mathit{d}}^S\right)}\left(m_1,1,0\right),f^{\left({\mathit{d}}^S\right)}\left(m_1,1,1\right),\dots ,f^{\left({\mathit{d}}^S\right)}\left(m_1,1,m_3-1\right)\right)}^T,\hfill \\ & ⋮\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ \hfill {\mathit{f}}_{m_2+1}^{\left({\mathit{d}}^S\right)}& ={\left(f^{\left({\mathit{d}}^S\right)}\left(m_1,m_2,0\right),f^{\left({\mathit{d}}^S\right)}\left(m_1,m_2,1\right),\dots ,f^{\left({\mathit{d}}^S\right)}\left(m_1,m_2,m_3-m_2\right)\right)}^T,\hfill \\ \hfill {\mathit{f}}_{m_2+2}& ={\left(f\left(m_1,m_2,m_3-m_2+1\right),f\left(m_1,m_2,m_3-m_2+2\right),\dots ,f\left(m_1,m_2,m_3\right)\right)}^T.\hfill \end{array}$$

In the remainder of this section, the long-run average profit of the data center (or the policy-based continuous-time Markov process $\left\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\right\}$) under an asynchronous dynamic policy $\mathit{d}$ is defined as

$${\eta }^{\mathit{d}}=\underset{T\to +\infty }{lim}E\left\{\frac{1}{T}{\int }_0^T{f}^{\left(\mathit{d}\right)}\left({\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right)\right)\mathrm{d}t\right\}={\mathbf{\pi }}^{\left(\mathit{d}\right)}{\mathit{f}}^{\left(\mathit{d}\right)},$$

(9)

where ${\mathbf{\pi }}^{\left(\mathit{d}\right)}$ and ${\mathit{f}}^{\left(\mathit{d}\right)}$ are given by (3) and (8), respectively.

We observe that as the number of working servers in Group 2 decreases, the total revenues and the total costs in the data center will decrease synchronously, and vice versa. On the other hand, as the number of sleeping servers in Group 2 increases, the total revenues and the total costs in the data center will decrease synchronously, and vice versa. Thus, there is a tradeoff between the total revenues and the total costs for a suitable number of working and/or sleeping servers in Group 2 by using the setup and sleep policies, respectively. This motivates us to study an optimal dynamic control mechanism for the energy-efficient data center. Thus, our objective is to find an optimal asynchronous dynamic policy ${\mathit{d}}^{*}$ such that the long-run average profit ${\eta }^{\mathit{d}}$ is maximized, that is,

$${\mathit{d}}^{*}=\underset{\mathit{d}\in \mathcal{D}}{argmax}\left\{{\eta }^{\mathit{d}}\right\}.$$

(10)

Since the setup and sleep policies ${\mathit{d}}^W$ and ${\mathit{d}}^S$ occur asynchronously, they cannot interact with each other at any time. Therefore, it is seen that the optimal policy can be decomposed into

$${\mathit{d}}^{*}={\mathit{d}}^{W^{*}}⊠{\mathit{d}}^{S^{*}}=\underset{{\mathit{d}}^W\in \mathcal{D}}{argmax}\left\{{\eta }^{{\mathit{d}}^W}\right\}⊠\underset{{\mathit{d}}^S\in \mathcal{D}}{argmax}\left\{{\eta }^{{\mathit{d}}^S}\right\}.$$

In fact, it is difficult and challenging to analyze the properties of the optimal asynchronous dynamic policy ${\mathit{d}}^{*}={\mathit{d}}^{W^{*}}⊠{\mathit{d}}^{S^{*}}$, and to provide an effective algorithm for computing the optimal policy ${\mathit{d}}^{*}$. To do this, in the next sections we will introduce the sensitivity-based optimization theory to study this energy-efficient optimization problem.

4. The Block-Structured Poisson Equation

In this section, for the energy-efficient data center, we set up a block-structured Poisson equation which provides a useful relation between the sensitivity-based optimization and the MDP. Additionally, we use the RG-factorization, given in Li [33], to solve the block-structured Poisson equation and provide an expression for its unique solution.

For $\mathit{d}\in \mathcal{D}$, it follows from Chapter 2 in Cao [34] that for the policy-based continuous-time Markov process $\left\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\right\}$, we define the performance potential as

$$g^{\left(\mathit{d}\right)}\left(n_1,n_2,n_3\right)=E\left\{\left.{\int }_0^{+\infty }\left[f^{\left(\mathit{d}\right)}\left({\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right)\right)-{\eta }^{\mathit{d}}\right]\mathrm{d}t\right|{\mathbf{X}}^{\left(\mathit{d}\right)}\left(0\right)=\left(n_1,n_2,n_3\right)\right\},$$

(11)

where ${\eta }^{\mathit{d}}$ is defined in (9). It is seen from Cao [34] that for any policy $\mathit{d}\in \mathcal{D}$, $g^{\left(\mathit{d}\right)}\left(n_1,n_2,n_3\right)$ quantifies the contribution of the initial state $\left(n_1,n_2,n_3\right)$ to the long-run average profit of the data center. Here, $g^{\left(\mathit{d}\right)}\left(n_1,n_2,n_3\right)$ is also called the relative value function or the bias in the traditional Markov decision process theory, see, e.g., Puterman [39] for more details. We further define a column vector ${\mathit{g}}^{\left(\mathit{d}\right)}$ with elements $g^{\left(\mathit{d}\right)}\left(n_1,n_2,n_3\right)$ for $(n_1,n_2,n_3)\in \Omega$

$${\mathit{g}}^{\left(\mathit{d}\right)}={\left({\mathit{g}}_0^{\left(\mathit{d}\right)},{\mathit{g}}_1^{\left(\mathit{d}\right)},{\mathit{g}}_2^{\left(\mathit{d}\right)},\dots ,{\mathit{g}}_{m_2+1}^{\left(\mathit{d}\right)},{\mathit{g}}_{m_2+2}^{\left(\mathit{d}\right)}\right)}^T,$$

(12)

where

$$\begin{array}{cc}\hfill {\mathit{g}}_0^{\left(\mathit{d}\right)}& ={\left(g^{\left(\mathit{d}\right)}\left(0,0,0\right),g^{\left(\mathit{d}\right)}\left(1,0,0\right),\dots ,g^{\left(\mathit{d}\right)}\left(m_1,0,0\right)\right)}^T,\hfill \\ \hfill {\mathit{g}}_1^{\left(\mathit{d}\right)}& ={\left(g^{\left(\mathit{d}\right)}\left(m_1,0,1\right),g^{\left(\mathit{d}\right)}\left(m_1,0,2\right),\dots ,g^{\left(\mathit{d}\right)}\left(m_1,0,m_3\right)\right)}^T,\hfill \\ \hfill {\mathit{g}}_2^{\left(\mathit{d}\right)}& ={\left(g^{\left(\mathit{d}\right)}\left(m_1,1,0\right),g^{\left(\mathit{d}\right)}\left(m_1,1,1\right),\dots ,g^{\left(\mathit{d}\right)}\left(m_1,1,m_3-1\right)\right)}^T,\hfill \\ & ⋮\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ \hfill {\mathit{g}}_{m_2+1}^{\left(\mathit{d}\right)}& ={\left(g^{\left(\mathit{d}\right)}\left(m_1,m_2,0\right),g^{\left(\mathit{d}\right)}\left(m_1,m_2,1\right),\dots ,g^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2\right)\right)}^T,\hfill \\ \hfill {\mathit{g}}_{m_2+2}^{\left(\mathit{d}\right)}& ={\left(g^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2+1\right),g^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3-m_2+2\right),\dots ,g^{\left(\mathit{d}\right)}\left(m_1,m_2,m_3\right)\right)}^T.\hfill \end{array}$$

A similar computation to that in Ma et al. [31], the block-structured Poisson equation is given by

$${\mathbf{Q}}^{\left(\mathit{d}\right)}{\mathit{g}}^{\left(\mathit{d}\right)}={\eta }^{\mathit{d}}\mathit{e}-{\mathit{f}}^{\left(\mathit{d}\right)},$$

(13)

where ${\eta }^{\mathit{d}}$ is defined in (9), ${\mathit{f}}^{\left(\mathit{d}\right)}$ is given in (8), and ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ is given in (2).

To solve the system of linear equations (13), we note that rank $\left({\mathbf{Q}}^{\left(\mathit{d}\right)}\right)=m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3$ and $det\left({\mathbf{Q}}^{\left(\mathit{d}\right)}\right)=0$ because the size of the matrix ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ is $m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3+1$. Hence, this system (13) of linear equations exists with infinitely many solutions with a free constant of an additive term. Let $\stackrel{\sim }{\mathbf{Q}}$ be a matrix obtained through omitting the first row and the first column vectors of the matrix ${\mathbf{Q}}^{\left(\mathit{d}\right)}$. Then,

$${\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}=\left(\begin{array}{cccccccc}{\stackrel{\sim }{Q}}_{0,0}& {\stackrel{\sim }{Q}}_{0,1}& & & & & & \\ {\stackrel{\sim }{Q}}_{1,0}& Q_{1,1}& Q_{1,2}& Q_{1,3}& Q_{1,4}& \cdots & Q_{1,m_2+1}& \\ {\stackrel{\sim }{Q}}_{2,0}& Q_{2,1}& Q_{2,2}& & & & & \\ & Q_{3,1}& Q_{3,2}& Q_{3,3}& & & & \\ & Q_{4,1}& Q_{4,2}& Q_{4,3}& Q_{4,4}& & & \\ & ⋮& ⋮& ⋮& ⋮& \ddots & & \\ & Q_{m_2+1,1}& Q_{m_2+1,2}& Q_{m_2+1,3}& Q_{m_2+1,4}& \cdots & Q_{m_2+1,m_2+1}& Q_{m_2+1,m_2+2}\\ & & & & & & Q_{m_2+2,m_2+1}& Q_{m_2+2,m_2+2}\end{array}\right),$$

(14)

where

$${\stackrel{\sim }{Q}}_{0,0}=\left(\begin{array}{cccc}-\left(\lambda +{\mu }_1\right)& \lambda & & \\ 2{\mu }_1& -\left(\lambda +2{\mu }_1\right)& \lambda & \\ & \ddots \hspace{1em}\hspace{1em}& \ddots & \ddots \hspace{1em}\\ & \left(m_1-1\right){\mu }_1& -\left[\lambda +\left(m_1-1\right){\mu }_1\right]& \lambda \\ & & m_1{\mu }_1& -\left(\lambda +m_1{\mu }_1\right)\end{array}\right),$$

${\stackrel{\sim }{Q}}_{0,1}$ is obtained by means of omitting the first row vector of $Q_{0,1}$, ${\stackrel{\sim }{Q}}_{1,0}$ and ${\stackrel{\sim }{Q}}_{2,0}$ are obtained from omitting the first column vectors of $Q_{1,0}$ and $Q_{2,0}$, respectively. The other block entries in ${\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}$ are the same as the corresponding block entries in the matrix ${\mathbf{Q}}^{\left(\mathit{d}\right)}.$

Note that, rank $\left({\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)=$$m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3$ and the size of the matrix ${\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}$ is $m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3$. Hence, the matrix ${\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}$ is invertible.

Let ${\mathit{h}}^{\left(\mathit{d}\right)}$ and ${\mathbf{\phi }}^{\left(\mathit{d}\right)}$ be two column vectors of size $m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3$ obtained through omitting the first element of the two column vectors ${\mathit{f}}^{\left(\mathit{d}\right)}-{\eta }^{\mathit{d}}\mathit{e}$ and ${\mathit{g}}^{\left(\mathit{d}\right)}$ of size $m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3+1$, respectively, and

$$\begin{array}{cc}\hfill l_0& =m_1,\hfill \\ \hfill l_1& =m_1+m_3,\hfill \\ \hfill l_2& =m_1+2m_3,\hfill \\ & ⋮\hfill \\ \hfill l_{m_2+1}& =m_1+\frac{m_2}{2}-\frac{m_2^2}{2}+m_2{m}_3+m_3,\hfill \\ \hfill L& =m_1+\frac{3m_2}{2}-\frac{m_2^2}{2}+m_2{m}_3+m_3.\hfill \end{array}$$

Then,

$${\mathit{h}}^{\left(\mathit{d}\right)}=\left(\begin{array}{c}{\stackrel{\sim }{\mathit{f}}}_0-{\eta }^{\mathit{d}}\\ {\mathit{f}}_1^{\left({\mathit{d}}^W\right)}-{\eta }^{\mathit{d}}\\ {\mathit{f}}_2^{\left({\mathit{d}}^S\right)}-{\eta }^{\mathit{d}}\\ ⋮\\ {\mathit{f}}_{m_2+1}^{\left({\mathit{d}}^S\right)}-{\eta }^{\mathit{d}}\\ {\mathit{f}}_{m_2+2}-{\eta }^{\mathit{d}}\end{array}\right)\stackrel{\mathrm{def}}{=}\left(\begin{array}{c}{\mathit{h}}_0^{\left(\mathit{d}\right)}\\ {\mathit{h}}_1^{\left(\mathit{d}\right)}\\ {\mathit{h}}_2^{\left(\mathit{d}\right)}\\ ⋮\\ {\mathit{h}}_{m_2+1}^{\left(\mathit{d}\right)}\\ {\mathit{h}}_{m_2+2}^{\left(\mathit{d}\right)}\end{array}\right), {\mathbf{\phi }}^{\left(\mathit{d}\right)}\stackrel{\mathrm{def}}{=}\left(\begin{array}{c}{\stackrel{\sim }{\mathit{g}}}_0^{\left(\mathit{d}\right)}\\ {\mathit{g}}_1^{\left(\mathit{d}\right)}\\ {\mathit{g}}_2^{\left(\mathit{d}\right)}\\ ⋮\\ {\mathit{g}}_{m_2+1}^{\left(\mathit{d}\right)}\\ {\mathit{g}}_{m_2+2}^{\left(\mathit{d}\right)}\end{array}\right),$$

(15)

where ${\stackrel{\sim }{\mathit{f}}}_0$ and ${\stackrel{\sim }{\mathit{g}}}_0^{\left(\mathit{d}\right)}$ are the two column vectors, which are obtained through omitting the scale entries $f\left(0,0,0\right)$ and $g^{\left(\mathit{d}\right)}\left(0,0,0\right)$ of ${\mathit{f}}_0$ and ${\mathit{g}}_0^{\left(\mathit{d}\right)},$ respectively, and

$$\begin{array}{c}{\mathit{h}}_0^{\left(\mathit{d}\right)}={\left(h_1,h_2,\dots ,h_{l_0}\right)}^T,\hfill \\ {\mathit{h}}_1^{\left(\mathit{d}\right)}={\left(h_{l_0+1},h_{l_1+2},\dots ,h_{l_1}\right)}^T,\hfill \\ {\mathit{h}}_2^{\left(\mathit{d}\right)}={\left(h_{l_1+1},h_{l_2+2},\dots ,h_{l_2}\right)}^T,\hfill \\ \hspace{1em}⋮\hfill \\ {\mathit{h}}_{m_2+1}^{\left(\mathit{d}\right)}={\left(h_{l_{m_2}+1},h_{l_{m_2+1}+2},\dots ,h_{l_{m_2+1}}\right)}^T,\hfill \\ {\mathit{h}}_{m_2+2}^{\left(\mathit{d}\right)}={\left(h_{l_{m_2+1}+1},h_{l_{m_2+2}+2},\dots ,h_L\right)}^T.\hfill \end{array}$$

Therefore, it follows from (13) that

$$-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}{\mathbf{\phi }}^{\left(\mathit{d}\right)}={\mathit{h}}^{\left(\mathit{d}\right)}+{\mu }_1{\mathit{e}}_1{g}^{\left(\mathit{d}\right)}\left(0,0,0\right),$$

(16)

where ${\mathit{e}}_1$ is a column vector with the first element being one and all the others being zero. Note that the matrix $-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}$ is invertible and ${\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}>0$, thus the system (16) of linear equations always exists with one unique solution:

$${\mathbf{\phi }}^{\left(\mathit{d}\right)}={\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{h}}^{\left(\mathit{d}\right)}+{\mu }_1{\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{e}}_1·\Im ,$$

(17)

where $g^{\left(\mathit{d}\right)}\left(0,0,0\right)=\Im$ is any given positive constant. For the convenience of computation, we take $g^{\left(\mathit{d}\right)}\left(0,0,0\right)=\Im =1$. In this case, we have

$${\mathbf{\phi }}^{\left(\mathit{d}\right)}={\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{h}}^{\left(\mathit{d}\right)}+{\mu }_1{\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{e}}_1.$$

(18)

Note that the expression of the invertible matrix ${\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}$ can be obtained by means of the RG-factorization, which is given in Li [33] for general Markov processes.

For convenience of computation, we write

$${\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}={\left({\mathbb{Q}}_0^T,{\mathbb{Q}}_1^T,{\mathbb{Q}}_2^T,\dots ,{\mathbb{Q}}_{m_2+1}^T,{\mathbb{Q}}_{m_2+2}^T\right)}^T,$$

and every element of the matrix ${\mathbb{Q}}_r$ is written by a scalar $q_{n,l}^{\left(r\right)}$, we denote by n a system state under the certain block, and l the index of element, where $r=0,1,\dots ,m_2+2$, $l=1,2,\dots ,L$, for $L=m_1+3m_2/2-m_2^2/2+m_2{m}_3+m_3,$ and

$$n=\left\{\begin{array}{c}1,2,\dots ,m_1, \mathrm{for} r=0,\hfill \\ 1,2,\dots ,m_3, \mathrm{for} r=1,\hfill \\ 0,1,\dots ,m_3-r+1, \mathrm{for} 2\le r\le m_2+1,\hfill \\ m_3-m_2+1,m_3-m_2+2,\dots ,m_3, \mathrm{for} r=m_2+2.\hfill \end{array}\right.$$

It is easy to check that

$$\begin{array}{cc}\hfill {\mathbb{Q}}_0& ={\left(\begin{array}{cccc}{q}_{1,1}^{\left(0\right)}& q_{1,2}^{\left(0\right)}& \cdots & q_{1,L}^{\left(0\right)}\\ q_{2,1}^{\left(0\right)}& q_{2,2}^{\left(0\right)}& \cdots & q_{2,L}^{\left(0\right)}\\ ⋮& ⋮& & ⋮\\ q_{m_1,1}^{\left(0\right)}& q_{m_1,2}^{\left(0\right)}& \cdots & q_{m_1,L}^{\left(0\right)}\end{array}\right)}_{L\times m_1},\hfill \\ \hfill {\mathbb{Q}}_1& ={\left(\begin{array}{cccc}{q}_{1,1}^{\left(1\right)}& q_{1,2}^{\left(1\right)}& \cdots & q_{1,L}^{\left(1\right)}\\ q_{2,1}^{\left(1\right)}& q_{2,2}^{\left(1\right)}& \cdots & q_{2,L}^{\left(1\right)}\\ ⋮& ⋮& & ⋮\\ q_{m_3,1}^{\left(1\right)}& q_{m_3,2}^{\left(1\right)}& \cdots & q_{m_3,L}^{\left(1\right)}\end{array}\right)}_{L\times m_3},\hfill \end{array}$$

for $2\le r\le m_2+1,$

$${\mathbb{Q}}_r={\left(\begin{array}{cccc}{q}_{0,1}^{\left(r\right)}& q_{0,2}^{\left(r\right)}& \cdots & q_{0,L}^{\left(r\right)}\\ q_{1,1}^{\left(r\right)}& q_{1,2}^{\left(r\right)}& \cdots & q_{1,L}^{\left(r\right)}\\ ⋮& ⋮& & ⋮\\ q_{m_3-r+1,1}^{\left(r\right)}& q_{m_3-r+1,2}^{\left(r\right)}& \cdots & q_{m_3-r+1,L}^{\left(r\right)}\end{array}\right)}_{L\times \left(m_3-r+2\right)},$$

and

$${\mathbb{Q}}_{m_2+2}={\left(\begin{array}{cccc}{q}_{m_3-m_2+1,1}^{\left(m_2+2\right)}& q_{m_3-m_2+1,2}^{\left(m_2+2\right)}& \cdots & q_{m_3-m_2+1,L}^{\left(m_2+2\right)}\\ q_{m_3-m_2+2,1}^{\left(m_2+2\right)}& q_{m_3-m_2+2,2}^{\left(m_2+2\right)}& \cdots & q_{m_3-m_2+2,L}^{\left(m_2+2\right)}\\ ⋮& ⋮& & ⋮\\ q_{m_3,1}^{\left(m_2+2\right)}& q_{m_3,2}^{\left(m_2+2\right)}& \cdots & q_{m_3,L}^{\left(m_2+2\right)}\end{array}\right)}_{L\times m_2}.$$

The following theorem provides an expression for the vector ${\mathbf{\phi }}^{\left(\mathit{d}\right)}$ under a constraint condition $g^{\left(\mathit{d}\right)}\left(0,0,0\right)=\Im =1$. Note that this expression is very useful for applications of the sensitivity-based optimization theory to the study of Markov decision processes in our later study.

Theorem 2.

If $g^{\left(\mathit{d}\right)}\left(0,0,0\right)=1$, then for $n_1=1,2,\dots ,m_1,$

$$g^{\left(\mathit{d}\right)}\left(n_1,0,0\right)=\sum _{l=1}^L{q}_{n_1,l}^{\left(0\right)}{h}_l+{\mu }_1{q}_{n_1,1}^{\left(0\right)};$$

for $n_3=1,2,\dots ,m_3,$

$$g^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)=\sum _{l=1}^L{q}_{n_3,l}^{\left(1\right)}{h}_l+{\mu }_1{q}_{n_3,1}^{\left(1\right)};$$

for $n_2=r-1,n_3=0,1,\dots ,m_3-n_2,$ and $2\le r\le m_2+1,$

$$g^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)=\sum _{l=1}^L{q}_{n_3,l}^{\left(r\right)}{h}_l+{\mu }_1{q}_{n_3,1}^{\left(r\right)};$$

for $n_3=m_3-m_2+1,m_3-m_2+2,\dots ,m_3,$

$$g^{\left(\mathit{d}\right)}\left(m_1,m_2,n_3\right)=\sum _{l=1}^L{q}_{n_3,l}^{\left(m_2+2\right)}{h}_l+{\mu }_1{q}_{n_3,1}^{\left(m_2+2\right)}.$$

Proof of Theorem 2.

It is seen from (18) that we need to compute two parts: ${\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{h}}^{\left(\mathit{d}\right)}$ and ${\mu }_1{\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{e}}_1$. Note that

$${\left(-\stackrel{\sim }{\mathbf{Q}}\right)}^{-1}{\mathit{h}}^{\left(\mathit{d}\right)}={\left(\begin{array}{c}\sum _{l=1}^L{q}_{1,l}^{\left(0\right)}{h}_l\\ ⋮\\ \sum _{l=1}^L{q}_{m_1,l}^{\left(0\right)}{h}_l\\ ⋮\\ \sum _{l=1}^L{q}_{0,l}^{\left(r\right)}{h}_l\\ ⋮\\ \sum _{l=1}^L{q}_{m_3-r+1,l}^{\left(r\right)}{h}_l\\ ⋮\\ \sum _{l=1}^L{q}_{m_3-m_2+1,l}^{\left(m_2+2\right)}{h}_l\\ ⋮\\ \sum _{l=1}^L{q}_{m_3,l}^{\left(m_2+2\right)}{h}_l\end{array}\right)}_{L\times 1} \mathrm{and}\hspace{1em}{\mu }_1{\left(-\stackrel{\sim }{\mathbf{Q}}\right)}^{-1}{\mathit{e}}_1={\mu }_1{\left(\begin{array}{c}{q}_{1,1}^{\left(0\right)}\\ ⋮\\ q_{m_1,1}^{\left(0\right)}\\ ⋮\\ q_{0,1}^{\left(r\right)}\\ ⋮\\ q_{m_3-r+1,1}^{\left(r\right)}\\ ⋮\\ q_{m_3-m_2+1,1}^{\left(m_2+2\right)}\\ ⋮\\ q_{m_3,1}^{\left(m_2+2\right)}\end{array}\right)}_{L\times 1}.$$

thus a simple computation for the vector ${\mathbf{\phi }}^{\left(\mathit{d}\right)}={\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{h}}^{\left(\mathit{d}\right)}+{\mu }_1{\left(-{\stackrel{\sim }{\mathbf{Q}}}^{\left(\mathit{d}\right)}\right)}^{-1}{\mathit{e}}_1$ can obtain our desired results. This completes the proof. □

5. Impact of the Service Price

In this section, we study the perturbation realization factor of the policy-based continuous-time Markov process both for the setup policy and for the sleep policy (i.e., they form the asynchronous energy-efficient policy), and analyze how the service price impacts on the perturbation realization factor. To do this, our analysis includes the following two cases: the setup policy and the sleep policy. Note that the results given in this section will be useful for establishing the optimal asynchronous dynamic policy of the energy-efficient data center in later sections.

It is a key in our present analysis that the setup policy and the sleep policy are asynchronous at any time; thus, we can discuss the perturbation realization factor under the asynchronous dynamic policy from two different computational steps.

5.1. The Setup Policy

For the performance potential vector ${\mathbf{\phi }}^{\left(\mathit{d}\right)}$ under a constraint condition $g^{\left(\mathit{d}\right)}\left(0,0,0\right)=1$, we define a perturbation realization factor as

$$G^{\left(\mathit{d}\right)}\left(\mathit{n},{\mathit{n}}^{\prime }\right)\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left({\mathit{n}}^{\prime }\right)-g^{\left(\mathit{d}\right)}\left(\mathit{n}\right),$$

(19)

where $\mathit{n}=\left(n_1,n_2,n_3\right),{\mathit{n}}^{\prime }=\left(n_1^{\prime },n_2^{\prime },n_3^{\prime }\right).$ We can see that $G^{\left(\mathit{d}\right)}\left(\mathit{n},{\mathit{n}}^{\prime }\right)$ quantifies the difference between two performance potentials $g^{\left(\mathit{d}\right)}\left(n_1,n_2,n_3\right)$ and $g^{\left(\mathit{d}\right)}\left(n_1^{\prime },n_2^{\prime },n_3^{\prime }\right)$. It measures the long-run effect on the average profit of the data center when the system state is changed from ${\mathit{n}}^{\prime }=\left(n_1^{\prime },n_2^{\prime },n_3^{\prime }\right)$ to $\mathit{n}=\left(n_1,n_2,n_3\right)$. For our next discussion, through observing the state space, it is necessary to define some perturbation realization factors as follows:

$$\begin{array}{cc}& G_1^{\left({\mathit{d}}^W\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,i_1,n_3-i_1\right)-g^{\left(\mathit{d}\right)}\left(m_1,i_2,n_3-i_2\right),\hfill \\ & G_2^{\left({\mathit{d}}^W\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)-g^{\left(\mathit{d}\right)}\left(m_1,i_1,n_3-i_1\right),\hfill \\ & G_3^{\left({\mathit{d}}^W\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)-g^{\left(\mathit{d}\right)}\left(m_1,i_2,n_3-i_2\right),\hfill \end{array}$$

(20)

where $0\le i_2<i_1\le m_2$ and $n_3=0,1,\dots ,m_3.$

It follows from Theorem 2 that

$$\begin{array}{cc}\hfill g^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)=& \sum _{l=1}^L{q}_{n_{3,}l}^{\left(1\right)}{h}_l+{\mu }_1{q}_{n_{3,}1}^{\left(1\right)},\hfill \\ \hfill g^{\left(\mathit{d}\right)}\left(m_1,i_1,n_3-i_1\right)& =\sum _{l=1}^L{q}_{n_3-i_1,l}^{\left(i_1+1\right)}{h}_l+{\mu }_1{q}_{n_3-i_1,1}^{\left(i_1+1\right)},\hfill \\ \hfill g^{\left(\mathit{d}\right)}\left(m_1,i_2,n_3-i_2\right)& =\sum _{l=1}^L{q}_{n_3-i_2,l}^{\left(i_2+1\right)}{h}_l+{\mu }_1{q}_{n_3-i_2,1}^{\left(i_2+1\right)}.\hfill \end{array}$$

To express the perturbation realization factor by means of the service price R, we write

$$A_0=0,\hspace{1em}{B}_0=\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1>0;$$

for $1\le l\le l_0$ and $n_1=1,2,\dots ,m_1$, $n_2=n_3=0,$

$$A_l=n_1{\mu }_1>0, B_l=\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1+n_1{C}_2^{\left(1\right)}>0;$$

for $l_0+1\le l\le l_1$, and $n_1=m_1$, $n_2=0,$$n_3=1,2,\dots ,m_3,$

$$\begin{array}{cc}\hfill A_l& =m_1{\mu }_1>0,\hfill \\ \hfill B_l^{\left({\mathit{d}}^W\right)}& =\left[m_1{P}_{1,W}+d_{m_1,0,n_3}^W{P}_{2,W}+\left(m_2-d_{m_1,0,n_3}^W\right)P_{2,S}\right]C_1\hfill \\ & \hspace{1em}+\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right]+d_{m_1,0,n_3}^W{C}_3^{\left(1\right)}+\lambda 1_{\left\{n_1=m_1,n_2=0,n_3=m_3\right\}}{C}_5>0;\hfill \end{array}$$

for $l_1+1\le l\le l_{m_2+1}$, and $n_1=m_1$, $n_2=1,2,\dots ,m_2$,$n_3=0,1,\dots ,m_3-n_2$,

$$\begin{array}{cc}\hfill A_l^{\left({\mathit{d}}^S\right)}& =m_1{\mu }_1+(m_2-d_{m_1,n_2,n_3}^S){\mu }_2>0,\hfill \\ \hfill B_l^{\left({\mathit{d}}^S\right)}& =\left[m_1{P}_{1,W}+d_{m_1,n_2,n_3}^S{P}_{2,S}+\left(m_2-d_{m_1,n_2,n_3}^S\right)P_{2,W}\right]C_1+\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]\hfill \\ & \hspace{1em}+\left[n_2-\left(m_2-d_{m_1,n_2,n_3}^S\right)\right]C_3^{\left(2\right)}+m_1{\mu }_1{1}_{\left\{n_3=0\right\}}{C}_4+\lambda 1_{\left\{n_2+n_3=m_3\right\}}{C}_5>0;\hfill \end{array}$$

for $l_{m_2+1}+1\le l\le L$, and $n_1=m_1$, $n_2=m_2$,$n_3=m_3-m_2+1,m_3-m_2+2,\dots ,m_3$,

$$A_l=m_1{\mu }_1+m_2{\mu }_2>0,$$

$$\begin{array}{cc}\hfill B_l& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1+\left[m_1{C}_2^{\left(1\right)}+m_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]+\lambda 1_{\left\{n_1=m_1,n_2=m_2,n_3=m_3\right\}}{C}_5>0.\hfill \end{array}$$

Then for $1\le l\le l_0$ and $n_1=0,1,\dots ,m_1$, $n_2=n_3=0$,

$$f\left(n_1,0,0\right)=R{A}_l-B_l;$$

for $l_0+1\le l\le l_1$, and $n_1=m_1$, $n_2=0,$ $n_3=1,2,\dots ,m_3,$

$$f^{\left({\mathit{d}}^W\right)}\left(m_1,0,n_3\right)=R{A}_l-B_l^{\left({\mathit{d}}^W\right)};$$

for $l_1+1\le l\le l_{m_2+1}$, and $n_1=m_1$, $n_2=1,2,\dots ,m_2$,$n_3=0,1,\dots ,m_3-n_2$,

$$f^{\left({\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)=R{A}_l^{\left({\mathit{d}}^S\right)}-B_l^{\left({\mathit{d}}^S\right)};$$

for $l_{m_2+1}+1\le l\le L$, and $n_1=m_1$, $n_2=m_2$,$n_3=m_3-m_2+1,m_3-m_2+2,\dots ,m_3$,

$$f^{\left(\mathit{d}\right)}\left(m_1,m_2,n_3\right)=R{A}_l-B_l.$$

We rewrite ${\mathbf{\pi }}^{\left(\mathit{d}\right)}$ as

$$\begin{array}{c}{\mathbf{\pi }}_0^{\left(\mathit{d}\right)}=\left({\pi }_0;{\pi }_1,{\pi }_2,\dots ,{\pi }_{l_0}\right),\hfill \\ {\mathbf{\pi }}_1^{\left(\mathit{d}\right)}=\left({\pi }_{l_0+1},{\pi }_{l_0+2},\dots ,{\pi }_{l_1}\right),\hfill \\ {\mathbf{\pi }}_2^{\left(\mathit{d}\right)}=\left({\pi }_{l_1+1},{\pi }_{l_1+2},\dots ,{\pi }_{l_2}\right),\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}⋮\hfill \\ {\mathbf{\pi }}_{m_2+1}^{\left(\mathit{d}\right)}=\left({\pi }_{l_{m_2}+1},{\pi }_{l_{m_2}+2},\dots ,{\pi }_{l_{m_2+1}}\right),\hfill \\ {\mathbf{\pi }}_{m_2+2}^{\left(\mathit{d}\right)}=\left({\pi }_{l_{m_2+1}+1},{\pi }_{l_{m_2+1}+2},\dots ,{\pi }_L\right).\hfill \end{array}$$

Then it is easy to check that

$$\begin{array}{cc}\hfill D^{\left(\mathit{d}\right)}& ={\pi }_0{A}_0+\sum _{l=0}^{l_0}{\pi }_l{A}_l+\sum _{l=l_0+1}^{l_1}{\pi }_l{A}_l+\sum _{l=l_1+1}^{l_{m_2+1}}{\pi }_l{A}_l^{\left({\mathit{d}}^S\right)}+\sum _{l=l_{m_2+1}+1}^L{\pi }_l{A}_l>0,\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill F^{\left(\mathit{d}\right)}& ={\pi }_0{B}_0+\sum _{l=0}^{l_0}{\pi }_l{B}_l+\sum _{l=l_0+1}^{l_1}{\pi }_l{B}_l^{\left({\mathit{d}}^W\right)}+\sum _{l=l_1+1}^{l_{m_2+1}}{\pi }_l{B}_l^{\left({\mathit{d}}^S\right)}+\sum _{l=l_{m_2+1}+1}^L{\pi }_l{B}_l>0.\hfill \end{array}$$

Thus, we obtain

$$\begin{array}{cc}\hfill {\eta }^{\mathit{d}}& ={\mathbf{\pi }}^{\left(\mathit{d}\right)}{\mathit{f}}^{\left(\mathit{d}\right)}\hfill \\ & =\sum _{n_1=0}^{m_1}{\pi }^{\left(\mathit{d}\right)}\left(n_1,0,0\right)f\left(n_1,0,0\right)+\sum _{n_3=1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)f^{\left({\mathit{d}}^W\right)}\left(m_1,0,n_3\right)\hfill \\ & \hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2=0}^{m_2}{\pi }^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)f^{\left({\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)\hfill \\ & \hspace{1em}+\sum _{n_3=m_3-m_2+1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,n_3\right)f\left(m_1,m_2,n_3\right)\hfill \\ & =R{D}^{\left(\mathit{d}\right)}-F^{\left(\mathit{d}\right)}.\hfill \end{array}$$

It follows from (15) that for $1\le l\le l_0$,

$$h_l=R\left[A_l-D^{\left(\mathit{d}\right)}\right]-\left[B_l-F^{\left(\mathit{d}\right)}\right];$$

for $l_0+1\le l\le l_1$,

$$h_l=R\left[A_l-D^{\left(\mathit{d}\right)}\right]-\left[B_l^{\left({\mathit{d}}^W\right)}-F^{\left(\mathit{d}\right)}\right];$$

for $l_1+1\le l\le l_{m_2+1}$,

$$h_l=R\left[A_l^{\left({\mathit{d}}^S\right)}-D^{\left(\mathit{d}\right)}\right]-\left[B_l^{\left({\mathit{d}}^S\right)}-F^{\left(\mathit{d}\right)}\right];$$

for $l_{m_2+1}+1\le l\le L$,

$$h_l=R\left[A_l-D^{\left(\mathit{d}\right)}\right]-\left[B_l-F^{\left(\mathit{d}\right)}\right].$$

If a job finishes its service at a server and leaves this system immediately, then the data center can obtain a fixed revenue (i.e., the service price) R from such a served job. Now, we study the influence of the service price R on the perturbation realization factor. Note that all the numbers $q_{n,l}^{\left(r\right)}$ are positive and are independent of the service price R, while all the numbers $h_l$ are the linear functions of R. We write

$$\begin{array}{cc}\hfill W_n^{\left(r\right)}& =\sum _{l=1}^{l_0}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[A_l-D^{\left(\mathit{d}\right)}\right]+\sum _{l=l_0+1}^{l_1}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[A_l-D^{\left(\mathit{d}\right)}\right]\hfill \\ & \hspace{1em}+\sum _{l=l_1+1}^{l_{m_2+1}}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[A_l^{\left({\mathit{d}}^S\right)}-D^{\left(\mathit{d}\right)}\right]+\sum _{l=l_{m_2+1}+1}^L{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[A_l-D^{\left(\mathit{d}\right)}\right]+{\mu }_1{q}_{n,1}^{\left(r\right)}\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill V_n^{\left(r\right)}& =\sum _{l=1}^{l_0}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[B_l-F^{\left(\mathit{d}\right)}\right]+\sum _{l=l_0+1}^{l_1}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[B_l^{\left({\mathit{d}}^W\right)}-F^{\left(\mathit{d}\right)}\right]\hfill \\ & \hspace{1em}+\sum _{l=l_1+1}^{l_{m_2+1}}{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[B_l^{\left({\mathit{d}}^S\right)}-F^{\left(\mathit{d}\right)}\right]+\sum _{l=l_{m_2+1}+1}^L{q}_{n_{,}l}^{\left(r\right)}{h}_l\left[B_l-F^{\left(\mathit{d}\right)}\right],\hfill \end{array}$$

then for $i_1,i_2=0,1,\dots ,m_2$, we obtain

$$\begin{array}{cc}& G_1^{\left({\mathit{d}}^W\right)}=R\left[W_{n_3-i_1}^{\left(i_1+1\right)}-W_{n_3-i_2}^{\left(i_2+1\right)}\right]-\left[V_{n_3-i_1}^{\left(i_1+1\right)}-V_{n_3-i_2}^{\left(i_2+1\right)}\right],\hfill \\ & G_2^{\left({\mathit{d}}^W\right)}=R\left[W_{n_3}^{\left(1\right)}-W_{n_3-i_1}^{\left(i_1+1\right)}\right]-\left[V_{n_3}^{\left(1\right)}-V_{n_3-i_1}^{\left(i_1+1\right)}\right],\hfill \\ & G_3^{\left({\mathit{d}}^W\right)}=R\left[W_{n_3}^{\left(1\right)}-W_{n_3-i_2}^{\left(i_2+1\right)}\right]-\left[V_{n_3}^{\left(1\right)}-V_{n_3-i_2}^{\left(i_2+1\right)}\right].\hfill \end{array}$$

(21)

Now, we define

$$G^{\left({\mathit{d}}^W\right)}=m_1{\mu }_1{G}_1^{\left({\mathit{d}}^W\right)}-i_1{\mu }_2\left(G_2^{\left({\mathit{d}}^W\right)}+{\beta }_1\right)+i_2{\mu }_2\left(G_3^{\left({\mathit{d}}^W\right)}+{\beta }_1\right),$$

where ${\beta }_1$ is defined as

$${\beta }_1=\frac{\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}}{{\mu }_2}.$$

From the later discussion in Section 6, we will see that $G^{\left({\mathit{d}}^W\right)}$ plays a fundamental role in the performance optimization of data centers, and the sign of $G^{\left({\mathit{d}}^W\right)}$ directly determines the selection of decision actions, as shown in (38) later. To this end, we analyze how the service price can impact on $G^{\left({\mathit{d}}^W\right)}$ as follows. Substituting (21) into the linear equation $G^{\left({\mathit{d}}^W\right)}=0$, we obtain

$$\begin{array}{c}R={\displaystyle \frac{\phi \left(i_1\right)V_{n_3-i_1}^{\left(i_1+1\right)}-\phi \left(i_2\right)V_{n_3-i_2}^{\left(i_2+1\right)}-\psi \left(i_1,i_2\right)\left(V_{n_3}^{\left(1\right)}-{\beta }_1\right)}{\phi \left(i_1\right)W_{n_3-i_1}^{\left(i_1+1\right)}-\phi \left(i_2\right)W_{n_3-i_2}^{\left(i_2+1\right)}-\psi \left(i_1,i_2\right)W_{n_3}^{\left(1\right)}}},\hfill \end{array}$$

(22)

where $\phi \left(i_1\right)=m_1{\mu }_1+i_1{\mu }_2,\phi \left(i_2\right)=m_1{\mu }_1+i_2{\mu }_2$ and $\psi \left(i_1,i_2\right)=\left(i_1-i_2\right){\mu }_2.$

Thus, the unique solution of the price R in (22) is given by

$$\begin{array}{c}{\Re }^{\left({\mathit{d}}^W\right)}\left(i_1,i_2\right)={\displaystyle \frac{\phi \left(i_1\right)V_{n_3-i_1}^{\left(i_1+1\right)}-\phi \left(i_2\right)V_{n_3-i_2}^{\left(i_2+1\right)}-\psi \left(i_1,i_2\right)\left(V_{n_3}^{\left(1\right)}-{\beta }_1\right)}{\phi \left(i_1\right)W_{n_3-i_1}^{\left(i_1+1\right)}-\phi \left(i_2\right)W_{n_3-i_2}^{\left(i_2+1\right)}-\psi \left(i_1,i_2\right)W_{n_3}^{\left(1\right)}}},\hfill \end{array}$$

(23)

It is easy to see from (22) that (a) if $R\ge {\Re }^{\left({\mathit{d}}^W\right)}\left(i_1,i_2\right)$, then $G^{\left({\mathit{d}}^W\right)}\ge 0$; and (b) if $R\le {\Re }^{\left({\mathit{d}}^W\right)}\left(i_1,i_2\right)$, then $G^{\left({\mathit{d}}^W\right)}\le 0$.

In the energy-efficient data center, we define two critical values, related to the service price, as

$$\begin{array}{c}{R}_H^W={\displaystyle \underset{\mathit{d}\in \mathcal{D}}{max}}\left\{0,{\Re }^{\left({\mathit{d}}^W\right)}\left(1,0\right),{\Re }^{\left({\mathit{d}}^W\right)}\left(2,0\right),\dots ,{\Re }^{\left({\mathit{d}}^W\right)}\left(m_2,m_2-1\right)\right\}\hfill \end{array}$$

(24)

and

$$\begin{array}{c}{R}_L^W={\displaystyle \underset{\mathit{d}\in \mathcal{D}}{min}}\left\{{\Re }^{\left({\mathit{d}}^W\right)}\left(1,0\right),{\Re }^{\left({\mathit{d}}^W\right)}\left(2,0\right),\dots ,{\Re }^{\left({\mathit{d}}^W\right)}\left(m_2,m_2-1\right)\right\}\hfill \end{array}$$

(25)

The following proposition uses the two critical values, which are related to the service price, to provide a key condition whose purpose is to establish a sensitivity-based optimization framework of the energy-efficient data center in our later study. Additionally, this proposition will be useful in the next section for studying the monotonicity of the asynchronous energy-efficient policies.

Proposition 1.

(1) If $R\ge R_H^W$, then for any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(i_1,i_2\right)$ with $0\le i_2<i_1\le m_2,$ we have

$$G^{\left({\mathit{d}}^W\right)}\ge 0.$$

(26)

(2) If $0\le R\le R_L^W$, then for any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(i_1,i_2\right)$ with $0\le i_2<i_1\le m_2,$ we have

$$G^{\left({\mathit{d}}^W\right)}\le 0.$$

(27)

Proof of Proposition 1.

(1) For any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(i_1,i_2\right)$ with $0\le i_2<i_1\le m_2$, since $R\ge R_H^W$ and $R_H^W={max}_{\mathit{d}\in \mathcal{D}}\left\{0,{\Re }^{\left({\mathit{d}}^W\right)}\left(1,0\right),{\Re }^{\left({\mathit{d}}^W\right)}\left(2,0\right),\dots ,\right.$$\hspace{1em}\left.{\Re }^{\left({\mathit{d}}^W\right)}\left(m_2,m_2-1\right)\right\}$, this gives

$$R\ge {\Re }^{\left({\mathit{d}}^W\right)}\left(i_1,i_2\right).$$

Thus, for any couple $\left(i_1,i_2\right)$ with $0\le i_2<i_1\le m_2$ this makes that $G^{\left({\mathit{d}}^W\right)}\ge 0$.

(2) For any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(i_1,i_2\right)$ with $0\le i_2<i_1\le m_2$, if $0\le R\le R_L^W$, we get

$$R\le {\Re }^{\left({\mathit{d}}^W\right)}\left(i_1,i_2\right),$$

this gives that $G^{\left({\mathit{d}}^W\right)}\le 0$. This completes the proof. □

5.2. The Sleep Policy

The analysis for the sleep policy is similar to that of the setup policy given in the above subsection. Here, we shall provide only a simple discussion.

We define the perturbation realization factor for the sleep policy as follows:

$$\begin{array}{cc}& G_1^{\left({\mathit{d}}^S\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,j_2,n_3+n_2-j_2\right)-g^{\left(\mathit{d}\right)}\left(m_1,j_1,n_3+n_2-j_1\right),\hfill \\ & G_2^{\left({\mathit{d}}^S\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)-g^{\left(\mathit{d}\right)}\left(m_1,j_1,n_3+n_2-j_1\right),\hfill \\ & G_3^{\left({\mathit{d}}^S\right)}\stackrel{\mathrm{def}}{=}{g}^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)-g^{\left(\mathit{d}\right)}\left(m_1,j_2,n_3+n_2-j_2\right),\hfill \end{array}$$

(28)

where $0\le j_2<j_1\le n_2,n_2=0,1,\dots ,m_2$ and $n_3=0,1,\dots ,m_3.$

It follows from Theorem 2 that

$$\begin{array}{c}{g}^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)=\sum _{l=1}^L{q}_{n_3,l}^{\left(n_2+1\right)}{h}_l+{\mu }_1{q}_{n_3,1}^{\left(n_2+1\right)},\\ g^{\left(\mathit{d}\right)}\left(m_1,j_1,n_3+n_2-j_1\right)=\sum _{l=1}^L{q}_{n_3+n_2-j_1,l}^{\left(j_1+1\right)}{h}_l+{\mu }_1{q}_{n_3+n_2-j_1,1}^{\left(j_1+1\right)},\\ g^{\left(\mathit{d}\right)}\left(m_1,j_2,n_3+n_2-j_2\right)=\sum _{l=1}^L{q}_{n_3+n_2-j_2,l}^{\left(j_2+1\right)}{h}_l+{\mu }_1{q}_{n_3+n_2-j_2,1}^{\left(j_2+1\right)}.\end{array}$$

Similarly, to express the perturbation realization factor by means of the service price R, we write

$$G^{\left({\mathit{d}}^S\right)}=m_1{\mu }_1{G}_1^{\left({\mathit{d}}^S\right)}+j_1{\mu }_2\left(G_2^{\left({\mathit{d}}^S\right)}+{\beta }_2\right)-j_2{\mu }_2\left(G_3^{\left({\mathit{d}}^S\right)}+{\beta }_2\right),$$

where

$$\begin{array}{cc}& G_1^{\left({\mathit{d}}^S\right)}=R\left[W_{n_3+n_2-j_2}^{\left(j_2+1\right)}-W_{n_3+n_2-j_1}^{\left(j_1+1\right)}\right]-\left[V_{n_3+n_2-j_2}^{\left(j_2+1\right)}-V_{n_3+n_2-j_1}^{\left(j_1+1\right)}\right],\hfill \\ & G_2^{\left({\mathit{d}}^S\right)}=R\left[W_{n_3}^{\left(n_2+1\right)}-W_{n_3+n_2-j_1}^{\left(j_1+1\right)}\right]-\left[V_{n_3}^{\left(n_2+1\right)}-V_{n_3+n_2-j_1}^{\left(j_1+1\right)}\right],\hfill \\ & G_3^{\left({\mathit{d}}^S\right)}=R\left[W_{n_3}^{\left(n_2+1\right)}-W_{n_3+n_2-j_2}^{\left(j_2+1\right)}\right]-\left[V_{n_3}^{\left(n_2+1\right)}-V_{n_3+n_2-j_2}^{\left(j_2+1\right)}\right],\hfill \end{array}$$

(29)

and

$${\beta }_2=-R+\frac{\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(2\right)}}{{\mu }_2}.$$

Now, we analyze how the service price impacts on $G^{\left({\mathit{d}}^S\right)}$ as follows: Substituting (29) into the linear equation $G^{\left({\mathit{d}}^S\right)}=0$, we obtain

$$\begin{array}{c}R={\displaystyle \frac{\phi \left(j_1\right)V_{n_3+n_2-j_1}^{\left(j_1+1\right)}-\phi \left(j_2\right)V_{n_3+n_2-j_2}^{\left(j_2+1\right)}-\psi \left(j_1,j_2\right)\left(V_{n_3}^{\left(n_2+1\right)}-{\beta }_2\right)}{\phi \left(j_1\right)W_{n_3+n_2-j_1}^{\left(j_1+1\right)}-\phi \left(j_2\right)W_{n_3+n_2-j_2}^{\left(j_2+1\right)}-\psi \left(j_1,j_2\right){\mu }_2{W}_{n_3}^{\left(n_2+1\right)}}}.\hfill \end{array}$$

(30)

Then, the unique solution of the price R in (30) is given by

$$\begin{array}{c}{\Re }^{\left({\mathit{d}}^S\right)}\left(j_1,j_2\right)={\displaystyle \frac{\phi \left(j_1\right)V_{n_3+n_2-j_1}^{\left(j_1+1\right)}-\phi \left(j_2\right)V_{n_3+n_2-j_2}^{\left(j_2+1\right)}-\psi \left(j_1,j_2\right)\left(V_{n_3}^{\left(n_2+1\right)}-{\beta }_2\right)}{\phi \left(j_1\right)W_{n_3+n_2-j_1}^{\left(j_1+1\right)}-\phi \left(j_2\right)W_{n_3+n_2-j_2}^{\left(j_2+1\right)}-\psi \left(j_1,j_2\right){\mu }_2{W}_{n_3}^{\left(n_2+1\right)}}}.\hfill \end{array}$$

It is easy to see from Equation (30) that (a) if $R\ge {\Re }^{\left({\mathit{d}}^S\right)}\left(j_1,j_2\right)$, then $G^{\left({\mathit{d}}^S\right)}\ge 0$; and (b) if $R\le {\Re }^{\left({\mathit{d}}^S\right)}\left(j_1,j_2\right)$, then $G^{\left({\mathit{d}}^S\right)}\le 0$.

In the energy-efficient data center, we relate to the service price and define two critical values as

$$\begin{array}{c}{R}_H^S={\displaystyle \underset{\mathit{d}\in \mathcal{D}}{max}}\left\{0,{\Re }^{\left({\mathit{d}}^S\right)}\left(1,0\right),{\Re }^{\left({\mathit{d}}^S\right)}\left(2,0\right),\dots ,{\Re }^{\left({\mathit{d}}^S\right)}\left(m_2,m_2-1\right)\right\}\hfill \end{array}$$

(31)

and

$$\begin{array}{c}{R}_L^S={\displaystyle \underset{\mathit{d}\in \mathcal{D}}{min}}\left\{{\Re }^{\left({\mathit{d}}^S\right)}\left(1,0\right),{\Re }^{\left({\mathit{d}}^S\right)}\left(2,0\right),\dots ,{\Re }^{\left({\mathit{d}}^S\right)}\left(m_2,m_2-1\right)\right\}\hfill \end{array}$$

(32)

The following proposition is similar to Proposition 1, thus its proof is omitted here.

Proposition 2.

(1) If $R\ge R_H^S$, then for any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(j_1,j_2\right)$ with $0\le j_2<j_1\le n_2,$ we have

$$G^{\left({\mathit{d}}^S\right)}\ge 0.$$

(2) If $0\le R\le R_L^S$, then for any $\mathit{d}\in \mathcal{D}$ and for each couple $\left(j_1,j_2\right)$ with $0\le j_2<j_1\le n_2,$ we have

$$G^{\left({\mathit{d}}^S\right)}\le 0.$$

From Propositions 1 and 2, we relate to the service price and define two new critical values as

$$R_H=max\left\{R_H^W,R_H^S\right\} \mathrm{and} R_L=min\left\{R_L^W,R_L^S\right\}.$$

(33)

The following theorem provides a simple summarization from Propositions 1 and 2, and it will be useful for studying the monotonicity and optimality of the asynchronous dynamic policy in our later sections.

Theorem 3.

(1) If $R\ge R_H$, then for any asynchronous dynamic policy $\mathit{d}\in \mathcal{D}$, we have

$$G^{\left({\mathit{d}}^W\right)}\ge 0 and G^{\left({\mathit{d}}^S\right)}\ge 0.$$

(2) If $0\le R\le R_L$, then for any asynchronous policy $\mathit{d}\in \mathcal{D}$, we have

$$G^{\left({\mathit{d}}^W\right)}\le 0 and G^{\left({\mathit{d}}^S\right)}\le 0.$$

6. Monotonicity and Optimality

In this section, we use the block-structured Poisson equation to derive a useful performance difference equation, and discuss the monotonicity and optimality of the long-run average profit of the energy-efficient data center with respect to the setup and sleep policies, respectively. Based on this, we can give the optimal asynchronous dynamic policy of the energy-efficient data center.

The standard Markov model-based formulation suffers from a number of drawbacks. First and foremost, the state space is usually too large for practical problems. That is, the number of potentials to be calculated or estimated is too large for most problems. Secondly, the generally applicable Markov model does not reflect any special structure of a particular problem. Thus, it is not clear whether and how potentials can be aggregated to save computation by exploring the special structure of the system. The sensitivity point of view and the flexible construction of the sensitivity formulas provide us a new perspective to explore alternative approaches for the performance optimization of systems with some special features.

For any given asynchronous energy-efficient policy $\mathit{d}\in \mathcal{D}$, the policy-based continuous-time Markov process $\{{\mathbf{X}}^{\left(\mathit{d}\right)}\left(t\right):t\ge 0\}$ with infinitesimal generator ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ given in (2) is an irreducible, aperiodic, and positive recurrent. Therefore, by using a similar analysis to Ma et al. [31], the long-run average profit of the data center is given by

$${\eta }^{\mathit{d}}={\mathbf{\pi }}^{\left(\mathit{d}\right)}{\mathit{f}}^{\left(\mathit{d}\right)},$$

and the Poisson equation is written as

$${\mathbf{Q}}^{\left(\mathit{d}\right)}{\mathit{g}}^{\left(\mathit{d}\right)}={\eta }^{\mathit{d}}\mathit{e}-{\mathit{f}}^{\left(\mathit{d}\right)}.$$

For State $\left(n_1,n_2,n_3\right)$, it is seen from (2) that the asynchronous energy-efficient policy $\mathit{d}$ directly affects not only the elements of the infinitesimal generator ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ but also the reward function ${\mathit{f}}^{\left(\mathit{d}\right)}$. That is, if the asynchronous policy $\mathit{d}$ changes, then the infinitesimal generator ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ and the reward function ${\mathit{f}}^{\left(\mathit{d}\right)}$ will have their corresponding changes. To express such a change mathematically, we take two different asynchronous energy-efficient policies $\mathit{d}$ and ${\mathit{d}}^{\prime }$, both of which correspond to their infinitesimal generators ${\mathbf{Q}}^{\left(\mathit{d}\right)}$ and ${\mathbf{Q}}^{\left({\mathit{d}}^{\prime }\right)}$, and to their reward functions ${\mathit{f}}^{\left(\mathit{d}\right)}$ and ${\mathit{f}}^{\left({\mathit{d}}^{\prime }\right)}$.

The following lemma provides a useful equation for the difference ${\eta }^{{\mathit{d}}^{\prime }}-{\eta }^{\mathit{d}}$ of the long-run average performances ${\eta }^{\mathit{d}}$ and ${\eta }^{{\mathit{d}}^{\prime }}$ for any two asynchronous policies $\mathit{d},{\mathit{d}}^{\prime }\in \mathcal{D}$. Here, we only restate it without proof, while readers may refer to Ma et al. [31] for more details.

Lemma 1.

For any two asynchronous energy-efficient policies $\mathit{d},{\mathit{d}}^{\prime }\in \mathcal{D}$, we have

$${\eta }^{{\mathit{d}}^{\prime }}-{\eta }^{\mathit{d}}={\mathbf{\pi }}^{\left({\mathit{d}}^{\prime }\right)}\left[\left({\mathbf{Q}}^{\left({\mathit{d}}^{\prime }\right)}-{\mathbf{Q}}^{\left(\mathit{d}\right)}\right){\mathit{g}}^{\left(\mathit{d}\right)}+\left({\mathit{f}}^{\left({\mathit{d}}^{\prime }\right)}-{\mathit{f}}^{\left(\mathit{d}\right)}\right)\right].$$

(34)

Now, we describe the first role played by the performance difference, in which we set up a partial order relation in the policy set $\mathcal{D}$ so that the optimal asynchronous energy-efficient policy in the finite set $\mathcal{D}$ can be found by means of finite comparisons. Based on the performance difference ${\eta }^{{\mathit{d}}^{\prime }}-{\eta }^{\mathit{d}}$ for any two asynchronous energy-efficient policies $\mathit{d},{\mathit{d}}^{\prime }\in \mathcal{D}$, we can set up a partial order in the policy set $\mathcal{D}$ as follows. We write ${\mathit{d}}^{\prime }\succ$$\mathit{d}$ if ${\eta }^{{\mathit{d}}^{\prime }}>{\eta }^{\mathit{d}}$; ${\mathit{d}}^{\prime }\approx \mathit{d}$ if ${\eta }^{{\mathit{d}}^{\prime }}={\eta }^{\mathit{d}}$; ${\mathit{d}}^{\prime }\prec \mathit{d}$ if ${\eta }^{{\mathit{d}}^{\prime }}<{\eta }^{\mathit{d}}$. Furthermore, we write ${\mathit{d}}^{\prime }⪰\mathit{d}$ if ${\eta }^{{\mathit{d}}^{\prime }}\ge {\eta }^{\mathit{d}}$; ${\mathit{d}}^{\prime }⪯\mathit{d}$ if ${\eta }^{{\mathit{d}}^{\prime }}\le {\eta }^{\mathit{d}}$. By using this partial order, our research target is to find an optimal asynchronous policy ${\mathit{d}}^{*}\in \mathcal{D}$ such that ${\mathit{d}}^{*}⪰\mathit{d}$ for any asynchronous energy-efficient policy $\mathit{d}\in \mathcal{D}$, or

$${\mathit{d}}^{*}=\underset{\mathit{d}\in \mathcal{D}}{argmax}\left\{{\eta }^{\mathit{d}}\right\}.$$

Note that the policy set $\mathcal{D}$ and the state space $\Omega$ are both finite, thus an enumeration method is feasible for finding the optimal asynchronous energy-efficient policy ${\mathit{d}}^{*}$ in the policy set $\mathcal{D}$. Since

$$\begin{array}{cc}\hfill \mathcal{D}& =\left\{\mathit{d}={\mathit{d}}^W⊠{\mathit{d}}^S:d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,m_2\right\} \mathrm{for} 1\le n_3\le m_3;\right.\hfill \\ & \hspace{1em}\left.d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\} \mathrm{for} \left(m_1,n_2,n_3\right)\in {\Omega }_2\cup {\Omega }_3\cup \cdots \cup {\Omega }_{m_2+1}\right\}.\hfill \end{array}$$

It is seen that the policy set $\mathcal{D}$ contains ${\left(m_2+1\right)}^{m_3}$$\times 2^{m_3}\times 3^{m_3-1}\times \cdots \times {\left(m_2+1\right)}^{m_2+1}$ elements so that the enumeration method used to find the optimal policy will require a huge enumeration workload. However, our following work will be able to greatly reduce the amount of searching for the optimal asynchronous policy ${\mathit{d}}^{*}$ by means of the sensitivity-based optimization theory.

Now, we discuss the monotonicity of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to any asynchronous policy $\mathit{d}$ under the different service prices. Since the setup and sleep policies ${\mathit{d}}^W$ and ${\mathit{d}}^S$ occur asynchronously and they will not interact with each other at any time, we can, respectively, study the impact of the policies ${\mathit{d}}^W$ and ${\mathit{d}}^S$ on the long-run average profit ${\eta }^{\mathit{d}}.$ To this end, in what follows we shall discuss three different cases: $R\ge R_H,$$0\le R\le R_L$, and $R_L<R<R_H.$

6.1. The Service Price $R\ge R_H$

In the case of $R\ge R_H,$ we discuss the monotonicity and optimality with respect to two different policies: the setup policy and the sleep policy, respectively.

6.1.1. The Setup Policy with $R\ge R_H^W$

The following theorem analyzes the right-half part of the unimodal structure (see Figure 2) of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to the setup policy—either $d_{m_1,0,n_3}^W\in \left\{n_3,n_3+1,\dots ,m_2\right\}$ if $n_3\le m_2$ or $d_{m_1,0,n_3}^W=m_2$ if $n_3>m_2$.

Theorem 4.

For any setup policy ${\mathit{d}}^W$ with ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$ and for each $n_3=1,2,\dots ,m_3$, the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is linearly increasing with respect to the setup policy either $d_{m_1,0,n_3}^W\in \left\{n_3,n_3+1,\dots ,m_2\right\}$ if $n_3\le m_2$ or $d_{m_1,0,n_3}^W=m_2$ if $n_3>m_2$.

Proof of Theorem 4.

For each $n_3=1,2,\dots ,m_3$, we consider two interrelated policies ${\mathit{d}}^W⊠{\mathit{d}}^S,{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\in \mathcal{D}$ as follows:

$$\begin{array}{c}\hfill {\mathit{d}}^W=\left(d_{m_1,0,1}^W,d_{m_1,0,2}^W,\dots ,d_{m_1,0,n_3-1}^W,\underline{d_{m_1,0,n_3}^W},d_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_3}^W\right),\\ \hfill {\mathit{d}}^{W^{\prime }}=\left(d_{m_1,0,1}^W,d_{m_1,0,2}^W,\dots ,d_{m_1,0,n_3-1}^W,\underline{n_3\wedge m_2},d_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_3}^W\right),\end{array}$$

where $d_{m_1,0,n_3}^W\le n_3\wedge m_2$. It is seen that the two policies ${\mathit{d}}^W,{\mathit{d}}^{W^{\prime }}$ have one difference only between their corresponding decision elements $d_{m_1,0,n_3}^W$ and $n_3\wedge m_2$. In this case, it is seen from Theorem 1 that ${\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}={\mathbf{Q}}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}$ and ${\mathbf{\pi }}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}={\mathbf{\pi }}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}$. Furthermore, it is easy to check from (4) to (7) that

$$\begin{array}{cc}& {\mathit{f}}^{\left(\mathit{d}\right)}-{\mathit{f}}^{\left({\mathit{d}}^{\prime }\right)}={\left(0,0,\dots ,0\underline{,-\left(d_{m_1,0,n_3}^W-n_3\wedge m_2\right)\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right],}0,\dots ,0\right)}^T.\hfill \end{array}$$

Thus, it follows from Lemma 1 that

$$\begin{array}{cc}& {\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}\hfill \\ & ={\mathbf{\pi }}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left[\left({\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}-{\mathbf{Q}}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\right){\mathit{g}}^{({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S)}+\left({\mathit{f}}^{\left({\mathit{d}}^W\right)}-{\mathit{f}}^{\left({\mathit{d}}^{W^{\prime }}\right)}\right)\right]\hfill \\ & =-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)\left(d_{m_1,0,n_3}^W-n_3\wedge m_2\right)\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right]\hfill \end{array}$$

or

$$\begin{array}{cc}& {\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)\left(d_{m_1,0,n_3}^W-n_3\wedge m_2\right)\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right].\hfill \end{array}$$

(35)

Since ${\mathbf{\pi }}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}={\mathbf{\pi }}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}$, it is easy to see that ${\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}$$\left(m_1,0,n_3\right)$ can be determined by $d_{m_1,0,n_3}^{W^{\prime }}=n_3\wedge m_2.$ This indicates that ${\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)$ is irrelevant to the decision element $d_{m_1,0,n_3}^W.$ Furthermore, note that ${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}$ is irrelevant to the decision element $d_{m_1,0,n_3}^W$, and $P_{2,W}-P_{2,S}$, $C_1$ and $C_3^{\left(1\right)}$ are all positive constants, thus it is easy to see from (35) that the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is linearly decreasing with respect to each decision element $d_{m_1,0,n_3}^W$ for $d_{m_1,0,n_3}^W\in \left\{\left(n_3+1\right)\wedge m_2,\left(n_3+2\right)\wedge m_2,\dots ,m_2\right\}$. It is worth noting that if $m_2\le n_3\le m_3,$ then $d_{m_1,0,n_3}^W\in \left\{m_2,m_2,\dots ,m_2\right\}$. This completes the proof. □

In what follows, we discuss the left-half part of the unimodal structure (see Figure 2) of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to each decision element $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,n_3\right\}$ if $n_3<m_2.$ Compared to analysis of its right-half part, our discussion for the left-half part is a little bit complicated.

Let the optimal setup policy ${\mathit{d}}^{W^{*}}=\underset{{\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}}{argmax}\left\{{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}\right\}$ be

$${\mathit{d}}^{W^{*}}=\left(d_{m_1,0,1}^{W^{*}},d_{m_1,0,2}^{W^{*}},\dots ,d_{m_1,0,m_3}^{W^{*}}\right).$$

Then, it is seen from Theorem 4 that

$$d_{m_1,0,n_3}^{W^{*}}=\left\{\begin{array}{cc}0,1,\dots ,n_3,\hfill & 1\le n_3\le m_2,\hfill \\ m_2,\hfill & m_2\le n_3\le m_3.\hfill \end{array}\right.$$

Hence, Theorem 4 takes the area of finding the optimal setup policy ${\mathit{d}}^{W^{*}}$ from a large set ${\left\{0,1,\dots ,m_2\right\}}^{m_3}$ to a greatly shrunken area $\left\{0,1\right\}\times \left\{0,1,2\right\}\times \cdots \times \left\{0,1,\dots ,m_2-1\right\}\times {\left\{0,1,\dots ,m_2\right\}}^{m_3-m_2+1}$.

To find the optimal setup policy ${\mathit{d}}^{W^{*}}$, we consider two setup policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^W& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^W,}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \\ \hfill {\mathit{d}}^{W^{\prime }}& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^{W^{\prime }},}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \end{array}$$

where $d_{m_1,0,n_3}^{W^{\prime }}=i_1>d_{m_1,0,n_3}^W=i_2$, and $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{1,2,\dots ,n_3\wedge m_2\right\}$. It is easy to check from (2) that

$$\begin{array}{cc}& \hspace{1em}{\mathbf{Q}}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}-{\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)=}\hfill \\ & \left(\begin{array}{ccccccccc}0& & 0& & 0& & & & \\ & \ddots & & \ddots & & \ddots & & & \\ & & 0& & 0& & 0& & \\ & & -\left(i_1-i_2\right){\mu }_2& \cdots & -\left(m_1{\mu }_1+i_2{\mu }_2\right)& \cdots & m_1{\mu }_1+i_1{\mu }_2& & \\ & & 0& & 0& & 0& & \\ & & & \ddots & & \ddots & & \ddots & \\ & & & & 0& & 0& & 0\end{array}\right).\hfill \end{array}$$

(36)

On the other hand, from the reward functions given in (8), it is seen that for $n_3=1,2,\dots ,m_2$, and $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,n_3\right\}$,

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^W\right)}\left(m_1,0,n_3\right)& =-\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right]d_{m_1,0,n_3}^W+R{m}_1{\mu }_1\hfill \\ & \hspace{1em}-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1-\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right]-\lambda 1_{\left\{n_3=m_3\right\}}{C}_5\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^{W^{\prime }}\right)}\left(m_1,0,n_3\right)& =-\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right]d_{m_1,0,n_3}^{W^{\prime }}+R{m}_1{\mu }_1\hfill \\ & \hspace{1em}-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1-\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right]-\lambda 1_{\left\{n_3=m_3\right\}}{C}_5.\hfill \end{array}$$

Hence, we have

$${\mathit{f}}^{\left({\mathit{d}}^{W^{\prime }}\right)}-{\mathit{f}}^{\left({\mathit{d}}^W\right)}={\left(0,0,\dots ,0,-\left(i_2-i_1\right){\mu }_2{\beta }_1,0,\dots ,0\right)}^T.$$

(37)

We write that

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,0,n_3}^W=i}={\mathbf{\pi }}^{\left(\mathit{d}\right)}{{\mid }_{d_{m_1,0,n_3}^W=i}·{\mathit{f}}^{\left(\mathit{d}\right)}\mid }_{d_{m_1,0,n_3}^W=i}.$$

The following theorem discusses the left-half part (see Figure 2) of the unimodal structure of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to each decision element $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,m_2\right\}$.

Theorem 5.

If $R\ge R_H^W$, then for any setup policy ${\mathit{d}}^W$ with ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$ and for each $n_3=1,2,\dots ,m_2$, the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is strictly monotone and increasing with respect to each decision element $d_{m_1,0,n_3}^W$ for $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,n_3\right\}.$

Proof of Theorem 5.

For each $n_3=1,2,\dots ,m_2$, we consider two setup policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^W& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^W,}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \\ \hfill {\mathit{d}}^{W^{\prime }}& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^{W^{\prime }},}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \end{array}$$

where $d_{m_1,0,n_3}^{W^{\prime }}=i_1>d_{m_1,0,n_3}^W=i_2$, and $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{0,1,\dots ,n_3\right\}$. Applying Lemma 1, it follows from (36)and (37) that

$$\begin{array}{cc}& {\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}\hfill \\ & ={\mathbf{\pi }}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left[\left({\mathbf{Q}}^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}-{\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\right){\mathit{g}}^{\left(\mathit{d}\right)}+\left({\mathit{f}}^{\left({\mathit{d}}^{W^{\prime }}\right)}-{\mathit{f}}^{\left({\mathit{d}}^W\right)}\right)\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)\left[-\left(i_1-i_2\right){\mu }_2{g}^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)\right.\hfill \\ & \hspace{1em}-\left(m_1{\mu }_1+i_2{\mu }_2\right)g^{\left(\mathit{d}\right)}\left(m_1,i_2,n_3-i_2\right)\hfill \\ & \hspace{1em}\left.+\left(m_1{\mu }_1+i_1{\mu }_2\right)g^{\left(\mathit{d}\right)}\left(m_1,i_1,n_3-i_1\right)-\left(i_1-i_2\right){\beta }_1\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)\left[m_1{\mu }_1{G}_1^{\left({\mathit{d}}^W\right)}-i_1{\mu }_2\left(G_2^{\left({\mathit{d}}^W\right)}+{\beta }_1\right)+i_2{\mu }_2\left(G_3^{\left({\mathit{d}}^W\right)}+{\beta }_1\right)\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^W\right)}.\hfill \end{array}$$

(38)

If $R\ge R_H^W$, then it is seen from Proposition 1 that $G^{\left({\mathit{d}}^W\right)}\ge 0$. Thus, we get that for the two policies ${\mathit{d}}^W⊠{\mathit{d}}^S,{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\in \mathcal{D}$ with $d_{m_1,0,n_3}^{W^{\prime }}>d_{m_1,0,n_3}^W$ and $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{0,1,\dots ,n_3\right\}$,

$${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}>{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}.$$

This shows that

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,0,n_3}^W=1}<{\eta }^{\mathit{d}}{\mid }_{d_{m_1,0,n_3}^W=2}<\cdots <{\eta }^{\mathit{d}}{{\mid }_{d_{m_1,0,n_3}^W=n_3-1}<{\eta }^{\mathit{d}}\mid }_{d_{m_1,0,n_3}^W=n_3}.$$

This completes the proof. □

When $R\ge R_H^W$, now we use Figure 2 to provide an intuitive summary for the main results given in Theorems 4 and 5. In the right-half part of Figure 2,

$$\begin{array}{cc}\hfill {\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}& ={\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)\left(d_{m_1,0,n_3}^W-n_3\right)\left[\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(1\right)}\right]\hfill \end{array}$$

shows that ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is a linear function of the decision element $d_{m_1,0,n_3}^W$. By contrast, in the right-half part of Figure 2, we need to first introduce a restrictive condition: $R\ge R_H^W$, under which

$${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^W\right)}.$$

Since $G^{\left({\mathit{d}}^W\right)}$ also depends on the decision element $d_{m_1,0,n_3}^W$, it is clear that ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is a nonlinear function of the decision element $d_{m_1,0,n_3}^W$.

6.1.2. The Sleep Policy with $R\ge R_H^S$

It is different from the setup policy in that, for the sleep policy, each decision element is $d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$. Hence, we just consider the structural properties of the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ with respect to each decision element $d_{m_1,n_2,n_3}^S$.

We write the optimal sleep policy as ${\mathit{d}}^{S^{*}}=\underset{{\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}}{argmax}\left\{{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}\right\},$ where

$$\begin{array}{cc}\hfill {\mathit{d}}^{S^{*}}& =\left(d_{m_1,1,0}^{S^{*}},d_{m_1,1,1}^{S^{*}},\dots ,d_{m_1,1,m_3-1}^{S^{*}};d_{m_1,2,0}^{S^{*}},\dots ,d_{m_1,2,m_3-2}^{S^{*}};\dots ;d_{m_1,m_2,0}^{S^{*}},\dots ,d_{m_1,m_2,m_3-m_2}^{S^{*}}\right).\hfill \end{array}$$

Then, it is seen that

$$\begin{array}{c}{d}_{m_1,1,0}^{S^{*}}\in \left\{m_2-1,m_2\right\},\cdots ,d_{m_1,1,m_3-1}^{S^{*}}\in \left\{m_2-1,m_2\right\};\\ d_{m_1,2,0}^{S^{*}}\in \left\{m_2-2,m_2-1,m_2\right\},\cdots ,d_{m_1,2,m_3-2}^{S^{*}}\in \left\{m_2-2,m_2-1,m_2\right\};\\ ⋮\hspace{1em}\hspace{1em}\\ d_{m_1,m_2,0}^{S^{*}}\in \left\{0,1,\dots ,m_2\right\},\cdots ,d_{m_1,m_2,m_3-m_2}^{S^{*}}\in \left\{0,1,\dots ,m_2\right\}.\end{array}$$

It is easy to see that the area of finding the optimal sleep policy ${\mathit{d}}^{S^{*}}$ is ${\left\{m_2-1,m_2\right\}}^{m_3}\times {\left\{m_2-2,m_2-1,m_2\right\}}^{m_3-1}\times \cdots \times {\left\{0,1,\dots ,m_2\right\}}^{m_3-m_2}$.

To find the optimal sleep policy ${\mathit{d}}^{S^{*}}$, we consider two sleep policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^S& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^S},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \\ \hfill {\mathit{d}}^{S^{\prime }}& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^{S^{\prime }}},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \end{array}$$

where $d_{m_1,n_2,n_3}^{S^{\prime }}=m_2-j_2>d_{m_1,n_2,n_3}^S=m_2-j_1$, $0\le j_2<j_1\le n_2$, it is easy to check from (2) that

$$\begin{array}{cc}& {\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}-{\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)=}\hfill \\ & \left(\begin{array}{ccccccccc}0& & 0& & 0& & & & \\ & \ddots & & \ddots & & \ddots & & & \\ & & 0& & 0& & 0& & \\ & & m_1{\mu }_1+j_2{\mu }_2& \cdots & -\left(m_1{\mu }_1+j_1{\mu }_2\right)& \cdots & -\left(j_2-j_1\right){\mu }_2& & \\ & & 0& & 0& & 0& & \\ & & & \ddots & & \ddots & & \ddots & \\ & & & & 0& & 0& & 0\end{array}\right).\hfill \end{array}$$

(39)

On the other hand, from the reward functions given in (6), $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}$ is in either $\left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$ for $1\le n_2\le m_2$ and $0\le n_3\le m_3-n_2$ or $\left\{0,1,\dots ,m_2\right\}$ for $n_2=m_2$ and $0\le n_3\le m_3-m_2,$ we have

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)& =-\left[R{\mu }_2-\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(2\right)}\right]d_{m_1,n_2,n_3}^S+R\left(m_1{\mu }_1+m_2{\mu }_2\right)\hfill \\ & \hspace{1em}-\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1-\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]\hfill \\ & \hspace{1em}-\left(n_2-m_2\right)C_3^{\left(2\right)}-m_1{\mu }_1{1}_{\left\{n_3=0\right\}}{C}_4\hfill \end{array}$$

and

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)& =-\left[R{\mu }_2-\left(P_{2,W}-P_{2,S}\right)C_1+C_3^{\left(2\right)}\right]d_{m_1,n_2,n_3}^{S^{\prime }}+R\left(m_1{\mu }_1+m_2{\mu }_2\right)\hfill \\ & \hspace{1em}-\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1-\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]\hfill \\ & \hspace{1em}-\left(n_2-m_2\right)C_3^{\left(2\right)}-m_1{\mu }_1{1}_{\left\{n_3=0\right\}}{C}_4.\hfill \end{array}$$

Hence, we have

$${\mathit{f}}^{\left({\mathit{d}}^{S^{\prime }}\right)}-{\mathit{f}}^{\left({\mathit{d}}^S\right)}={\left(0,0,\dots ,0,-\left(j_2-j_1\right){\mu }_2{\beta }_2,0,\dots ,0\right)}^T.$$

(40)

We write

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,n_2,n_3}^S=m_2-j}={\mathbf{\pi }}^{\left(\mathit{d}\right)}{{\mid }_{d_{m_1,n_2,n_3}^S=m_2-j}·{\mathit{f}}^{\left(\mathit{d}\right)}\mid }_{d_{m_1,n_2,n_3}^S=m_2-j}.$$

The following theorem discusses the structure of the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ with respect to each decision element $d_{m_1,n_2,n_3}^S$.

Theorem 6.

If $R\ge R_H^S$, then for any sleep policy ${\mathit{d}}^S$ with ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$ and for each $n_2=1,2,\dots ,m_2$, $n_3=0,1,\dots ,m_3-n_2$, the long-run average profit ${\eta }^{\mathit{d}}$ is strictly monotone decreasing with respect to each decision element $d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$.

Proof of Theorem 6.

For each $n_2=1,2,\dots ,m_2$ and $n_3=1,2,\dots ,m_3-n_2$, we consider two sleep policies with an interrelated structure as follows:

$$\begin{array}{c}{\mathit{d}}^S=\left(d_{m_1,1,0}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^S},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \\ {\mathit{d}}^{S^{\prime }}=\left(d_{m_1,1,0}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^{S^{\prime }}},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \end{array}$$

where $d_{m_1,n_2,n_3}^{S^{\prime }}=m_2-j_2>d_{m_1,n_2,n_3}^S=m_2-j_1$, $0\le j_2<j_1\le n_2$ and $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$. Applying Lemma 1, it follows from (39)and (40) that

$$\begin{array}{cc}& {\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}\hfill \\ & ={\mathbf{\pi }}^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left[\left({\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}-{\mathbf{Q}}^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\right){\mathit{g}}^{\left(\mathit{d}\right)}+\left({\mathit{f}}^{\left({\mathit{d}}^{S^{\prime }}\right)}-{\mathit{f}}^{\left({\mathit{d}}^S\right)}\right)\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)\left[\left(m_1{\mu }_1+j_2{\mu }_2\right)g^{\left(\mathit{d}\right)}\left(m_1,j_2,n_3+n_2-j_2\right)\right.\hfill \\ & \hspace{1em}\left.-\left(m_1{\mu }_1+j_1{\mu }_2\right)g^{\left(\mathit{d}\right)}\left(m_1,j_1,n_3+n_2-j_1\right)-\left(j_2-j_1\right){\mu }_2{g}^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)-\left(j_2-j_1\right){\mu }_2{\beta }_2\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)\left[m_1{\mu }_1{G}_1^{\left({\mathit{d}}^S\right)}+j_1{\mu }_2\left(G_2^{\left({\mathit{d}}^S\right)}+{\beta }_2\right)-j_2{\mu }_2\left(G_3^{\left({\mathit{d}}^S\right)}+{\beta }_2\right)\right]\hfill \\ & ={\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)G^{\left({\mathit{d}}^S\right)}.\hfill \end{array}$$

(41)

It is worthwhile to note that (41) has the same form as (38), since the perturbation of the sleep policy, $j_1$, and $j_2$ denote the number of the working servers. If $R\ge R_H^S$, then it is seen from Proposition 1 that for $j_2<j_1,$ we have $G^{\left({\mathit{d}}^S\right)}\ge 0$. Thus, we get that for $j_2<j_1$ and $j_1,j_2\in \left\{0,1,\dots ,n_2\right\}$,

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}>{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S},$$

this shows that ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is strictly monotone increasing with respect to $m_2-d_{m_1,n_2,n_3}^S$. Thus, we get that for the two policies ${\mathit{d}}^W⊠{\mathit{d}}^S,{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\in \mathcal{D}$ with $d_{m_1,n_2,n_3}^S>d_{m_1,n_2,n_3}^{S^{\prime }}$ and $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$,

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}<{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}.$$

It is easy to see that

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,n_2,n_3}^S=m_2-n_2}>{\eta }^{\mathit{d}}{{\mid }_{d_{m_1,n_2,n_3}^S=m_2-n_2+1}>\cdots >{\eta }^{\mathit{d}}\mid }_{d_{m_1,n_2,n_3}^S=m_2}.$$

This completes the proof. □

When $R\ge R_H^S$, now we use Figure 3 to provide an intuitive summary for the main results given in Theorems 6. According to (41), $G^{\left({\mathit{d}}^S\right)}$ depends on $d_{m_1,n_2,n_3}^S$, and it is clear that ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is a nonlinear function of $d_{m_1,n_2,n_3}^S$.

As a simple summarization of Theorems 5 and 6, we obtain the monotone structure of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to the asynchronous energy-efficient policy, while its proof is easy only on the condition that $R\ge R_H$ makes $R\ge R_H^W$ and $R\ge R_H^S$.

Theorem 7.

If $R\ge R_H$, then for any policy $\mathit{d}\in \mathcal{D}$, the long-run average profit ${\eta }^{\mathit{d}}$ is strictly monotone with respect to each decision element of ${\mathit{d}}^W$ and of ${\mathit{d}}^S$, respectively.

6.2. The Service Price $0\le R\le R_L$

A similar analysis to that of the case $R\ge R_H,$ we simply discuss the service price $0\le R\le R_L$ for the monotonicity and optimality for two different policies: the setup policy and the sleep policy.

6.2.1. The Setup Policy with $0\le R\le R_L^W$

Theorem 8.

If $0\le R\le R_L^W$, for any setup policy ${\mathit{d}}^W$ with ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$ and for each $n_3=1,2,\dots ,m_2$, then the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is strictly monotone decreasing with respect to each decision element $d_{m_1,0,n_3}^W\in \left\{0,1,\dots ,n_3\right\}$.

Proof of Theorem 8.

This proof is similar to that of Theorem 5. For each $n_3=1,2,\dots ,m_2$, we consider two setup policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^W& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^W,}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \\ \hfill {\mathit{d}}^{W^{\prime }}& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^{W^{\prime }},}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \end{array}$$

where $d_{m_1,0,n_3}^{W^{\prime }}=i_1>d_{m_1,0,n_3}^W=i_2$, and $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{0,1,\dots ,n_3\right\}$ for $1\le n_3\le m_2$. It is clear that

$${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^W\right)}.$$

If $0\le R\le R_L^W$, then it is seen from Proposition 1 that $G^{\left({\mathit{d}}^W\right)}\le 0$. Thus, we get that for the two setup policies with $d_{m_1,0,n_3}^{W^{\prime }}<d_{m_1,0,n_3}^W$ and $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{0,1,\dots ,n_3\right\}$,

$${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}<{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}.$$

This shows that for $1\le n_3\le m_2$,

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,0,n_3}^W=1}>{\eta }^{\mathit{d}}{\mid }_{d_{m_1,0,n_3}^W=2}>\cdots >{\eta }^{\mathit{d}}{{\mid }_{d_{m_1,0,n_3}^W=n_3-1}>{\eta }^{\mathit{d}}\mid }_{d_{m_1,0,n_3}^W=n_3}.$$

This completes the proof. □

When $0\le R\le R_L^W$, we also use Figure 4 to provide an intuitive summary for the main results given in Theorems 4 and 8.

6.2.2. The Sleep Policy with $0\le R\le R_L^S$

Theorem 9.

If $0\le R\le R_L^S$, then for any sleep policy ${\mathit{d}}^S$ with ${\mathit{d}}^W⊠{\mathit{d}}^S\in \mathcal{D}$ and for each $n_2=1,2,\dots ,m_2$, $n_3=0,1,\dots ,m_3-n_2$, the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is strictly monotone increasing with respect to each decision element $d_{m_1,n_2,n_3}^S$, for $d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$.

Proof of Theorem 9.

This proof is similar to that of Theorem 6. For each $n_2=1,2,\dots ,m_2$ and $n_3=0,1,\dots ,m_3-n_2$, we consider two sleep policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^S& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^S},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \\ \hfill {\mathit{d}}^{S^{\prime }}& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^{S^{\prime }}},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \end{array}$$

where $d_{m_1,n_2,n_3}^{S^{\prime }}=m_2-j_2>d_{m_1,n_2,n_3}^S=m_2-j_1$, $0\le j_2<j_1\le n_2$ and $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$. It is clear that

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)G^{\left({\mathit{d}}^S\right)}.$$

By a similar analysis to that in Theorem 6, if $0\le R\le R_L^S$, then it is seen from Proposition 1 that for $j_2<j_1,$ we have $G^{\left({\mathit{d}}^S\right)}\le 0$. Thus, we get that for $j_2<j_1$ and $j_1,j_2\in \left\{0,1,\dots ,n_2\right\}$, ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is strictly monotone decreasing with respect to $m_2-d_{m_1,n_2,n_3}^S$, hence it is also strictly monotone increasing with respect to $d_{m_1,n_2,n_3}^S$. Thus, we get that for the two sleep policies with $d_{m_1,n_2,n_3}^S<d_{m_1,n_2,n_3}^{S^{\prime }}$ and $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$,

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}<{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}.$$

This shows that

$${\eta }^{\mathit{d}}{\mid }_{d_{m_1,n_2,n_3}^S=m_2-n_2}<{\eta }^{\mathit{d}}{{\mid }_{d_{m_1,n_2,n_3}^S=m_2-n_2+1}<\cdots <{\eta }^{\mathit{d}}\mid }_{d_{m_1,n_2,n_3}^S=m_2}.$$

This completes the proof. □

When $0\le R\le R_L^S$, we also use Figure 5 to provide an intuitive summary for the main results given in Theorem 9.

As a simple summarization of Theorems 8 and 9, the following theorem further describes monotone structure of the long-run average profit ${\eta }^{\mathit{d}}$ with respect to the asynchronous energy-efficient policy, while its proof is easy only through using the condition that $0\le R\le R_L$ makes $0\le R\le R_L^W$ and $0\le R\le R_L^S$.

Theorem 10.

If $0\le R\le R_L$, then for any asynchronous energy-efficient policy $\mathit{d}\in \mathcal{D}$, the long-run average profit ${\eta }^{\mathit{d}}$ is strictly monotone with respect to each decision element of ${\mathit{d}}^W$ and of ${\mathit{d}}^S$, respectively.

In the remainder of this section, we discuss a more complicated case with the service price $R_L<R<R_H$. In this case, we use the bang–bang control and the asynchronous structure of $\mathit{d}\in \mathcal{D}$ to prove that the optimal asynchronous energy-efficient polices ${\mathit{d}}^{W^{*}}$ and ${\mathit{d}}^{S^{*}}$ both have bang–bang control forms.

6.3. The Service Price $R_L<R<R_H$

For the price $R_L<R<R_H$, we can further derive the following theorems about the monotonicity of ${\eta }^{\mathit{d}}$ with respect to the setup policy and the sleep policy, respectively.

6.3.1. The Setup Policy with $R_L^W<R<R_H^W$

For the service price $R_L^W<R<R_H^W$, the following theorem provides the monotonicity of ${\eta }^{\mathit{d}}$ with respect to the decision element $d_{m_1,0,n_3}^W$.

Theorem 11.

If $R_L^W<R<R_H^W$, then the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is monotone (either increasing or decreasing) with respect to the decision element $d_{m_1,0,n_3}^W$, where $n_3=1,2,\cdots ,m_3$ and $d_{m_1,0,n_3}^W\in \left\{0,1,\cdots ,n_3\right\}$.

Proof of Theorem 11.

Similarly to the first part of the proof for Theorem 5, we consider any two setup policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^W& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^W,}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \\ \hfill {\mathit{d}}^{W^{\prime }}& =\left(d_{m_1,0,1}^W,\dots ,d_{m_1,0,n_3-1}^W\underline{,d_{m_1,0,n_3}^{W^{\prime }},}{d}_{m_1,0,n_3+1}^W,\dots ,d_{m_1,0,m_2}^W,\dots ,d_{m_1,0,m_3}^W\right),\hfill \end{array}$$

where $d_{m_1,0,n_3}^W,d_{m_1,0,n_3}^{W^{\prime }}\in \left\{0,1,\dots ,n_3\right\}$. Applying Lemma 1, we obtain

$${\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^W\right)}.$$

(42)

On the other hand, we can similarly obtain the following difference equation

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S}=-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^{W^{\prime }}\right)}.$$

(43)

By summing (42) and (43), we have

$${\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^W\right)}-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)G^{\left({\mathit{d}}^{W^{\prime }}\right)}=0.$$

Therefore, we have the sign conservation equation

$$\frac{G^{\left({\mathit{d}}^W\right)}}{G^{\left({\mathit{d}}^{W^{\prime }}\right)}}=\frac{{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)}{{\pi }^{\left({\mathit{d}}^{W^{\prime }}⊠{\mathit{d}}^S\right)}\left(m_1,0,n_3\right)}>0.$$

(44)

The above equation means that the sign of $G^{\left({\mathit{d}}^W\right)}$ and $G^{\left({\mathit{d}}^{W^{\prime }}\right)}$ are always identical when a particular decision element $d_{m_1,0,n_3}^W$ is changed to any $d_{m_1,0,n_3}^{W^{\prime }}$. With the sign conservation Equation (44) and the performance difference Equation (43), we can directly derive that the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is monotone with respect to $d_{m_1,0,n_3}^W$. This completes the proof. □

Based on Theorem 11, the following corollary directly derives that the optimal decision element $d_{m_1,0,n_3}^{W^{*}}$ has a bang–bang control form (see more details in Cao [34] and Xia and Chen [35]).

Corollary 1.

For the setup policy, the optimal decision element $d_{m_1,0,n_3}^{W^{*}}$ is either 0 or $n_3$, i.e., the bang–bang control is optimal.

With Corollary 1, we should either keep all servers in sleep mode or turn on the servers such that the number of working servers equals the number of waiting jobs in the buffer. In addition, we can see that the search space of $d_{m_1,0,n_3}^W$ can be reduced from $\{0,1,\cdots ,n_3\}$ to a two-element set $\{0,n_3\}$, which is a significant reduction of search complexity.

6.3.2. The Sleep Policy with $R_L^S<R<R_H^S$

For the service price $R_L^S<R<R_H^S$, the following theorem provides the monotonicity of ${\eta }^{\mathit{d}}$ with respect to the decision element $d_{m_1,n_2,n_3}^S$.

Theorem 12.

If $R_L^S<R<R_H^S$, then the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is monotone (either increasing or decreasing) with respect to the decision element $d_{m_1,n_2,n_3}^S$, where $n_2=1,2,\dots ,m_2$, $n_3=0,1,\dots ,m_3-n_2$ and $d_{m_1,n_2,n_3}^S\in \left\{m_2-n_2,m_2-n_2+1,\dots ,m_2\right\}$.

Proof of Theorem 12.

Similar to the proof for Theorem 11, we consider any two sleep policies with an interrelated structure as follows:

$$\begin{array}{cc}\hfill {\mathit{d}}^S& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^S},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \\ \hfill {\mathit{d}}^{S^{\prime }}& =\left(d_{m_1,1,0}^S,d_{m_1,1,1}^S,\dots ,d_{m_1,n_2,n_3-1}^S,\underline{d_{m_1,n_2,n_3}^{S^{\prime }}},d_{m_1,n_2,n_3+1}^S,\dots ,d_{m_1,m_2,m_3-m_2}^S\right),\hfill \end{array}$$

where $d_{m_1,n_2,n_3}^S,d_{m_1,n_2,n_3}^{S^{\prime }}\in \left\{0,1,\dots ,m_2\right\}$. Applying Lemma 1, we obtain

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}={\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)G^{\left({\mathit{d}}^S\right)}.$$

(45)

On the other hand, we can also obtain the following difference equation:

$${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}-{\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}}=-{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)G^{\left({\mathit{d}}^{S^{\prime }}\right)}.$$

(46)

Thus, the sign conservation equation is given by

$$\frac{G^{\left({\mathit{d}}^S\right)}}{G^{\left({\mathit{d}}^{S^{\prime }}\right)}}=\frac{{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^S\right)}\left(m_1,n_2,n_3\right)}{{\pi }^{\left({\mathit{d}}^W⊠{\mathit{d}}^{S^{\prime }}\right)}\left(m_1,n_2,n_3\right)}>0.$$

(47)

This means that the signs of $G^{\left({\mathit{d}}^S\right)}$ and $G^{\left({\mathit{d}}^{S^{\prime }}\right)}$ are always identical when a particular decision element $d_{m_1,n_2,n_3}^S$ is changed to any $d_{m_1,n_2,n_3}^{S^{\prime }}$. We can directly derive that the long-run average profit ${\eta }^{{\mathit{d}}^W⊠{\mathit{d}}^S}$ is monotone with respect to $d_{m_1,n_2,n_3}^S$. This completes the proof. □

Corollary 2.

For the sleep policy, the optimal decision element $d_{m_1,n_2,n_3}^{S^{*}}$ is either $m_2-n_2$ or $m_2$, i.e., the bang–bang control is optimal.

With Corollary 2, we should either keep all in sleep or turn off the servers such that the number of sleeping servers equals the number of servers without jobs in Group 2. We can see that the search space of $d_{m_1,n_2,n_3}^S$ can be reduced from $\{m_2-n_2,m_2-n_2+1,\dots ,m_2\}$ to a two-element set $\{m_2-n_2,m_2\}$, hence this is also a significant reduction of search complexity.

It is seen from Corollaries 1 and 2 that the form of the bang–bang control is very simple and easy to adopt in practice, while the optimality of the bang–bang control guarantees the performance confidence of such simple forms of control. This makes up the threshold-type of the optimal asynchronous energy-efficient policy in the data center.

7. The Maximal Long-Run Average Profit

In this section, we provide the optimal asynchronous dynamic policy ${\mathit{d}}^{*}$ of the threshold-type in the energy-efficient data center and further compute the maximal long-run average profit.

We introduce some notation as follows:

$$\begin{array}{cc}\hfill c_0& =\left(P_{2,W}-P_{2,S}\right)C_1,\hfill \\ \hfill c_1& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1,\hfill \\ \hfill c_2& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1+m_1{C}_2^{\left(1\right)},\hfill \\ \hfill c_3& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1+m_1{C}_2^{\left(1\right)}+m_2{C}_3^{\left(1\right)},\hfill \\ \hfill c_4& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1+m_1{C}_2^{\left(1\right)}+m_1{\mu }_1{1}_{\left\{n_2>0,n_3=0\right\}}{C}_4,\hfill \\ \hfill c_5& =\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1+m_1{C}_2^{\left(1\right)}+m_2{C}_2^{\left(2\right)}+m_1{\mu }_1{1}_{\left\{n_2>0,n_3=0\right\}}{C}_4+\lambda 1_{\left\{n_2+n_3=m_3\right\}}{C}_5.\hfill \end{array}$$

(48)

Now, we express the optimal asynchronous energy-efficient policy ${\mathit{d}}^{*}$ of the threshold-type and compute the maximal long-run average profit ${\eta }^{{\mathit{d}}^{*}}$ under three different service prices as follows:

Case 1.

The service price $R\ge R_H$

It follows from Theorem 7 that

$$\begin{array}{c}{\mathit{d}}^{W^{*}}=\left(1,2,\dots ,n_3,\dots ,m_2,\dots ,m_2\right),\\ {\mathit{d}}^{S^{*}}=\left(m_2-1,\dots ,m_2-1;\dots ;m_2-n_2,\dots ,m_2-n_2;\dots ;1,\dots ,1;0,\dots ,0\right),\end{array}$$

thus we have

$$\begin{array}{cc}\hfill {\eta }^{{\mathit{d}}^{*}}& =\sum _{n_1=0}^{m_1}{\pi }^{\left(\mathit{d}\right)}\left(n_1,0,0\right)\left[\left(R{\mu }_1-C_2^{\left(1\right)}\right)n_1-c_1\right]\hfill \\ & \hspace{1em}+\sum _{n_3=1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)\left[R{m}_1{\mu }_1-c_2-\left(c_0+C_3^{\left(1\right)}\right)\left(n_3\wedge m_2\right)-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2=0}^{m_2}{\pi }^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)\left[R{m}_1{\mu }_1-c_4+\left(R{\mu }_2-c_0-C_2^{\left(2\right)}\right)n_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}+\sum _{n_3=m_3-m_2+1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,n_3\right)\left[R\left(m_1{\mu }_1+m_2{\mu }_2\right)-c_5-C_2^{\left(3\right)}{n}_3\right].\hfill \end{array}$$

Case 2.

The service price $0\le R\le R_L$

It follows from Theorem 10 that

$$\begin{array}{c}{\mathit{d}}^{W^{*}}=\left(0,0,\dots ,0\right),\\ {\mathit{d}}^{S^{*}}=\left(m_2,m_2,\dots ,m_2\right),\end{array}$$

thus we have

$$\begin{array}{cc}\hfill {\eta }^{{\mathit{d}}^{*}}& =\sum _{n_1=0}^{m_1}{\pi }^{\left(\mathit{d}\right)}\left(n_1,0,0\right)\left[\left(R{\mu }_1-C_2^{\left(1\right)}\right)n_1-c_1\right]+\sum _{n_3=1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,0,n_3\right)\left[R{m}_1{\mu }_1-c_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2=0}^{m_2}{\pi }^{\left(\mathit{d}\right)}\left(m_1,n_2,n_3\right)\left[R{m}_1{\mu }_1-c_4-\left(C_2^{\left(2\right)}+C_3^{\left(2\right)}\right)n_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}+\sum _{n_3=m_3-m_2+1}^{m_3}{\pi }^{\left(\mathit{d}\right)}\left(m_1,m_2,n_3\right)\left[R\left(m_1{\mu }_1+m_2{\mu }_2\right)-c_5-C_2^{\left(3\right)}{n}_3\right].\hfill \end{array}$$

Remark 5.

The above results are intuitive because when the service price is suitably high, the number of working servers is equal to a crucial number related to waiting jobs both in Group 2 and in the buffer; when the service price is lower, each server at the work state must pay a high energy consumption cost, but they receive only a low revenue. In this case, the profit of the data center cannot increase, so that all the servers in Group 2 would like to be closed at the sleep state.

Case 3.

The service price $R_L<R<R_H$

In Section 6.3, we have, respectively, proven the optimality of the bang–bang control for the setup and sleep policies, regardless of the service price R. However, if $R_L<R<R_H$, we cannot exactly determine the monotone form (i.e., increasing or decreasing) of the optimal asynchronous energy-efficient policy. This makes the threshold-type of the optimal asynchronous energy-efficient policy in the data center. In fact, such a threshold-type policy also provides us with a choice to compute the optimal setup and sleep policies, they not only have a very simple form but are also widely adopted in numerical applications.

In what follows, we focus our study on the threshold-type asynchronous policy, although its optimality is not yet proven in our next analysis.

We define a couple of threshold-type control parameters as follows:

$$\left\{\left({\theta }_1,{\theta }_2\right):{\theta }_1,{\theta }_2=0,1,\dots ,m_2\right\},$$

where ${\theta }_1$ and ${\theta }_2$ are setup and sleep thresholds, respectively. Furthermore, we introduce two interesting subsets of the policy set $\mathcal{D}$. We write ${\mathit{d}}_{{\theta }_1}^W$ as a threshold-type setup policy and ${\mathit{d}}_{{\theta }_2}^S$ as a threshold-type sleep policy. Let

$$\begin{array}{cc}& {\mathit{d}}_{{\theta }_1}^W\stackrel{\mathrm{def}}{=}\left(\underset{{\theta }_1-1 \mathrm{zeros}}{\underbrace{0,0,\dots ,0},}{\theta }_1,{\theta }_1+1,\dots ,m_2,\dots ,m_2\right),\hfill \\ & {\mathit{d}}_{{\theta }_2}^S\stackrel{\mathrm{def}}{=}\left(0,0,\dots ,0;\dots ;m_2-\left({\theta }_2+1\right),\dots ,m_2-\left({\theta }_2+1\right);m_2-{\theta }_2,\dots ,m_2-{\theta }_2;\underset{\left(m_3-\frac{1}{2}{\theta }_2\right)\left({\theta }_2-1\right) m_2\mathrm{s}}{\underbrace{m_2,\dots ,m_2}}\right).\hfill \end{array}$$

Then

$${\mathcal{D}}^{△}=\left\{{\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}:{\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}={\mathit{d}}_{{\theta }_1}^W⊠{\mathit{d}}_{{\theta }_2}^S,{\theta }_1,{\theta }_2=0,1,\dots ,m_2\right\}.$$

It is easy to see that ${\mathcal{D}}^{△}\subset \mathcal{D}$.

For an asynchronous energy-efficient policy ${\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}$, it follows from (4) to (7) that for $n_1=0,1,\dots ,m_1$ and $n_2=n_3=0,$

$$f\left(n_1,0,0\right)=R{n}_1{\mu }_1-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1-n_1{C}_2^{\left(1\right)};$$

for $n_1=m_1$, $n_2=0$ and $n_3=1,2,\dots ,{\theta }_1-1,$

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}_{{\theta }_1}^W\right)}\left(m_1,0,n_3\right)& =R{m}_1{\mu }_1-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1-\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right];\hfill \end{array}$$

for $n_1=m_1$, $n_2=0$ and $n_3={\theta }_1,{\theta }_1+1,\dots ,m_3,$

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}_{{\theta }_1}^W\right)}\left(m_1,0,n_3\right)& =R{m}_1{\mu }_1-\left\{m_1{P}_{1,W}+\left(n_3\wedge m_2\right)P_{2,W}\right.\hfill \\ & \hspace{1em}\left.+\left[m_2-\left(n_3\wedge m_2\right)\right]P_{2,S}\right\}{C}_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+n_3{C}_2^{\left(3\right)}\right]-\left(n_3\wedge m_2\right)C_3^{\left(1\right)};\hfill \end{array}$$

for $n_1=m_1$, $n_2=1,2,\dots ,{\theta }_2-1$ and $n_3=0,1,\dots ,m_3-n_2,$

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}_{{\theta }_2}^S\right)}\left(m_1,n_2,n_3\right) & =R{m}_1{\mu }_1-\left(m_1{P}_{1,W}+m_2{P}_{2,S}\right)C_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]\hfill \\ & \hspace{1em}-n_2{C}_3^{\left(2\right)}-m_1{\mu }_1{1}_{\left\{n_3=0\right\}}{C}_4;\hfill \end{array}$$

for $n_1=m_1$, $n_2={\theta }_2,{\theta }_2+1,\dots ,m_2$ and $n_3=0,1,\dots ,m_3-n_2,$

$$\begin{array}{cc}\hfill f^{\left({\mathit{d}}_{{\theta }_2}^S\right)}\left(m_1,n_2,n_3\right) & =R\left(m_1{\mu }_1+n_2{\mu }_2\right)-\left[m_1{P}_{1,W}+\left(m_2-n_2\right)P_{2,S}+n_2{P}_{2,W}\right]C_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+n_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]-m_1{\mu }_1{1}_{\left\{n_3=0\right\}}{C}_4;\hfill \end{array}$$

for $n_1=m_1$, $n_2=m_2$ and $n_3=m_3-m_2,m_3-m_2+1,\dots ,m_3$,

$$\begin{array}{cc}\hfill f\left(m_1,m_2,n_3\right)& =R\left(m_1{\mu }_1+m_2{\mu }_2\right)-\left(m_1{P}_{1,W}+m_2{P}_{2,W}\right)C_1\hfill \\ & \hspace{1em}-\left[m_1{C}_2^{\left(1\right)}+m_2{C}_2^{\left(2\right)}+n_3{C}_2^{\left(3\right)}\right]-\lambda 1_{\left\{n_3=m_3\right\}}{C}_5.\hfill \end{array}$$

Note that

$$\begin{array}{cc}\hfill {\eta }^{{\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}}& =\sum _{n_1=0}^{m_1}{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(n_1,0,0\right)f\left(n_1,0,0\right)\hfill \\ & \hspace{1em}+\sum _{n_3=1}^{m_3}{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(m_1,0,n_3\right)f^{\left({\mathit{d}}_{{\theta }_1}^W\right)}\left(m_1,0,n_3\right)\hfill \\ & \hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2=0}^{m_2}{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(m_1,n_2,n_3\right)f^{\left({\mathit{d}}_{{\theta }_2}^S\right)}\left(m_1,n_2,n_3\right)\hfill \\ & \hspace{1em}+\sum _{n_3=m_3-m_2+1}^{m_3}{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(m_1,m_2,n_3\right)f\left(m_1,m_2,n_3\right).\hfill \end{array}$$

It follows from (48) that the long-run average profit under policy ${\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}$ is given by

$$\begin{array}{cc}& {\eta }^{{\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}}=\sum _{i=0}^n{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(n_1,0,0\right)\left[\left(R{\mu }_1-C_2^{\left(1\right)}\right)n_1-c_1\right]\hfill \\ & \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{n_3=1}^{{\theta }_1-1}{\pi }^{\left({\mathit{d}}_{{\theta }_1}^W\right)}\left(m_1,0,n_3\right)\left[R{m}_1{\mu }_1-c_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{n_3={\theta }_1}^{m_3}{\pi }^{\left({\mathit{d}}_{{\theta }_1}^W\right)}\left(m_1,0,n_3\right)\left[R{m}_1{\mu }_1-c_2-\left(c_0+C_3^{\left(1\right)}\right)\left(n_3\wedge m_2\right)-n_3{C}_2^{\left(3\right)}\right]\hfill \\ & \hspace{1em}\hspace{1em}\hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2=1}^{{\theta }_2}{\pi }^{\left({\mathit{d}}_{{\theta }_2}^S\right)}\left(m_1,n_2,n_3\right)\left[R{m}_1{\mu }_1-c_4+\left(R{\mu }_2-c_0-C_2^{\left(2\right)}\right)n_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}\hspace{1em}\hspace{1em}+\stackrel{m_3-n_2}{\sum _{n_3=0}}\sum _{n_2={\theta }_2+1}^{m_2}{\pi }^{\left({\mathit{d}}_{{\theta }_2}^S\right)}\left(m_1,n_2,n_3\right)\left[R{m}_1{\mu }_1-c_4-\left(C_2^{\left(2\right)}+C_3^{\left(2\right)}\right)n_2-C_2^{\left(3\right)}{n}_3\right]\hfill \\ & \hspace{1em}\hspace{1em}\hspace{1em}+\sum _{n_3=m_3-m_2+1}^{m_3}{\pi }^{\left({\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}\right)}\left(m_1,m_2,n_3\right)\left[R\left(m_1{\mu }_1+m_2{\mu }_2\right)-c_5-C_2^{\left(3\right)}{n}_3\right].\hfill \end{array}$$

Let

$$\left({\theta }_1^{*},{\theta }_2^{*}\right)=\underset{\left({\theta }_1,{\theta }_2\right)\in \left\{0,1,\dots ,m_2\right\}}{argmax}\left\{{\eta }^{{\mathit{d}}_{\left({\theta }_1,{\theta }_2\right)}}\right\}.$$

Then, we call ${\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}$ the optimal threshold-type asynchronous energy-efficient policy in the policy set ${\mathcal{D}}^{△}$. Since ${\mathcal{D}}^{△}\subset \mathcal{D}$, the partially ordered set $\mathcal{D}$ shows that ${\mathcal{D}}^{△}$ is also a partially ordered set. Based on this, it is easy to see from the two partially ordered sets $\mathcal{D}$ and ${\mathcal{D}}^{\Delta }$ that

$${\eta }^{{\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}}\le {\eta }^{{\mathit{d}}^{*}}.$$

For the energy-efficient data center, if ${\eta }^{{\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}}={\eta }^{{\mathit{d}}^{*}}$, then we call ${\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}$ the optimal threshold-type asynchronous energy-efficient policy in the original policy set $\mathcal{D}$; if ${\eta }^{{\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}}<{\eta }^{{\mathit{d}}^{*}}$, then we call ${\mathit{d}}_{\left({\theta }_1^{*},{\theta }_2^{*}\right)}$ the suboptimal threshold-type asynchronous energy-efficient policy in the original policy set $\mathcal{D}$.

Remark 6.

This paper is a special case of the group-server queue (see Li et al. [6]), but it provides a new theoretical framework for the performance optimization of such queueing systems. It is also more applicable to large-scale service systems, such as data centers for efficiently allocating service resources.

Remark 7.

In this paper, we discuss the optimal asynchronous dynamic policy of the energy-efficient data center deeply, and such types of policies are widespread in practice. It would be interesting to extend our results to a more general situation. Although the sensitivity-based optimization theory can effectively overcome the drawbacks of MDPs, it still has some limitations. For example, it cannot discuss the optimization of two or more dynamic control policies synchronously, which is a very important research direction in dynamic optimization.

8. Conclusions

In this paper, we highlight the optimal asynchronous dynamic policy of an energy-efficient data center by applying sensitivity-based optimization theory and RG-factorization. Such an asynchronous policy is more important and necessary in the study of energy-efficient data centers, and it largely makes an optimal analysis of energy-efficient management more interesting, difficult, and challenging. To this end, we consider a more practical model with several basic factors, for example, a finite buffer, a fast setup process from sleep to work, and the necessary cost of transferring jobs from Group 2 either to Group 1 or to the buffer. To find the optimal asynchronous dynamic policy in the energy-efficient data center, we set up a policy-based block-structured Poisson equation and provide an expression for its solution by means of the RG-factorization. Based on this, we derive the monotonicity and optimality of the long-run average profit with respect to the asynchronous dynamic policy under different service prices. We prove the optimality of the bang–bang control, which significantly reduces the action search space, and study the optimal threshold-type asynchronous dynamic policy. Therefore, the results of this paper provide new insights to the discussion of the optimal dynamic control policies of more general energy-efficient data centers.

Along such a line, there are a number of interesting directions for potential future research, for example:

• Analyzing non-Poisson inputs such as Markovian arrival processes (MAPs) and/or non-exponential service times, e.g., the PH distributions;
• Developing effective algorithms for finding the optimal dynamic policies of the policy-based block-structured Markov process (i.e., block-structured MDPs);
• Discussing the fact that the long-run performance is influenced by the concave or convex reward (or cost) function;
• Studying individual optimization for the energy-efficient management of data centers from the perspective of game theory.