There has been a lot of research activity on scheduling control problems for queueing networks in the Halfin-Whitt regime. The discounted problem for multiclass manyserver queues was first studied in [1]. See also the work in [2,3]. For the ergodic control problem in the case of Markovian queueing networks see [4][5][6]. Scheduling control problems for queueing networks in random environments have also attracted much attention recently [7][8][9][10]. It is worth noting that in the study of asymptotic optimality in Markov-modulated environments, the scaling parameter depends on the rate of the underlying Markov process; see, for example, [7,10,11].
In this paper we consider queueing networks operating in alternating renewal (up-down) random environments, modeling service interruptions, and with renewal arrivals. It is well known that for large-scale service systems, service interruptions can have a dramatic impact on system performance [12]. For single class queues and networks in an alternating renewal environment, limit theorems have been studied in [12][13][14][15][16]. To the best of our knowledge, there are no studies on optimal scheduling control for multiclass many-server queues in alternating renewal environments, or even ergodic control in the Halfin-Whitt regime with arrivals that are renewal processes.
Specifically, we consider multiclass (d classes) G I /M/n + M queues with service interruptions in the Halfin-Whitt regime, where the arrival rate in each class and the number of servers in the pool are large, with a scaling parameter n, and the service interruptions are asymptotically negligible of order n -1 /2 . The service interruption is modeled as an alternating renewal process constructed by regenerative 'up' and 'down' cycles. In the 'down' state, all servers stop functioning, and new customers arrive, which may abandon the queue. In the 'up' state, the queueing system functions normally. We assume that at least one class of customers has a strictly positive abandonment rate. The scheduling policy determines the allocation of servers to different classes of customers. We approximate the scheduling problem via the corresponding control problem of the limiting jump diffusion in the heavy-traffic regime, for which a sharp characterization of optimal Markov controls is available [17], and use this to exhibit matching upper and lower bounds on the optimal scheduling performance for the queueing dynamics.
In Proposition 3.1, we establish a functional central limit theorem (FCLT) for the d-dimensional diffusion-scaled state processes under work-conserving scheduling policies. The limiting controlled processes are jump diffusions with piecewise linear drift and compound Poisson jumps. The proof of weak convergence relies on the construction of a modified diffusion-scaled state process, where we add the cumulative downtime to a diffusion-scaled state process without interruptions. We show that the modified and original diffusion-scaled state processes have the same weak limits, which are governed by the jump diffusions described above.
The discounted and ergodic control problems for a large class of jump diffusions arising from queueing networks in the Halfin-Whitt regime have been studied in [17], and these results are essential for establishing asymptotic optimality in the present paper. In Theorem 3.1, we show that the optimal value functions of the discounted problem for the diffusion-scaled processes converge to the corresponding function for the limiting jump diffusion. The proof of asymptotic optimality for the discounted problem follows the approach in [1], which deals with the discounted problem for multiclass G I /M/n + M queues. An essential part of this proof involves moment bounds for the diffusion-scaled state process, and the cumulative downtime process.
Asymptotic optimality for the ergodic control problem is more challenging. The result is stated in Theorem 3.2. Here, long-run average moment bounds for the diffusion-scaled state processes play a crucial role (see Proposition 4.2). Typically, such bounds are obtained in the literature via Foster-Lyapunov inequalities [4][5][6]10,18]. However, since the process counting the number of customers in each class, referred to as the queueing process, or state process, is not Markov, we first construct a sequence of auxiliary diffusion-scaled processes by adding the scaled residual time process of the alternating renewal process in the 'down' state to the original process, taking advantage of the fact that the long-run average moments of the scaled residual time process are negligible as the scaling parameter n tends to infinity (see equation (4.25)). We then consider the joint Markov process comprised of the auxiliary diffusion-scaled state process and the age processes of renewal arrival and alternating renewal processes, and construct Foster-Lyapunov functions, which bear a resemblance to the Lyapunov functions in [19]. In this part, we assume that the mean residual life functions are bounded, and use the criterion in [20,Theorem 4.2] to show that the joint Markov processes are positive Harris recurrent for all large enough n under some (modified) priority scheduling policy. We apply a two-step scheduling: first, the servers are allocated to the classes of customers with zero abandonment rate in such a manner that the servers used for each class do not exceed a certain proportion dictated by the traffic intensity; second, a static priority rule is applied to allocate the remaining servers. We show that the long-run average moments of the auxiliary diffusion-scaled state processes are bounded under this scheduling policy. We then establish a moment estimate for the difference between the auxiliary and original diffusion-scaled processes, and proceed to show that the analogous moment bounds hold for the original diffusion-scaled processes.
To prove asymptotic optimality for the ergodic control problem, we establish lower and upper bounds for the limits of the value functions (see Eqs. (5.10) and (5.28)). For the proof of the lower bound, we show that the sequence of mean empirical measures of the diffusion-scaled state processes is tight (see Lemma 5.2), and any limit of mean empirical measures is an ergodic occupation measure for the limiting jump diffusion. This is analogous to the technique used in [4][5][6]10]. However, characterizing the limits of mean empirical measures (see Theorem 5.2) is quite challenging here. Since we consider the diffusion-scaled processes with renewal arrivals in an alternating renewal environment, the martingale arguments in the above papers cannot be applied here. Instead, we develop a new approach. Following the technique of the proof of ergodicity under the specific scheduling policy described in the preceding paragraph, we consider the generator of the joint Markov process of the auxiliary diffusion-scaled state process, which incorporates the residual time process, and the associated age processes of the renewal arrivals and the alternating renewal environment. We construct suitable test functions (see (5.12)) which involve the coefficients of variation of interarrival times, and proceed to show the convergence of generators.
For the proof of the upper bound, we adopt the spatial truncation technique developed in [4], which is also used in [5,6,10], and is extended to jump diffusions in [17]. This involves a concatenated scheduling policy. We first construct a continuous precise -optimal control for the ergodic control problem for the limiting jump diffusion (see Proposition 5.1). Then, inside a compact set, we map this control to a scheduling policy for the diffusion-scaled process. On the complement of this set, we apply the (modified) priority scheduling policy. We show that the long run average moments of the diffusion-scaled state process are bounded under this concatenated scheduling policy (see Proposition 4.3), and the limit of mean empirical measures is the ergodic occupation measure of the limiting jump diffusion governed by the -optimal control (see Lemma 5.3). Here, the techniques used in establishing the long-run average moment bounds under the (modified) priority scheduling policy, and the convergence of mean empirical measures, play an important role.
The notation used in the paper is summarized in the next subsection. In Sect. 2, we describe the model of multiclass many-server queues with service interruptions. In Sect. 3, we define the diffusion-scaled processes and associated control problems, and state the main results on weak convergence and asymptotic optimality. In Sect. 4, we summarize the ergodic properties of the limiting controlled jump diffusion, and state the results concerning long-run average moment bounds for the diffusion-scaled processes. The proofs of Theorems 3.1 and 3.2 are given in Sect. 5. Appendix A is devoted to the proofs of Lemma 3.1 and Proposition 3.1. Appendix B contains the proofs of Lemmas 4.1 and 5.2.
We let | • | and •, • denote the standard Euclidean norm and the inner product in R d , respectively. For x ∈ R d , we let x := i |x i |, and x denote the transpose of x. The symbols R + , Z + , N, denote the set of nonnegative real numbers, nonnegative integers, and the set of natural numbers, respectively. The indicator function of a set
, respectively, a denotes the integer part of a, and a ± := (±a) ∨ 0. The complement and closure of a set A ⊂ R d are denoted by A c and Ā, respectively. We use the notation e i to denote the vector with ith entry equal to 1 and all other entries equal to 0. We also let e := (1, . . . , 1) T . We let B r denote the open ball of radius r in R d , centered at the origin. For a process {X t } t≥0 , τ(A) denotes the first exit time from the set A ⊂ R d , defined by τ(A) := inf {t > 0 : X t / ∈ A}, and we let τ r := τ(B r ).
By a slight abuse of notation, O(g) also denotes a generic member of these spaces.
For k ∈ N, we let D k := D(R + , R k ) denote the space of R k -valued cádlág functions on R + . When k = 1, we write D for D k . Given a Polish space E, by P(E) we denote the space of probability measures on E, endowed with the Prokhorov metric.
We consider a sequence of G I /M/n+M queueing models with d classes of customers. Let I := {1, . . . , d}. For the nth system, let {A n i (t)} t≥0 denote the arrival process of class-i customers. We assume that the arrivals are mutually independent renewal processes defined as follows. Let {G i, j : j ∈ N}, i ∈ I, be an i.i.d. sequence of strictly positive random variables with mean
. Then, we define
where λ n i > 0 denotes the arrival rate. For each n ∈ N, the service and patience times of the class-i customers are exponentially distributed with parameters μ n i and γ n i , respectively. We adopt the following standard assumption on the parameters (see [1,4,13]).
The parameters satisfy the following limits for each i ∈ I as n → ∞:
We assume that inf n∈N γ n d > 0. Assumption 2.1, which is also known as the Quality-and-Efficiency-Driven regime, implies that the system is critically loaded and
All queues are in the same up-down alternating renewal random environment. Waiting customers may abandon at any time. In the 'up' state, the system functions normally, and in the 'down' state all servers stop, while customers keep joining the queues and any jobs that have started service will wait for the system to resume. For this reason, we also refer to this model as multiclass queues with service interruptions. Let (u n k , d n k ) : k ∈ N be a sequence of i.i.d. positive random vectors denoting the up-down cycles, and define the counting process of downtimes by
and T n 0 ≡ 0. At time 0, the system is in the 'up' state.
For k ∈ N, we let (D k , M 1 ) and (D k , J 1 ) denote the space D k endowed with the Skorokhod M 1 and J 1 topologies, respectively (see, for example, [21,22]). Assumption 2.2 implies that the service interruptions are asymptotically negligible, and
where the limiting process N is a Poisson process with rate β. Define the server availability process n := { n (t) : t ≥ 0} by
for k ∈ N. We also define the cumulative up-time process
where {L t } t≥0 is a compound Poisson process with intensity L (dx)dt = β F d 1 (ϑdx)dt, where β is given in Assumption 2.2. For the nth system, we denote the processes counting the total number of customers, those in queue, and those in service, by
, and Z n = (Z n 1 , . . . , Z n d ) , respectively. These processes satisfy the following constraints:
and e, Z n (t) ≤ n (2.5)
for each t ≥ 0 and i ∈ I. We let
for i ∈ I, t ≥ 0, and r ≥ 0, where {S n * ,i , R n * ,i : i ∈ I, n ∈ N} are Poisson processes with rate one. We assume that for each n ∈ N, X n i (0), A n i , S n * ,i , R n * ,i : i ∈ I are mutually independent. These processes are governed by the equation
for each t ≥ 0, n ∈ N, and i ∈ I, where S n i (t) := S n i (t, 0) and R n i (t) := R n i (t, 0).
A scheduling policy is identified with a Z d + -valued stochastic process Z n with cádlág sample paths, which satisfies (2.5). Let
for i ∈ I. Recall the definitions of C n d in (2.4), and S n and R n in (2.6). Define the σ -fields
for t ≥ 0, where N is the collection of all P-null sets. We say that a scheduling policy
and so forth, where k denotes the jump size which takes values in a bounded set. Note that the integrals in (2.6) are finite by the definition of n in (2.3) and (2.5). Thus, given any non-anticipative scheduling policy Z n , and initial condition X n (0), there exists a unique solution to (2.7).
For x ∈ Z d + , we define the action set Z n (x) by
This map is invertible, and its inverse is given by
for e, X n (t) ≤ n.
Therefore, as far as control problems are concerned, we can use policies in U n or Z n interchangeably. Note that U n i can be considered as the proportion of class-i customers in the queue when there are waiting customers in the system.
Next, we augment the state space, and define the class of stationary Markov scheduling policies. Recall the definitions of A n , N n , and n in (2.1)-(2.3), respectively. Definition 2.1 Let H n i (t) denote the age process for the class-i customers, that is,
and define the age process K n for the alternating renewal process in the 'down' state by
Then, (A n i , H n i ), i ∈ I, and ( n , K n ) are strong Markov processes (see, e.g., [23]). We say that a scheduling policy
and we let Z n sm denote the class of these policies. Under a policy Z n ∈ Z n sm , the process
Abusing the notation, when z n depends only on its first argument, we simply write Z n (t) = z n X n (t) .
Let X n , Qn , and Ẑ n denote the diffusion-scaled processes defined by
respectively, for t ≥ 0 and i ∈ I. It follows by (2.7) that the process X n i takes the form
where
Let Ŵ n and Ŷ n , n ∈ N, be d-dimensional processes defined by
and
respectively. Then, X n i in (3.1) has the representation
The initial condition X n (0), n ∈ N, is assumed to be deterministic throughout the paper.
In Lemma 3.1 and Proposition 3.1 which follow, products or powers of the spaces (D d , J 1 ) and (D d , M 1 ) are viewed as metric spaces endowed with the maximum metric. The proofs of these results are given in Appendix A.
Lemma 3.1 Suppose that Assumptions 2.1 and 2.2 hold, and that { X n (0) : n ∈ N} is bounded. Then, under any sequence of U n ∈ U n , we have
where e 0 (t) ≡ (0, . . . , 0) for all t ≥ 0, and e ρ (t) ≡ (ρ 1 , . . . , ρ d ) .
Proposition 3.1 Grant the assumptions in Lemma 3.1. Then, the following hold.
where the matrix is given by :
with initial condition X 0 = x ∈ R d , where U is a limit of U n , and b(x, u) :
)
and Γ := diag(γ 1 , . . . , γ d ).
Moreover, any such limit U is non-anticipative, that is, for s < t,
Throughout the paper, the time variable appears as a subscript in the processes governing the limiting controlled jump diffusion in order to distinguish them from the processes associated with the nth system.
for some c > 0 and m ≥ 1. The running cost function R :
We only choose a running cost function as in (3.5) to simplify the exposition. One may replace (3.5) with a function R, which is locally Lipschitz continuous, and satisfies
for some positive constants c 1 , c 2 , and m ≥ 1. All the results still hold with (3.6). Moreover, the lower bound in (3.6) is not needed for the discounted problem (see, e.g., [1]).
The α-discounted control problem for the nth system is given by
where the cost criterion is defined by
For the controlled (jump) diffusion X in (3.3), we say that a control U is admissible if it takes values in S, and non-anticipative (see [17]). We denote the set of all admissible controls by U. The corresponding α-discounted cost criterion for the diffusion takes the form
and the optimal α-discounted value function is given by
where E U x denotes the expectation operator corresponding to the process under the control U , with initial condition x ∈ R d . We introduce the following assumption for the discounted problem.
We state the main result for the discounted problem in the next theorem, whose proof is given in Sect. 5.2. Theorem 3.1 Grant the hypotheses in Assumptions 2.1, 2.2, and 3.1, and suppose that
(3.8) Remark 3.2 Note that in Theorem 3.1, we do not need to impose any restrictions on the limiting abandonment rates {γ i : i ∈ I}.
We define the ergodic control problem for the diffusion-scaled process by
where the cost criterion Ĵ is given by
Here, the infimum is over all Markov scheduling policies, since for the ergodic control problem, we work with Markov processes. For the controlled jump diffusion in (3.3), the ergodic cost criterion, and the optimal ergodic value are defined by
respectively. By [17,Theorem 4.1], it follows that * is independent of x, and optimality is attained by a stationary Markov control.
We introduce the following assumption on G i and d 1 for the ergodic control problem. (i) The right derivative of F i (t) is finite, and F i (t) < 1, for all t ≥ 0 and i ∈ I. The distribution function F d 1 of d 1 satisfies the same property. (ii) The mean residual life functions of G i and d 1 are bounded, that is, there exists some positive constant C such that
and for all t ≥ 0.
Assumption 3.2 implies that all absolute moments of G i , i ∈ I, and d 1 are finite. The main result of the ergodic control problem is stated in the next theorem, whose proof is given in Sect. 5.3. Theorem 3.2 Grant Assumptions 2.1, 2.2, and 3.2. In addition, suppose that m in (3.5) is larger than 1, and that X n (0) → x ∈ R d as n → ∞. Then, we have
In this section, we present some ergodicity results for the limiting jump diffusion and the diffusion-scaled processes. These results are used to prove Theorem 3.2 in Sect. 5.3.
The controlled generator of the controlled limiting jump diffusion in (3.3) is given by Proposition 4.1 implies that the optimal control problems for the limiting jump diffusion are well-posed.
We denote the scaled hazard rate function of G i by r n i . This is defined by
where Ḟi denotes the right derivative of F i . Recall H n in (2.10). The extended generator of (A n , H n ) associated with the renewal arrival processes, denoted by H n , is given by
Remark 4. 2 We sketch the derivation of (4.2); see also
where
by the regenerative property of renewal process. Since Ḟi (t) is finite for all t ≥ 0, it follows that
, and lim
It is evident that lim s 0 r n i,0,s = 1 and lim s 0 r n i, j,s = 0 for j ∈ N. Thus, we obtain (4.2).
We define (compare this with [19])
Note that η n i is bounded by (3.10). The following identity is frequently used throughout the paper.
Recall that c 2 a,i denotes the squared coefficient of variation of G i . Let
for h i ∈ R + and i ∈ I. Note that the first term on the right-hand side of (4.5) is the second order residual life function. It follows by (3.10) that κ n i is bounded. Using (4.5), we obtain κ n i (0) = 0, and
The scaled hazard rate function of d 1 is defined by
Recall K n in (2.11). The extended generator of ( n , K n ) associated with the alternating renewal process, denoted by K n , is given by
In analogy to (4.4), we define
The following identities hold: α n (0) = 0, and
It follows by (4.9) that
Note that αn is bounded by (3.10).
To prove Theorem 3.2, we need to establish long-run average moment bounds for the diffusion-scaled processes under a class of scheduling policies, which agree with a proposed policy outside a compact set. We make this formal in Proposition 4.3. The proposed policy is given in the next definition. Let I 0 := {i ∈ I : γ i = 0}. If I 0 = ∅, then, without loss of generality, we assume that I 0 = {1, . . . , |I 0 |}, where |I 0 | denotes the cardinality of the set I 0 . In Definition 4.1 below, we introduce a modified priority scheduling policy which can be described as follows: First, nρ i/ i∈I 0 ρ i ∧ x i servers are allocated to each class i ∈ I 0 . Then, the remaining servers are allocated following the static priority rule.
The Markov policy žn is defined by
and
In obtaining long-run average moment bounds, since the queueing system is in an alternative renewal environment, we do not work with the diffusion-scaled processes directly. To utilize the fact that ( n , K n ) is a Markov process, we introduce the following auxiliary process. We define the 'unscaled' process X n by
for i ∈ I and t ≥ 0, where R n (t) is the residual time process for the system in the 'down' state given by
and N n u (t) is the process counting the number of completed 'up' periods by time t. Here, the second equality in (4.11) follows by the fact that given X n (0), n and Z n , the evolution equation in (2.7) admits a unique solution. Also, if n (t) = 1, then R n (t) = 0 and thus X n (t) = X n (t) a.s. Note that under a Markov policy z n ∈ Z n sm , the process ( X n , H n , n , K n ) is Markov with state space
and
Under z n ∈ Z n sm , the generator of ( X n , H n , n , K n ) denoted by Lz n n is given by
The operators on the right-hand side of (4.12) are defined by
and
In (4.13),
x,k denotes the conditional distribution of d n
given {d n 1 > k}, and
The first two terms on the right-hand side of (4.13) correspond to the extended generator associated with the renewal arrival processes. Compare this with (4.2). Conditioning on the alternative renewal process n in the 'up' state, the third term on the right-hand side of (4.13) corresponds to the service and abandonment processes, and I n,ψ corresponds to the residual time process R n together with n . Similarly, conditioning on the alternative renewal process in the 'down' state, the last two terms on the right-hand side of (4.13) correspond to the abandonment process and R n , respectively, and Q n,ψ corresponds to ( n , K n ). The generators in (4.14) and (4.15) are analogous to the extended generator associated with the alternating renewal process in (4.7).
We sketch the derivation of I n,ψ . The rest of the terms in (4.12) follow by the calculation below and Remark 4.2. To simplify the calculation, we assume that the arrival processes are Poisson, and only consider the ith component ( X n i , n , K n ), i ∈ I. Note that K n (t) = 0 when n (t) = 1. Since there are no simultaneous jumps w.p.1., here we only consider the jumps caused by n , that is, we consider
for s, t ≥ 0, where N n (t) denotes the number of jumps of n up to time t, and
By the memoryless property of 'up' times, and using the same calculation as in Remark 4.2 for 'down' times, it is straightforward to check that lim
and for any t ≥ 0. By the continuity of K n , we have lim
123 Thus, lim
This proves (4.14).
and
n denote the generator of the scaled joint process n := ( X n , H n , n , K n ) with X n := n -1 /2 ( X nnρ). The state space of n is given by
Then, under any z n ∈ Z n sm , we have
The next lemma concerns the ergodicity of the process n under the modified priority policy in Definition 4.1. Let V κ,ξ (x) := i∈I ξ i |x i | κ for x ∈ R d , where κ > 0, and ξ is a positive vector. Define the function
where η n i and α n are as in (4.3) and (4.8), respectively, and Ṽn κ,i (x i ) := -|x i | κ for x i ∈ R + and i ∈ I \ I 0 , and
The function V n κ,ξ is constructed in such a manner as to allow us to take advantage of the identities in (4.4) and (4.10). We define the set
Note that L žn n denotes the generator of n under the modified priority scheduling policy in Definition 4.1. We have the following lemma. Lemma 4.1 Grant Assumptions 2.1, 2.2, and 3.2. For any even integer κ ≥ 2, there exist positive constants C 0 and C 1 , a positive vector ξ ∈ R d + , and ñ ∈ N such that:
for all n > ñ, and ( x, h, y, k) ∈ D n . As a consequence, for all large enough n, n is positive Harris recurrent under the modified priority scheduling policy žn .
The proof of Lemma 4.1 is given in Appendix B. We continue with the following prop, which plays a crucial role in proving Proposition 4.3. In its proof, especially, equation (4.26), we show the relationship between the processes X n and X n . Proof Let κ ≥ 2 be an arbitrary even integer. By (4.18), we have
Since (ϑ n ) -1 is of order n -1 /2 by Assumption 2.2, it follows by Young's inequality together with (3.10) that there exist some positive constants c 0 and c 1 such that
) for all large n. Note that X n (0) = X n (0). Thus, by (4.20), we obtain
for some positive constants C 3 and C 4 . By dividing both sides of (4.21) by T , and taking T → ∞, we have sup n> ň lim sup
Let E ≡ E U n for some admissible scheduling policy U n . We have
We use the identity
for any s ≥ 0. Here R n (s) is the residual time of the system in the 'down' state, and thus E[(
] ≤ c 2 for some positive constant c 2 , by Assumption 2.2 and (3.10). Also, P(R n (s) > 0) = P( n (s) = 0), and it follows by [27,Theorem 3.4.4] that
which is of order n -1 /2 by Assumption 2.2. Therefore, applying (4.24), we obtain lim The next prop is used to prove the upper bound for the ergodic control problem in Sect. 5.3.2, where we adopt the spatial truncation technique developed in [4]. We first introduce a class of concatenated scheduling policies.
For a sequence v n : R d → S, n ∈ N, of continuous functions satisfying
as in Definition 4.2, we define the map
and the scheduling policy Proof For all sufficiently large n, we have
i=1 xi ≤ n, and thus z n [e d ] is equivalent to the modified priority policy on this set. Therefore, the result follows by the argument in Lemma 4.1 and Proposition 4.2.
In this subsection, we present some optimality results for the limiting jump diffusion. These results are used in proving asymptotic optimality.
Recall that a stationary Markov control v is called stable if the process under v is positive recurrent, and the set of such controls is denoted by U ssm . Let G denote the set of ergodic occupation measures, that is,
See [28, Sect. 2.1] for more details. We summarize the characterization of optimal controls for the limiting jump diffusion in the following theorem. Recall the definition of d 1 in Assumption 2.2.
] < ∞ with m as in (3.5). The following hold:
to the HJB equation
In addition, V α has at most polynomial growth with degree m. Moreover, a stationary Markov control v is optimal for the α-discounted problem if and only if it is an a.e. measurable selector from the minimizer in (5.2). (ii) There exists a solution V ∈ C 2,r (R d ), r ∈ (0, 1), to the HJB equation If we consider (3.9) over all stable Markov controls, then the ergodic control problem is equivalent to min π∈G R d ×U R(x, u) π(dx, du), see, for example, [17,Sect. 4]. We summarize a result on -optimal controls for the ergodic problem in the next prop, which follows directly by Corollary 7.1 in [17]. Note that the constant control v ≡ e d also satisfies Proposition 4.1. Recall that a stationary Markov control v is called precise if it is a measurable map from R d to U.
) m ] < ∞, with m as in (3.5). For any > 0, there exist a continuous precise control v ∈ U ssm , and R ≡ R( ) ∈ N such that v ≡ e d on Bc R , and v is -optimal, that is,
To prove Theorem 3.1, we use the approach developed in [1]. We first establish a key moment estimate for the diffusion-scaled process X n , whose proof is similar to that of [1, Lemma 3].
where c 1 and m 1 are some positive constants independent of n, x and t.
Proof Recall Ln and X n in (3.1), and Ŵ n in (3.2). Let ˆ n be a d-dimensional process defined by
Thus, we obtain
for all t ≥ 0 and i ∈ I. Following the same method as in [1, Lemma 3], we have
for some positive constants C 1 = sup{μ n i ρ i : n ∈ N, i ∈ I}, C 2 , and m 2 . The third inequality in (5.6) follows by the independence of N n and d i , and Assumption 3.1. On the other hand, for some positive constant C 3 , we have
Thus,
for some positive constant C 4 , where the second inequality follows by (5.7) and the independence of A n and n , and the third inequality follows by [29,Theorem 4] and (5.6). Therefore, following the argument in the proof of [1, Lemma 3], and using (5.5), (5.6), and (5.8), we establish (5.4). This completes the proof.
We first prove the lower bound:
By Theorem 5.1, the partial derivatives of V α (x) up to order two are locally Hölder continuous. Let
Compare this with (4.1). We define H(x, p)
where N L is the Poisson random measure of {L t : t ≥ 0} with the intensity L . Thus, applying (5.2), we obtain
where N L (t, A) = N L (t, A)t L (A) for any Borel set A ⊂ R. Repeating the same calculation as for the claim (71) in [1], we obtain
Note that N L is a martingale measure and V α is nonnegative. Taking expectations on both sides of (5.9), the second and fourth terms on the right-hand side of (5.9) vanish. Thus, first taking limits as l → ∞, and then as R → ∞, it follows by the monotone convergence theorem that
Applying Theorem 5.1 it follows that solutions of (5.2) have at most polynomial growth of degree m, which corresponds to [1, Proposition 5 (i)]. Note that Lemma 5.1 corresponds to Lemma 3 in [1]. The rest of the proof of the lower bound follows exactly the proof of [1,Theorem 4 (i)].
To prove (3.8), we construct a sequence of asymptotically optimal scheduling policies U n . Let v α be an optimal control to (5.2). Recall the quantization function in Definition 4.3. We define a sequence of scheduling policies
where žn is the modified priority policy in Definition 4.1, and
Here the policy on ( Xn ) c may be chosen arbitrarily. Let U n [v α ] be the equivalent parameterization of zn [v α ]. Following the proof of [1, Theorem 2 (i)], we obtain
where
Thus, by using the method in [1, Theorem 4 (ii)], and repeating the above calculation, we obtain lim sup
This completes the proof.
In this section, we prove Theorem 3.2 by establishing lower and upper bounds.
We show that lim inf n→∞ n X n (0) ≥ * .
(5.10)
The proof is given at the end of this subsection. We need the following lemma whose proof is similar to that of Proposition 4.2, and is given in Appendix B.
The main challenge in the proof lies in approximating the generator of the diffusionscaled process with the generator of the limiting jump diffusion. Recall the extended generator H n of (A n , H n ) in (4.2). We define the function φ n [ f ] by
and n ∈ N, where
(5.13)
The function φn 2, j [ f ] is defined analogously to (5.13) with f
respectively. Also,
(x) defined analogously to (5.13), and
We have the following lemma. Lemma 5.3 Grant Assumptions 2.1 and 3.2 (i). Then,
Using (4.4) and (4.6), and the Taylor expansion, we have
(5.15)
It is straightforward to verify that
for any
Applying (4.4) and (4.6), and combining the first term on the right-hand side of (5.16) with the third, fifth and sixth terms on the right-hand side of (5.15), we obtain the third term on the right-hand side of (5.14). We repeat this procedure until all the terms r n i are canceled. This proves (5.14).
We define the operator Ân :
respectively. Define the operator În by
, and β n u as in Assumption 2.2.
Recall the generator L z n n of n given in (4.16). The next lemma establishes the relation between the generator of the diffusion-scaled process and the operator in Definition 5.1.
(5.17)
, where qn = n -1 /2 q n , and
, if e, x > 0,
)
Proof Note that Lemma 5.3 concerns the renewal arrival process in the diffusionscale. Recall that
where
by a slight abuse of notation. It is clear that
by Assumption 2.1, and thus the third term in the sum on the right-hand side of (5. 19) is of order n -1 /2 . We next consider the fifth and sixth terms in the sum on the right-hand side of (5.19). Using the fact that
and
Recall the definition of Fd n 1
x,k in (4.13). Note that (5.21) where the second equality follows by Assumption 2.2 and (3.10). Note that qn i ≤ e, x + for i ∈ I and ( x, h, ψ, k) ∈ D n . Thus, the fourth term in the sum on the righthand side of (5. 19) is bounded by C(1 -ψ)(1 + e, x + ) for some positive constant
), and
Therefore, (5.17) follows by the boundedness of φ n [ f ] and (5.19). This completes the proof.
The mean empirical measure ζ z n T ∈ P(R d × S) associated with X n and a stationary Markov policy z n ∈ Z n sm is defined by
for any Borel sets A ⊂ R d and B ⊂ S, and with v n as in (5.18).
The following theorem characterizes the limit points of mean empirical measures.
Theorem 5.2 Grant the hypotheses in Theorem 3.2. Let {z n ∈ Z n sm : n ∈ N} be a sequence of policies satisfying (5.11). Then any limit point π
Proof It follows directly by Assumptions 2.1 and 2.2 that, for any
uniformly over compact sets of R d × S. Thus, in view of (5.22) and (5.1), in order to prove the theorem, it is enough to show that lim
Applying (5.11 and (4.26), we obtain
It follows by the same calculation as in (5.6) that, for some positive constant C 1 , we have
Using the facts that qn i ≤ e, x + and n (s) ∈ {0, 1}, and Young's inequality, we obtain
where C 2 is a positive constant. In (5.26), the second inequality follows by (5.25), and the convergence follows by (5.24) and the fact that m > 1. Applying Itô's formula to φ n [ f ], and using Lemma 5.4 and (5.24) and (5.26), it follows by the boundedness of
Therefore, using (4.26) again, we obtain (5.23). This completes the proof.
This implies that R x -ẑn [v]( √ n x + nρ) is uniformly integrable. By Lemma 5.5,
T converges in P(R d × S) to π v as (n, T ) → ∞. Applying Proposition 5.1, we deduce that v is an -optimal control for the running cost function. Since is arbitrary, (5.28) follows.
To prove Proposition 3.1, we first consider a modified process. Let X n = ( X n 1 , . . . , X n d ) be the d-dimensional process defined by
Lemma A. 1 As n → ∞, X n and X n are asymptotically equivalent, that is, if either of them converges in distribution as n → ∞, then so does the other, and both of them have the same limit.
Proof Let K = K ( 1 ) > 0 be the constant satisfying P( X n T > K ) < 1 for T > 0 and any 1 > 0, where X n T := sup 0≤t≤T X n (t) . Since Û n (s) ∈ S for s ≥ 0, on the event { X n T ≤ K }, we obtain
where C 1 and C 2 are some positive constants. Then, by Gronwall's inequality, on the event { X n T ≤ K }, we have
Thus, applying [13, Lemma 2.2], we deduce that for any 2 > 0, there exist 3 > 0 and n
As a consequence, X n -X n T ⇒ 0, as n → ∞, and this completes the proof.
We first prove (i). Define the processes
and Rn i (t) := n -1 /2 (R n (nt)nt), for i ∈ I. Then, since n (s) ∈ {0, 1} for s ≥ 0, applying Lemma 3.1 and Lemma 2.2 in [13], we have Using (A.1) and Proposition 3.1 (i), the proof of (ii) is same as the proof of [1, Lemma 4 (iii)].
To prove (iii), we first show any limit of X n in (A.2) satisfies (3.3). Following an argument similar to the proof of Lemma 5.2 in [13], one can easily show that the d-dimensional integral mapping x = (y, u) :
then, by the tightness of U n and the continuous mapping theorem, any limit of X n satisfies (A.2), and the same result holds for X n by Lemma A.1.
Recall the definition of τ n in (2.8). It is evident that Repeating the same argument we establish convergence of Ŝn and Rn . Proving that U is non-anticipative follows exactly as in [1]*Lemma 6. This completes the proof of (iii).
In this section, we construct two functions, which are used to show the ergodicity of n . We provide two lemmas concerning the properties of these functions, respectively. The proofs of Lemmas 4.1 and 5.2 are given at the end of this section.
Note that if d n 1 ≡ 0 for all n, the queueing system has no interruptions. In this situation, under a Markov scheduling policy, the (infinitesimal) generator of (X n , H n ) takes the form of (B.1). Recall the scheduling policies žn in Definition 4.1, and x = xnρ in Definition 4.2. We define the sets
We have the following lemma.
Lemma B.1 Grant Assumptions 2.1, 2.2, and 3.2. For any even integer κ ≥ 2, there exist a positive vector ξ ∈ R d + , n ∈ N, and positive constants C0 and C1 , such that the functions f n , n ∈ N, defined by
with η n i as defined in (4.3), satisfy
Proof Using the estimate
an easy calculation shows that
where for the fourth term on the right-hand side we also used the fact that
On the other hand, η n i (t) is bounded for all n ∈ N and t ≥ 0 by Assumption 3.2. Thus, applying (B.4), (B.5) and (4.4), it follows that
). Note that for i ∈ I \ I 0 , žn i is equivalent to the static priority scheduling policy. Note also, that
and for i ∈ I 0 \ Kn ( x), we have žn inρ i = xi and qn i = 0. By using (B.6), and the identity in (5.20), we obtain
Compared with [4, Lemma 5.1], the important difference here is that, for i ∈ I \ I 0 , we have
.
Repeating the argument in the proof of [4, Lemma 5.1], it follows by (B.8) that
for some positive constants c 3 , c 4 and c 5 . Therefore, (B.3) follows by (B.7) and (B.9), and this completes the proof.
Let
Recall L z n n,ψ in (4.13). We also define
(B.13) Note that q n,k i ≤ c(1+ e, x + ) for some positive constant c, by (5.21). Since z n i , q n i ≤ xi + nρ i , (ϑ n ) -1 is of order n -1 /2 by Assumption 2.2, and η n i and α n are bounded, it follows by (5.20)
Thus, applying Young's inequality, we obtain (B.11), and this completes the proof. for all large enough n, where x is defined in Definition 4.2. Since qn i ≥ 0 and žn i -nρ i > 0 for i ∈ Kn ( x), then by using (B.7) and (B.18), we see that (B.14) holds when y = 1.
For ψ = 0, using (B.15), Young's inequality, and the fact that for i ∈ Kn ( x), xi > 0, we obtain for some positive constant C and sufficiently small > 0. We proceed by invoking the argument in the proof of [4,Lemma 5.1]. The important difference here is that
x jnμ j ρ j (zk) ,
where the functions ˜ i , ¯ i : R d → [0, 1], for i ∈ I. Since ˜ i and ¯ i are bounded, we have some additional terms which are bounded by C R * nμ i ρ i (yk) Fd n 1
x,k (dy) for some positive constant C. Therefore, these are of order √ n by (5.21). Thus, repeating the argument in the proof of Lemma B.1, and applying Lemma B.2, we deduce that (B.14) holds with ψ = 0. This completes the proof.
Proof of Lemma 5. 2 The proof mimics that of Proposition 4.2. We sketch the proof when I 0 is empty. Using the estimate Therefore, dividing both sides of (B.23) by T , taking T → ∞ and using (4.26) again, we obtain (5.11). We may show that the result also holds when I 0 is nonempty by repeating the above argument and applying Lemma B.2. This completes the proof.