Abstract
We consider \(GI/Ph/n+M\) parallel-server systems with a renewal arrival process, a phase-type service time distribution, \(n\) homogenous servers, and an exponential patience time distribution with positive rate. We show that in the Halfin–Whitt regime, the sequence of stationary distributions corresponding to the normalized state processes is tight. As a consequence, we establish an interchange of heavy-traffic and steady-state limits for \(GI/Ph/n+M\) queues.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Parallel-server queueing systems with customer abandonment serve as a building block for modeling complex service systems such as customer call centers. Gans et al. [15] argued that best practice companies should operate a service system in a quality- and efficiency-driven (QED) regime, also known as the Halfin–Whitt regime. In this regime, the service system provides high-quality service and at the same time achieves high server utilization. This is possible only when there are a large number of servers working in parallel on a common pool of customers.
This paper focuses on a subset of \(GI/GI/n+M\) queueing systems. In such a queueing system, there are \(n\) identical servers serving customers whose interarrival times are i.i.d. following a general distribution (the first \(GI\)) and whose service times are i.i.d. following a general distribution (the second \(GI\)). In addition, customers’ patience times are i.i.d. following an exponential distribution (\(+M\)): when a customer’s waiting time in queue exceeds his patience time, the customer abandons the system without service.
Despite decades of research, there is still no general analytical or numerical tool to efficiently and accurately predict the steady-state performance of a \(GI/GI/n+M\) system. Computer simulation is often the only remaining tool available, but it can be slow when the number of servers is large, particularly when the system is in the QED regime.
Recently, Dai and He [8] proposed diffusion models to approximate a \(GI/Ph/n+M\) system when the service time distribution is of phase type. Their approximations are rooted in many-server heavy-traffic limit theorems proved in [7]. The numerical examples in [8] demonstrate that the steady-state performance of the diffusion model provides a remarkably accurate estimate for the steady-state performance of the corresponding queueing system, even when the number of servers is moderate. In this paper, we provide a justification for the diffusion approximation procedure in [8].
We now describe our results and contributions more precisely. When the number of servers \(n\) is fixed, a \(GI/Ph/n+M\) system can be represented by a certain continuous-time Markov process \(\mathbb {X}^n=\{\mathbb {X}^n(t): t\ge 0\}\). Often \(\mathbb {X}^n(t)\) converges in distribution to \(\mathbb {X}^n(\infty )\) as time \(t\rightarrow \infty \), where the random variable \(\mathbb {X}^n(\infty )\) has the stationary distribution of \(\mathbb {X}^n\). On the other hand, Dai et al. [7] shows that \(\tilde{\mathbb {X}}^n\), as a sequence of stochastic processes that are centered and scaled versions of \(\mathbb {X}^n\), converges in distribution to some diffusion process \(\tilde{\mathbb {X}}\) as \(n\rightarrow \infty \) under a heavy-traffic condition. The limit process \(\tilde{\mathbb {X}}\) is a piecewise Ornstein–Uhlenbeck (OU) process. A similar result was proved earlier in [23] for \(GI/Ph/n\) systems without customer abandonment. The convergence proved in [7] implies that each finite \(t\ge 0,\,\tilde{\mathbb {X}}^n(t)\) converges in distribution to \(\tilde{\mathbb {X}}(t)\), but, as in almost all diffusion limits, does not cover the case when \(t=\infty \). This paper proves that \(\tilde{\mathbb {X}}^n(\infty )\) converges in distribution to \(\tilde{\mathbb {X}}(\infty )\) as \(n\rightarrow \infty \); see Theorem 1 and Corollary 1 in Sect. 3 below. Often, one can also prove that \(\tilde{\mathbb {X}}(t)\) converges in distribution to \(\tilde{\mathbb {X}}(\infty )\) as \(t\rightarrow \infty \). Formally, our results can be stated as
which is known as the interchange limit theorem.
There has been a surge of interest in establishing interchange limit theorems in the last ten years in both the conventional heavy-traffic setting and many-server heavy-traffic setting. To prove an interchange limit theorem, when the stationary distribution of the limit process \(\tilde{\mathbb {X}}\) is unique, it is sufficient to prove that the sequence of random variables \(\{\tilde{\mathbb {X}}^n(\infty ): n\ge 1\}\) is tight. Gamarnik and Zeevi [11] pioneered an approach in proving tightness in the context of generalized Jackson networks in conventional heavy traffic when all distributions are assumed to have finite exponential moments. Key to their proof is the construction of a geometric Lyapunov function. Inspired by this work, Budhiraja and Lee [4] devised an alternative method to prove tightness along with some other results also in the context of generalized Jackson networks, but with the minimal two-moment assumption on all distributions. Budhiraja and Lee [4] did not construct a geometric Lyapunov function, but they cleverly utilized and sharpened a fluid limit approach introduced in [6], and their approach is potentially more general and obtains sharper results.
Our current paper follows the approach in [11] by constructing a geometric Lyapunov function; see Lemma 4 in Sect. 4 below. We heavily rely on a delicate analysis of the behavior of our Lyapunov functions applied to a fluid model for \(GI/Ph/n+M\) queues. In particular, when applied to the fluid model, we show that our Lyapunov function decreases at a rate that is proportional to the size of the fluid state when it is far away from origin; see part (b) of Lemma 7. Because of the customer abandonment in our model, when the waiting fluid is high, the decreasing rate in our Lyapunov function should be expected due to abandonment. However, when the waiting fluid is not high, but a large fluid state is due to the huge imbalance of servers among different service phases, the decreasing rate is by no means obvious. Our proof relies critically on a common quadratic function that was used in [10]. Using the common quadratic Lyapunov function, the authors were able to devise a Lyapunov function and prove the existence of the stationary distribution of the limit process \(\tilde{\mathbb {X}}\). The diffusion process \(\tilde{\mathbb {X}}\) has two different drifts in two separate regions of state space, and the Lyapunov function works well in these two regions. It remains an open problem whether the approach in [4] can be adapted to our setting. One major step in their approach is to obtain estimates on moments of the state process that are uniform in both time and the scaling parameter. In [4], the authors relied on the uniform Lipschitz property (with respect to time) of the Skorohod map to obtain such estimates. However, in our many-server queue setting, the map introduced in Lemma 2 does not have such property: it is Lipschitz continuous but the Lipschitz constant depends on time; see part (c) of Lemma 2.
In the many-server setting without customer abandonment, [17] is the first paper to establish a many-server diffusion limit for the \(GI/M/n\) model. In the same paper, they proved the tightness result. Gamarnik and Mom c̆ ilović [12] proves the tightness result where service time distribution is lattice-valued with a finite support. Gamarnik and Goldberg [14] has generalized this result to \(GI/GI/n\) queues. In a single class, multiple server pool model, Tezcan [26] proved asymptotic optimality of some routing policies and some interchange limit results.
In the many-server setting with customer abandonment, Gamarnik and Stolyar [13] proved a tightness result. In their model, customers have many classes. Each class has its own homogeneous Poisson arrival process, exponential service time distribution, and exponential patience time distribution with class-dependent rate. The service policy in choosing which class of customers to serve next can be arbitrary as long as it is non-idling. When the service policy is first-in-first-out across customer classes and the patience rate is independent of customer classes, their model reduces to a special case of our model considered in this paper. Their proof critically relies on the assumption that service time distributions are exponential and it remains an open problem whether their tightness result holds for non-exponential service time distributions. Empirical study in [2] suggests that the service time distributions are approximately lognormal, not exponential.
In the conventional heavy-traffic setting, Gurvich [16] systematically generalized the results in [11] to multiclass queueing networks. Katsuda [18] proves some interchange limit results for a multiclass single-server queue with feedback under various disciplines. Ye and Yao [27] studied interchange limit results in a head-of-line bandwidth sharing model with two customer classes and two servers.
The rest of the paper is organized as follows. Sect. 2 presents the background on \(GI/Ph/n+M \) queues and diffusion approximations. Assuming positive Harris recurrence, Sect. 3 summarizes our main results, Theorem 1 and Corollary 1. Section 4 introduces our Lyapunov function and a fluid model used to prove Lemma 4. Section 5 discusses a key lemma, Lemma 4, for proving Theorem 1. In Appendix 1, we prove the positive Harris recurrence of \(GI/Ph/n+M\) queues when \(n\) is fixed. Appendix 2 is devoted to the proof of a negative drift condition for the fluid model. Appendix 3 uses this negative drift condition for the fluid model to establish a negative drift condition for the diffusion-scaled processes.
1.1 Notation
All random variables and stochastic processes are defined on a common probability space \((\Omega ,\mathcal {F},\mathbb {P})\) unless otherwise specified. For a positive integer \(d,\,{\mathbb {R}}^{d}\) denotes the \(d\)-dimensional Euclidean space. Given a subset \(S\) of some Euclidean space, the space of right-continuous functions \(f :\mathbb {R}_+ \rightarrow S\) with left limits in \((0,\infty )\) is denoted by \(\mathbb {D}(\mathbb {R}_+,S)\) or simply \(\mathbb {D}(S)\). For a sequence of random elements \(\{X_n: n =1, 2, \ldots \}\) taking values in a metric space, we write \(X_n \Rightarrow X\) to denote the convergence of \(X_n\) to \(X\) in distribution. Each stochastic process with sample paths in \(\mathbb {D}(S)\) is considered to be a \(\mathbb {D}(S)\)-valued random element. The space \(\mathbb {D}(S)\) is assumed to be endowed with the Skorohod \(J_1\)-topology. Given \(x\in {\mathbb {R}}\), we set \(x^{+}=\max \{x,0\}\) and \(x^{-}=\max \{-x,0\}\). All vectors are envisioned as column vectors. For a \(K\)-dimensional vector \(u\), we write \(\left| u\right| \) for its Euclidean norm. Given \( y \in \mathbb {D}(S)\) and \(t>0\), we set \(\Vert y\Vert _{t} = \sup _{ 0 \le s \le t} |y(s)|\), where \(|\cdot |\) denotes the Euclidean norm in \(S\). Given a \(K \times K\) matrix \(M\), we use \(M^{\prime }\) to denote its transpose, and similarly for vector transposition. We write \(M_{ij}\) for its \((i,j)\)th entry. Let the matrix norm of \(M\) be \(|M|=\sum _{ij} |M_{i,j}|,\) where \(|M_{ij}|\) is the absolute value of \(M_{ij}\). We reserve \(I\) for the \(K\times K\) identity matrix and \(e\) for the \(K\)-dimensional vector of ones.
2 \(GI/Ph/n+M\) queues and diffusion approximations
In Sect. 2.1, we describe the \(GI/Ph/n+M\) queueing model and probabilistic assumptions and in Sect. 2.2 we state a diffusion limit under a many-server heavy-traffic condition.
2.1 Model description and probabilistic assumptions
In a \(GI/Ph/n+M\) system, there are \(n\) identical servers. We allow some of the system parameters to change with \(n\) as the number of servers increases. For the rest of this section, we keep \(n\) fixed. Customers arrive according to a delayed renewal process with interarrival times given by \(\{\xi ^n (i): i=0, 1, 2, \ldots \}\). We assume that \(\{\xi ^n(i): i=1,2, \ldots \}\) is a sequence of independent, identically distributed (i.i.d.) random variables with a general distribution and this sequence is independent of \(\xi ^n(0)\). Here, \(\xi ^n(0)\) is the time that the first customer after time \(0\) is to arrive at the system. Upon arrival, a customer enters service immediately if an idle server is available. Otherwise, he waits in a buffer with infinite waiting room that holds a first-in-first-out (FIFO) queue. When a server completes a service, the server picks the next customer from the FIFO queue if there is one waiting. Otherwise, the server becomes idle.
The service times are i.i.d. random variables, following a phase-type distribution which corresponds to the absorption time of a certain transient continuous-time Markov chain (the \(Ph\) in \(GI/Ph/n+M\) notation). Specifically, let \(p\) be a \(K\)-dimensional nonnegative vector with entries summing up to one, \(\nu \) be a \(K\)-dimensional positive vector, and \(P\) be a \(K \times K\) sub-stochastic matrix. We assume that the diagonal entries of \(P\) are zero and \(I-P\) is invertible. Consider a continuous-time Markov chain with \(K +1\) phases (or states) where phases \(1, 2, \ldots , K\) are transient and phase \(K +1\) is absorbing. The Markov chain has the initial distribution \(p\) on \(\{1, 2, \ldots , K\}\). Each time it enters phase \(k\), the amount of time it stays in phase \(k\) is exponentially distributed with mean \({1}/{\nu _k}\). Each time it leaves phase \(k\), the Markov chain enters phase \(j\) with probability \(P_{kj}\) or enters phase \(K+1\) with probability \(1-\sum _{j \le K}{P_{kj}}\). Once the Markov chain enters state \(K+1\), it stays there forever. A phase-type random variable with parameters \((p, \nu , P)\) is defined as the first time until the above continuous-time Markov chain reaches state \(K +1\).
As discussed in the introduction, each customer waiting in the queue has a patience time. The patience times are i.i.d. exponentially distributed with rate \(\alpha >0\). When a customer’s waiting time in queue exceeds his patience time, the customer leaves the system without service. Once a customer enters service, he does not abandon. The sequence of interarrival times, service times, and abandon times are assumed to be independent.
To describe the “state” of the system as time evolves, we let \(Z_{k}^{n}(t)\) denote the number of customers in phase \(k\) service in the \(n\)th system at time \(t\); service times in phase \(k\) are exponentially distributed with rate \(\nu _{k}\). We use \(Z^{n}(t)\) to denote the corresponding \(K\)-dimensional vector. We call \(Z^{n}=\{Z^{n}(t):t\ge 0\}\) the server-allocation process. Let \(N^{n}(t)\) denote the number of customers in the \(n\)th system at time \(t\), either in queue or in service. Let \(A^n(t)\) be the “age” of the interarrival time at time \(t\), i.e., the time between the arrival time of the most recent arrival before time \(t\) and time \(t\). Then, \((A^n,N^n, Z^n)\) is called the state processes for the \(n\)th system. It follows that for each \(n\) fixed the state process \((A^n,N^n, Z^n)\) has state space \(\mathcal{S} =\mathbb {R}_+\times \mathbb {Z}_+ \times \mathbb {Z}_+^K\). As time \(t\) goes on, \(A^n(t)\) increases linearly while \((N^n(t) , Z^n(t)) \) remains constant. When \(A^n(t)\) reaches the interarrival for the next arrival, it instantaneous jumps to zero. We adopt the convention that all processes are right continuous on \([0, \infty )\), having left limits in \((0, \infty )\). It follows that \((A^n,N^n, Z^n)\) is a piecewise deterministic Markov process that conforms to Assumption 3.1 of [9], and hence it is a strong Markov process [9, p. 362]. Throughout the paper, we make the following assumptions.
Assumption 1
The interarrival times \(\{\xi ^n (i): i=1, 2, \ldots \}\) from the second customer onwards have the following representation: \(\xi ^n(i)= \frac{1}{\lambda ^n} u(i),\,i\ge 1\), where \(\{u(i):i\ge 1\}\) is an i.i.d. sequence with \(\mathbb {E}(u(i))=1\) and \(\mathbb {E}(u(i))^2<\infty \).
Assumption 2
For each \(n\), the Markov process \((A^n, N^n, Z^n)\) is positive Harris recurrent and has stationary distribution \(\pi ^n\).
Assumption 1 appears to be restrictive. A consequence of the assumption is that the squared coefficient of variation (variance divided by squared mean) of interarrival times does not depend on the scaling parameter \(n\). All results in this paper can be shown to continue to hold if we adopt a triangular array of random variables to model the family of interarrival time sequences and impose some uniform integrability condition on the second moment; see, for example, (3.4) of [1]. As discussed in the introduction, the major motivation of this paper is to justify the diffusion model procedure in [8], which applies to any queueing system with a fixed arrival process that has no scaling parameter. We adopt the current assumption for notational simplicity without affecting the relevance of our results.
For the definition of positive Harris recurrence of a Markov process in Assumption 2, see, for example, [5]. Since our model allows customer abandonment, for each fixed \(n\), the queueing system should be stable in some sense. However, to prove that the Markov process is positive Harris recurrent, some conditions on the interarrival time distribution are needed. To keep our paper focused on the interchange of limits, we do not pursue the best sufficient conditions for positive Harris recurrence. Proposition 2 in Appendix 1 provides a sufficient condition on the interarrival distribution for Assumption 2 to hold.
2.2 Halfin–Whitt regime and diffusion limits
We describe a parameter regime, known as the Halfin–Whitt regime, that was first introduced in [17]. When the parameters are in this regime, certain diffusion processes serve as good approximations for \(GI/Ph/n+M\) systems. Most of the materials in this section can be found in [7], and readers are referred there for more details.
We consider a sequence of \(GI/Ph/n+M\) systems indexed by \(n\). The arrival rate \(\lambda ^n\) depends on \(n\). We assume that the service time and the patience time distributions do not depend on \(n\). Let \(1/\mu \) denote the mean service time. Since service time distribution is assumed to be phase type with parameters \((p, \nu , P)\) and the \(i\)th component of \((I-P')^{-1}p\) is the expected number of visits to phase \(i\) before the Markov chain is absorbed into state \(K+1\), the mean service time has the following formula:
In vector form, \(1/\mu = e' R^{-1}p\), where \(e\) is the (column) vector of ones and
Define
The quantity \(\rho ^n\) is said to be the traffic intensity of the \(n\)th system. We assume that
When condition (2.3) is satisfied, the sequence of systems is critically loaded, and is said to be in the QED regime or the Halfin–Whitt regime.
Setting
we call \(X^{n}=\{X^{n}(t):t\ge 0\}\) the centered total-customer-count process in the \(n\)th system. One can check that \((X^{n}(t))^{+}\) is the number of customers waiting in queue at time \(t\), and \((X^{n}(t))^{-}\) is the number of idle servers at time \(t\). Clearly,
Now, we define the diffusion-scaled state processes:
and
where
which is a \(K\)-dimensional vector since \(\mu \in \mathbb {R}_+\). It follows from (2.1) that \(\sum _{k=1}^{K}\gamma _{k}=1\). One interprets \(\gamma _{k}\) to be the fraction of busy servers in phase \(k\) service. We write \(\tilde{\mathcal{S}}^n\) for the state space of \((\tilde{A}^n,\tilde{X}^n,\tilde{Z}^n)\):
The following result establishes a many-server diffusion limit for a sequence of \(GI/Ph/n+M\) systems that operate in the Halfin–Whitt regime. Since the abandonment rate \(\alpha \) is positive, the limit process is positive recurrent.
Proposition 1
Consider a sequence of \(GI/Ph/n+M\) systems satisfying Assumption 1 and (2.3). Assume that \(\xi ^n(0)=0\) and \((\tilde{X}^{n}(0),\tilde{Z}^{n}(0))\Rightarrow (\tilde{X}(0),\tilde{Z} (0))\) for a pair of random variables \((\tilde{X}(0),\tilde{Z}(0))\). We then have
-
(a)
$$\begin{aligned} (\tilde{X}^{n},\tilde{Z}^{n})\Rightarrow (\tilde{X},\tilde{Z})\quad \text { as }n\rightarrow \infty , \end{aligned}$$(2.8)
where \((\tilde{X},\tilde{Z})\) is some continuous-time Markov process on
$$\begin{aligned} \tilde{\mathcal{S}}= \{ (x,z)\in \mathbb {R}\times \mathbb {R}^K: e' z + {x}^-=0\}. \end{aligned}$$(2.9) -
(b)
The Markov process \((\tilde{X}, \tilde{Z})\) given in (2.8) is positive recurrent and has a unique stationary distribution \(\pi \).
Proof
Part (a) follows from [7]. It is assumed in [7] that as \(n\rightarrow \infty \),
where
with \({E}^{n}(t)\) being the number of arrivals in \((0, t]\). Under Assumption 1 on the interarrival times, it follows from the functional central limit theorem that (2.10) holds.
Part (b) is an immediate corollary of Theorem 3 in [10]. \(\square \)
3 The main result
In this section, we work under Assumption 2. Let \(\tilde{\pi }_n\) be the stationary distributions of the diffusion-scaled state process \((\tilde{A}^n, \tilde{X}^n, \tilde{Z}^n)\) defined in (2.5) and (2.6). Now, we state the main theorem of this paper.
Theorem 1
Suppose that Assumptions 1 and 2 and the many-server heavy-traffic condition (2.3) hold. Assume that the abandonment rate \(\alpha \) is strictly positive. Then, the sequence of probability distributions \(\{\tilde{\pi }^n: n \ge 1 \}\) is tight.
The following corollary states the validity of interchange of heavy-traffic and steady-state limits. Since [10] proved that \((\tilde{X}, \tilde{Z})\) has a unique stationary distribution, the corollary follows from Theorem 1 by a standard argument; see [4, 11].
Corollary 1
Under the assumptions of Theorem 1, the sequence of marginal distributions of \(\tilde{\pi }^n\) on \((\tilde{X}^{n},\tilde{Z}^n)\) converges weakly to \(\pi \), where \(\pi \) is the unique stationary distribution of \((\tilde{X},\tilde{Z})\) and \((\tilde{X},\tilde{Z})\) is the diffusion process from Proposition 1.
4 Our Lyapunov function and a fluid model
In this section, we first introduce the Lyapunov function that lies at the heart of this paper. We then introduce a fluid model associated with the sequence of \(GI/Ph/n+M\) systems and assert that our Lyapunov function is a geometric Lyapunov function for the fluid model. The proof of our main result relies on a comparison between the diffusion-scaled processes and the fluid model.
To define our Lyapunov function, we first introduce a lemma on so-called common quadratic Lyapunov functions. The lemma was established in Theorem 1 of [10]. Recall that \(p\) is a discrete probability distribution on \(\{1, \ldots , K\}\), representing the initial distribution of the phase-type service time distribution, \(e\) is a vector of ones, and \(R\) is a matrix given in (2.2) and is obtained from the parameters of the phase-type service time distribution.
Lemma 1
There exists a \(K\times K\) positive definite matrix \(Q\) such that
Our Lyapunov function is the square root of a function \(g=g_\beta \) that depends on the “slack parameter” \(\beta \) in (2.3). It is defined as
where \(Q\) is given in Lemma 1, \(\gamma \) is defined in (2.7), and \(\kappa \) is a large positive constant to be determined later.
The quadratic function in (4.1) is slightly different from the one used in [10] in their Lyapunov function. Our modification is needed, because [10] focused on a \(K\)-dimensional state process, but the current paper focuses on the degenerate \((K+1)\)-dimensional state process \((\tilde{X}, \tilde{Z})\) on the manifold \(\tilde{\mathcal{S}}\); both state processes are equivalent. More importantly, the centering for \((x, z)\) in the two quadratic terms is different. Our centering allows us to obtain a stronger property for the fluid model; see part (a) of Lemma 7.
In addition, it is clear that when \(\beta \ge 0\), the function \(g\) achieves its minimum value 0 at \((x^*, z^*) = (-\beta , -\beta \gamma ) \in \tilde{\mathcal{S}}\). For \(\beta <0\), the function \(g\) achieves its minimum value \(\kappa \beta ^2 \gamma ' Q \gamma \) at \((\bar{x}^*, \bar{z}^*) = \left( -\frac{\mu \beta }{ \alpha }, 0\right) \in \tilde{\mathcal{S}}\). This can be verified by rewriting \(g(x,z)\) as follows:
where the second equality follows from Lemma 8 with constant \(b>0\), and in the last equality we have used the fact that \((x, z) \in \tilde{\mathcal{S}}\). We remark that if \(\beta <0\), both \(\sqrt{g}\) and \(\sqrt{g} - \sqrt{\kappa \beta ^2 \gamma ' Q \gamma }\) can serve as our Lypaunov function. Those two functions only differ by a constant, and the function \(\sqrt{g} - \sqrt{\kappa \beta ^2 \gamma ' Q \gamma }\) has a minimum value of zero on the manifold \(\tilde{\mathcal{S}}\). We use \(\sqrt{g}\) as our Lyapunov function for the sake of clarity of the presentation.
We now introduce a fluid model associated with \(GI/Ph/n+M\) systems. This fluid model is defined through a map, which is established in a more general setting in [7]. Recall the definition of \(\tilde{\mathcal{S}}\) in (2.9) and write
Lemma 2
Let \(\alpha >0\).
-
(a)
For each \((u,v)\in \mathbb {D}(\tilde{\mathcal{T}})\), there exists a unique \((x,z)\in \mathbb {D}(\tilde{\mathcal{S}})\) such that
$$\begin{aligned} x(t)&= u(t)-\alpha \int \limits _{0}^{t}(x(s))^{+}\, ds-e^{\prime }R\int \limits _{0} ^{t}z(s)\,ds,\end{aligned}$$(4.2)$$\begin{aligned} z(t)&= v(t)-p(x(t))^{-}-(I-pe^{\prime })R\int \limits _{0}^{t}z(s)\,ds \end{aligned}$$(4.3)for \(t\ge 0\).
-
(b)
For each \((u,v)\in \mathbb {D}(\tilde{\mathcal{T}})\), define \((x,z)=\Psi (u,v)\in \mathbb {D}(\tilde{\mathcal{S}})\), where \((x,z)\) satisfies (4.2) and (4.3). The map \(\Psi \) is well-defined and is continuous when both the domain \(\mathbb {D}(\tilde{\mathcal{T}})\) and the range \(\mathbb {D}(\tilde{\mathcal{S}})\) are endowed with the standard Skorohod \(J_{1}\)-topology.
-
(c)
The map \(\Psi \) is Lipschitz continuous in the sense that for any \(T>0\), there exists a constant \(C=C(T)>0\) such that
$$\begin{aligned} \Vert \Psi (y^{1})-\Psi (y^{2}) \Vert _T \le C \Vert y^{1}-y^{2}\Vert _T \quad \text { for any }y^{1},y^{2}\in \mathbb {D}(\tilde{\mathcal{T}}). \end{aligned}$$ -
(d)
The map \(\Psi \) is positively homogeneous in the sense that
$$\begin{aligned} \Psi (by)=b\Psi (y)\quad \text { for each }b>0\text { and each }y\in \mathbb {D}(\tilde{\mathcal{T}}). \end{aligned}$$
We now define the fluid counterpart of the diffusion-scaled state processes \((\tilde{X}^n, \tilde{Z}^n)\). Fix an initial state \((\tilde{x}(0), \tilde{z}(0))\in \tilde{\mathcal{S}}\). For \(t \ge 0\), we set
and, after noting that \((\tilde{u}(0),\tilde{v}(0))\in \mathbb {D}(\tilde{\mathcal{T}})\), set
We call \((\tilde{x}, \tilde{z})\) the fluid model starting from \((\tilde{x}(0),\tilde{z}(0))\). The next lemma is a negative drift condition for the fluid model and states that the function \(\sqrt{g}\) is a geometric Lyapunov function for the fluid model. Appendix 2 is devoted to its proof.
Lemma 3
Fix some \(t_0>0\). There exists constants \(C=C(t_0)>0\) and \(\epsilon =\epsilon (t_0)\in (0,1)\) such that for each initial state \((\tilde{x}(0), \tilde{z}(0))\in \tilde{\mathcal{S}}\), we have
5 Our Lyapunov function and diffusion-scaled processes
In this section, we present a negative drift condition for the diffusion-scaled processes, and we briefly outline how this leads to our main result. We use the same Lyapunov function \(\sqrt{g}\) as in the fluid model.
We are now ready to formulate our negative drift condition for the diffusion-scaled processes. Here and in the rest of this paper, we adopt the notational convention that
for each initial state \((a,x,z)\in \tilde{\mathcal{S}}^n\).
Lemma 4
Fix any \(t_0>0\). Under the assumptions of Theorem 1, there exists a nonnegative function \(g\) on \(\tilde{\mathcal{S}}\), as well as two constants \(C=C(t_0)>0\) and \(\epsilon =\epsilon (t_0) \in (0,1)\), such that for each \(n\) and each feasible initial state \((a,x,z)\in \tilde{\mathcal{S}}^n\), we have
The function \(\sqrt{g}\) satisfying (5.1) is essentially a geometric Lyapunov function with a geometric drift size \(1-\epsilon \) and drift time \(t_0\), see for instance Sect. 3 in [11]. Readers are referred to [11, 22] for more details on the definition of a Lyapunov function and its application in deriving bounds for stationary distributions of Markov processes.
The proof of the negative drift condition in Lemma 4 is lengthy and will be given in Appendix 3. Assuming the lemma, the proof of Theorem 1 is standard. We end this section by giving a sketch of the proof, which is almost identical to the proof of Theorem 5 in [11].
Proof Sketch of theorem 1
In order to show that \(\tilde{\pi }^n\) is tight, since \(\tilde{A}^n\Rightarrow 0\) as \(n\rightarrow \infty \) and \(g\) has compact level sets (see Appendix 2), it is sufficient to show that for any given \(\delta >0\), there exists some large constant \(s\), such that for all \(n\) sufficiently large,
By Markov’s inequality, it suffices to show that, for some \(C<\infty \),
where \(C\) and \(\epsilon \) are constants in (5.1). To prove (5.2), we use (5.1) in the following form:
We argue that the right-hand side is nonpositive after taking the expectation with respect to \(\tilde{\pi }^n\), and (5.2) then follows. For each integer \(k\ge 1\) and each \((x,z)\in \mathbb {R}\times \mathbb {R}^K\), set \(f_k(x, z) = \sqrt{g(x,z)} \wedge k\). It can be checked that \(f_k(x,z) - \mathbb {E}_{(a,x,z)} f_k ( \tilde{X}^n(t_0), \tilde{Z}^n(t_0) )\) is bounded below by \(-C\) for all \((a,x,z)\in \tilde{\mathcal{S}}^n\). Therefore, Fatou’s Lemma can be applied and we deduce that
where the equality follows from stationarity of \(\tilde{\pi }^n\). \(\square \)
References
Bramson, M.: State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. 30, 89–140 (1998)
Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S., Zhao, L.: Statistical analysis of a telephone call center. J. Am. Stat. Assoc. 100, 36–50 (2005)
Budhiraja, A., Ghosh, A.P.: Diffusion approximations for controlled stochastic networks: an asymptotic bound for the value function. Ann. Appl. Probab. 16, 1962–2006 (2006)
Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34, 45–56 (2009)
Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77 (1995)
Dai, J.G., Meyn, S.P.: Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Autom. Control 40, 1889–1904 (1995)
Dai, J.G., He, S., Tezcan, T.: Many-server diffusion limits for \({G/Ph/n+GI}\) queues. Ann. Appl. Probab. 20, 1854–1890 (2010)
Dai, J.G., He, S.: Many-server queues with customer abandonment: Numerical analysis of their diffusion models. Stoch. Syst. 3, 96–146 (2013)
Davis, M.H.A.: Piecewise deterministic Markov processes: a general class of non-diffusion stochastic models. J. R. Stat. Soc. B 46, 353–388 (1984)
Dieker, A.B., Gao, X.: Positive recurrence of piecewise Ornstein–Uhlenbeck processes and common quadratic Lyapunov functions. Ann. Appl. Probab. 23(4), 1291–1720 (2013)
Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16, 56–90 (2006)
Gamarnik, D., Momčilović, P.: Steady-state analysis of a multi-server queue in the Halfin–Whitt regime. Adv. Appl. Probab. 40, 548–577 (2008)
Gamarnik, D., Stolyar, A.L.: Multiclass multiserver queueing system in the Halfin–Whitt heavy traffic regime: asymptotics of the stationary distribution. Queueing Syst. 71, 25–51 (2012)
Gamarnik, D., Goldberg, D.: Steady-state \({GI/GI/N}\) queue in the Halfin–Whitt regime. Ann. Appl. Probab. 23, 2382–2419 (2013)
Gans, N., Koole, G., Mandelbaum, A.: Telephone call centers: tutorial, review, and research prospects. Manuf. Serv. Oper. Manag. 5, 79–141 (2003)
Gurvich, I.: Validity of heavy-traffic steady-state approximations in multiclass queueing networks: the case of queue-ratio disciplines. Math. Oper. Res. (2013). doi:10.1287/moor.2013.0593
Halfin, S., Whitt, W.: Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29, 567–588 (1981)
Katsuda, T.: State-space collapse in stationarity and its application to a multiclass single-server queue in heavy traffic. Queueing Syst. 65, 237–273 (2010)
Konstantopoulos, T., Last, G.: On the use of Lyapunov function methods in renewal theory. Stoch. Process. Appl. 79, 165–178 (1999)
Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes III: Foster–Lyapunov criteria for continuous time processes. Adv. Appl. Probab. 25, 518–548 (1993)
Meyn, S.P., Down, D.: Stability of generalized Jackson networks. Ann. Appl. Probab. 4, 124–148 (1994)
Meyn, S., Tweedie, R.L.: Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press, Cambridge (2009)
Puhalskii, A.A., Reiman, M.I.: The multiclass \(GI/PH/N\) queue in the Halfin–Whitt regime. Adv. Appl. Probab. 32, 564–595 (2004). Correction: 36, 971 (2004)
Revuz, D., Yor, M.: Continuous Martingales and Brownian Motion. Springer, Berlin (1999)
Rolski, T., Schmidli, H., Schmidt, V., Teugels, J.: Stochastic Processes for Insurance and Finance. Wiley, Chichester (1999)
Tezcan, T.: Optimal control of distributed parallel server systems under the Halfin and Whitt regime. Math. Oper. Res. 33, 51–90 (2008)
Ye, H.-Q., Yao, D.D.: Diffusion limit of a two-class network: stationary distributions and interchange of limits. ACM SIGMETRICS Perform. Eval. Rev. 38, 18–20 (2010)
Acknowledgments
JGD is supported in part by NSF Grants CMMI-0727400, CMMI-0825840, CMMI-1030589, and CNS-1248117. ABD is supported in part by NSF Grant CMMI-1252878, and he also gratefully acknowledges the hospitality of the Korteweg-de Vries Institute.
Author information
Authors and Affiliations
Corresponding author
Additional information
J. G. Dai: On leave from Georgia Institute of Technology.
Appendix
Appendix
1.1 Appendix 1: Positive Harris recurrence of \(GI/Ph/n+M\) queues
In this appendix, we provide a sufficient condition on the interarrival time distribution under which Assumption 2 holds. To study the positive Harris recurrence of a \(GI/Ph/n + M\) queue, we fix the number of server \(n\), as well as the interarrival distribution and phase-type service time distribution. Since \(n\) is fixed, unlike in Sect. 2.1, here, we drop the superscript \(n\) in all relevant quantities. Let \(\{\xi (i):i=0, 1, 2, \ldots \}\) be the sequence of interarrival times with \(\{\xi (i):i=1, 2, \}\) being an i.i.d. sequence and \(\xi (0)\) being the arrival time of the first customer after time \(0\). We use \(F\) to denote the cumulative distribution of \(\xi (1)\). We make the following assumptions on \(F\):
-
(a)
The distribution \(F\) is unbounded, i.e., \(F(x)<1\) for all \(x>0\).
-
(b)
The distribution \(F\) has a density, and furthermore the hazard function
$$\begin{aligned} h(x)= \frac{F'(x)}{1-F(x)} \quad \text { for } x \ge 0 \end{aligned}$$of the distribution \(F\) is locally bounded. Here, \(h(0) =F'(0)\) where \(F'(0)\) is interpreted as the right derivative of \(F\) at zero.
Recall that \(\alpha \) is the rate of the exponential distribution for patience times. For the definition of positive Harris recurrence, see, for example, [5]. In the following proposition, \(Q(t)\) is the number of waiting customers in queue at time \(t\). The other two quantities \(A(t)\) and \(Z(t)\) retain the meaning in Sect. 2.1.
Proposition 2
Suppose Assumptions (a)–(b) hold and \(\alpha >0\). The Markov process \(\{(A(t), Q(t), Z(t)): t\ge 0\}\) is positive Harris recurrent.
Proof
The process \(\{(A(t), Q(t), Z(t)): t\ge 0\}\) is known as a piecewise deterministic Markov process as defined in [9]; see also Chap. 11 in [25]. The main idea is to construct a suitable Lyapunov function \(f\) that is in the extended domain of the generator \(G\) of the Markov process. To construct the Lyapunov function, we first define the mean residual life function \(m(x)\) of the distribution function \(F\) by
We use \((a,q,z)=(a, q, z_1, \ldots , z_K) \in \mathcal{S}= {\mathbb {R}}_{+}\times \mathbb {Z}_+\times \mathbb {Z}_{+}^{K} \) to represent a state of the Markov process. For each state \((a,q,z)\), we define
The first component, \(F(a)( 1+m(a))\), is identical to a Lyapunov function introduced in Lemma 2.1 of [19]. We first verify that \(f\) is in the domain of the extended generator of the Markov process (see Definition 5.2 in [9] for the definition of extended generator). We use Theorem 11.2.2 in [25] (see also Theorem 5.5 in [9]) and check the three conditions there. Since the boundary set of the piecewise deterministic Markov process is empty, and the sample path of the age process \(A\) is absolutely continuous between jumps, it suffices to check that for each \(t \ge 0\)
where \(T_i\) are the jump epochs of the Markov process \(\{(A(t), Q(t), Z(t)): t\ge 0\}\). It follows from the proof of Lemma 2.1 and Eq. (2.5) in [19] that
Thus, in order to establish (6.2), we know from (6.1) that it is enough to show
To show (6.3), we note that the number of customer departures within \([0, t]\), due to either service completion or abandonment, is bounded by \( q +n + E(t)\). Therefore,
from which (6.3) follows because
See, e.g., Lemma 3.5 in [3].
Now, we can write down the extended generator for the piecewise deterministic Markov process \(\{(A(t), Q(t), Z(t)): t\ge 0\}\). For \(\sum _k z_k=n,\,q>0\) and \(a\ge 0\), it follows from (5.7) of [9] that
where in the second equality we have used the fact that \(F(0)=0\), and the inequality follows from the derivation on p. 170 of [19]. Since
there exists some \(C_1>0\) such that
Combining (6.4) and (6.5), we have for \(a>C_1\) and \(q>0\)
For any \(a\ge 0\), \(q=0\), and \(z\ge 0\), one can check that (6.6) continues to hold with \(\sum _{k}\nu _k\) in (6.6) being replaced by \( \sum _{k: z_k>0}\nu _k\). Therefore, we have for \(a>C_1\), any \(q\in \mathbb {Z}_+\), and any \(z\in \mathbb {Z}_+^K\),
Let
which is finite by Assumption (b) on \(F\). It follows from (6.4) that for \(a\in [0, C_1]\) and \(q\ge C_2=(H+1)/\alpha \), (6.7) also holds. It follows that
where \(B\) is the compact set given by
Since \(F\) is assumed to have density, it is spread out. Together with Assumption (6) on \(F\), this implies that the set \(B\) is a closed petite set in the state space \(\mathcal{S}={\mathbb {R}}_{+}\times \mathbb {Z}_+\times \mathbb {Z}_{+}^{K} \); see, e.g., the proof of Lemma 3.7 of [21]. It follows from (6.8) and Theorem 4.2 of [20] that the Markov process \(\{(A(t), Q(t), Z(t)): t\ge 0\}\) is positive Harris recurrent. \(\square \)
1.2 Appendix 2: Negative drift condition for the fluid model
It is the goal of this appendix to establish the negative drift condition for the fluid model, i.e., to prove Lemma 3. Throughout, we let \(( \tilde{x}, \tilde{z})\) be defined through (4.5), i.e., as output of the map \(\Psi \) with input given in (4.4). The initial condition \((\tilde{x}(0),\tilde{z}(0))\in \tilde{\mathcal{S}}\) is arbitrary.
We start with several auxiliary lemmas, which establish key properties of our Lyapunov function and the fluid model. Their proofs are deferred to the end of this appendix. The next lemma says that \(\sqrt{g}\) is Lipschitz continuous.
Lemma 5
There exists a constant \(C\) such that
for any \((x^1,z^1),(x^2,z^2)\in \tilde{\mathcal{S}}\).
The next lemma implies that \((\tilde{x}(t),\tilde{z}(t))\) has derivatives with respect to \(t\) almost everywhere.
Lemma 6
The function \(t\mapsto (\tilde{x}(t),\tilde{z}(t))\) is locally Lipschitz continuous.
We next formulate two important properties of the function \({g}\) with fluid model input.
Lemma 7
Let \((\tilde{x},\tilde{z})\) be the fluid model on \(\tilde{\mathcal{S}}\) from Sect. 4.
-
(a)
For any \((\tilde{x}(0),\tilde{z}(0))\in \tilde{\mathcal{S}}\), we have
$$\begin{aligned} \frac{{dg(\tilde{x}(t), \tilde{z}(t))}}{{dt}} \le 0, \end{aligned}$$whenever \( {g (\tilde{x}(t), \tilde{z}(t))} \) is differentiable at \(t\).
-
(b)
There are positive constants \(c, C\), and \(M\) such that, for any \((\tilde{x}(0),\tilde{z}(0))\in \tilde{\mathcal{S}}\) such that \(|(\tilde{x}(t), \tilde{z}(t)) | \ge M\) and such that \(g(\tilde{x}(t),\tilde{z}(t))\) is differentiable at \(t\), we have
$$\begin{aligned} - C \cdot g(\tilde{x}(t),\tilde{z}(t)) \le \frac{dg(\tilde{x}(t),\tilde{z}(t))}{dt} \le - c \cdot g(\tilde{x}(t),\tilde{z}(t)). \end{aligned}$$
With these three lemmas at our disposal, we are ready to prove the negative drift condition for the fluid model.
Proof of Lemma 3
Throughout this proof, when using constants from auxiliary lemmas, their subscript denotes the lemma they originated from.
Since \(g(-\beta ,-\beta \gamma )=0\) or \(g(-\mu \beta /\alpha ,-\beta \gamma )=0\), one obtains from Lemma 5 that there exists some \(C_{5}\) such that for arbitrary \((x,z)\)
Let \(c_{7},C_{7},M_{7}\) be the constants defined in Lemma 7, and set
It follows from (6.9) that if
we have \(|(\tilde{x}(t), \tilde{z} (t))| \ge M_{7}\) and thus by the second part of Lemma 7,
Pick some \(C'\) such that
The constants \(\epsilon \) and \(C\) from the statement of the lemma can be chosen as follows:
as we now verify. If \(\sqrt{g(\tilde{x}(0),\tilde{z}(0))} \le C'\), then we have, by Lemma 6 and the first part of Lemma 7,
We next consider the case \(\sqrt{g(\tilde{x}(0), \tilde{z} (0))} >C'\). We want to show that in this case
which, together with (6.10), implies that
To establish (6.12), we assume that \( \sqrt{g(\tilde{x}(0), \tilde{z} (0))} >C' \) and define
One readily checks that \(\tau >0\), and we now show that in fact \(\tau > t_0\). If \(\tau = \infty ,\) the claim is true. Now, we assume \(\tau < \infty \). For \(t \in [0, \tau )\), we have
where we have used the definition \(\tau \). Now, we can apply (6.10) for \(t \in [0, \tau ),\) and obtain
On combining this with the definition of \(\tau ,\) it follows that if \(\sqrt{g(\tilde{x}(0), \tilde{z} (0))} >C',\)
where we use (6.11) in the last inequality. This shows that \(\tau > t_0\), which proves (6.12) and, therefore, the statement of the lemma. \(\square \)
1.2.1 Proofs of auxiliary lemmas
We now prove Lemmas 5, 6, and 7.
Proof of Lemma 5
We first discuss the case \(\beta \ge 0\). In that case, we have \(g(x,z) = \Vert (x+\beta , z+\beta \gamma ) \Vert ^2_{Q}\), where
Note that \(\Vert \cdot \Vert _{ Q} \) defines a norm since \(Q\) is positive definite.
Thus for \(\beta \ge 0\), there exists a constant \(C>0\) such that
where the first inequality follows from the subadditivity property of the norm \(\Vert \cdot \Vert _{ Q}\), and the last inequality follows from the equivalence of the \(|\cdot |\)-norm and the \(\Vert \cdot \Vert _{ Q}\)-norm on the Euclidean space \(\mathbb {R}^{K+1}\). We, therefore, obtain the claim when \(\beta \ge 0\). The claim for \(\beta <0\) can be established similarly. \(\square \)
Proof of Lemma 6
Since \(t\mapsto (\tilde{u}(t), \tilde{v} (t) )\) is continuous in \(t\), we deduce from Lemma 9 in [7] that \(t\mapsto ( \tilde{x}(t), \tilde{z} (t))\) is also continuous in \(t\). It follows from (4.2) that \(t\mapsto \tilde{x}(t)\) is locally Lipschitz continuous. Moreover, using the fact that for all \(s, t\ge 0\),
we conclude from (4.3) that \(\tilde{z}(\cdot )\) is also locally Lipschitz continuous; hence \((\tilde{x}(\cdot ), \tilde{z} (\cdot ))\) is locally Lipschitz. \(\square \)
For the proof of Lemma 7, we need to study derivatives of the fluid model. From (4.2), (4.3), (4.4), and (4.5), it is straightforward to see that when \( \tilde{x}(t) \ge 0\), we have \(e'\tilde{z}(t)=0\) and
On the other hand, when \( \tilde{x}(t)<0\), we have \(e' \tilde{z}(t)=\tilde{x}(t), \) and
We need two properties of the matrix \(Q\) from Lemma 1, which are recorded in the following lemma.
Lemma 8
Let \(Q\) be a positive definite matrix from Lemma 1.
-
(a)
\(Q\gamma = b e\) for some \(b>0\).
-
(b)
Up to a multiplicative constant, \(\gamma \) is the only vector satisfying
$$\begin{aligned}{}[Q (I-pe')R + R'(I-ep') Q]\gamma =0. \end{aligned}$$
Proof
One directly verifies that \(\gamma = \mu R^{-1} p\) satisfies
Lemma 1 states that \(Q(I-pe')R+ R'(I - ep')Q\) is a positive semi-definite matrix; thus, we deduce that
which immediately implies that \(Q(I-pe')R \gamma =0\) by definition of \(\gamma \). Since \((I-pe')\) has a simple zero eigenvalue and \(R\) is nonsingular, we must have
In addition, left-multiplying \(\gamma '\) at both sides of the above equality, we obtain that \(b=\gamma 'Q\gamma >0\), using the fact that \(Q\) is positive definite.
As a corollary to part (a), we obtain \((I-ep') Q R^{-1} p = 0\), which we use in the proof of part (b): it implies that
Lemma 1 states that \(QR+R'Q\) is positive definite. After left-multiplying by \((R^{-1})'\) and right-multiplying by \(R^{-1}\), we find that \(QR^{-1}+(R^{-1})'Q\) is also positive definite. Since \((I-pe')R\) has rank \(K-1\) and has a simple zero eigenvalue with a right eigenvector \(\gamma = \mu R^{-1} p\), we obtain from the preceding display that \(\gamma = \mu R^{-1} p\) is the unique vector (up to a constant) such that
This implies part (b) of the lemma. \(\square \)
The next corollary controls the term involving \(z\) in our Lyapunov function.
Lemma 9
There exist constants \(c,C>0\) such that, whenever the derivative exists,
as long as \(e'\tilde{z}(t)=0\) or equivalently \(\tilde{x}(t)\ge 0\).
Proof
It is readily seen with part (a) of Lemma 8 that
Since \(e'\gamma =1\ne 0\), we deduce from Lemma 1 and part (b) of Lemma 8 that the quadratic form \(h'[Q (I-pe')R + R'(I-ep') Q] h\) has a global (nonzero) minimum and maximum over the compact set \(\{h \in \mathbb {R}^K: e'h = 0, |h| =1\}\). This yields the statement of the lemma. \(\square \)
We are now ready to prove Lemma 7.
Proof of Lemma 7
We discuss the cases \(\beta \ge 0\) and \(\beta <0\) separately.
Case 1: \(\beta \ge 0\). In this case, we obtain from (4.1) that
To compute the derivative with respect to \(t\), we discuss two subcases.
Case 1.1: \(\beta \ge 0, \tilde{x}(t) \ge 0\).
In this case we have \(e' \tilde{z}(t)=0\). We use the differential equation (6.13) to rewrite the expression in (6.15). For the first term, this yields
To bound this further, we use our assumption that \(\beta \) and \(\tilde{x}(t)\) are nonnegative, which implies that
where \(\alpha \wedge \mu =\min \{ \alpha , \mu \}\) and \(\alpha \vee \mu =\max \{ \alpha , \mu \}\).
We bound (6.16) from above as follows. Since \(\alpha \wedge \mu >0\), we deduce that there exists some (large) \(\kappa \) so that
where \(c_{9}\) is the constant from Lemma 9. We have thus obtained
Combining this with Lemma 9 and (6.15), this yields
which establishes part (a) of the statement in Case 1.1. It also gives the upper bound claimed in part (b), since the positive definiteness of \(Q\) yields a constant \(c'>0\) such that
where the last inequality holds outside of some compact set. To prove the lower bound claimed in part (b), we similarly note that
and one can bound the second term in (6.15) with Lemma 9. We conclude that
By positive definiteness of \(Q\) there exists some constant \(C'>0\) such that, outside of some compact set,
and we have thus shown all the claims in case \(\beta \ge 0\) and \(\tilde{x}(t)\ge 0\).
Case 1.2: \(\beta \ge 0, \tilde{x}(t) < 0\).
In this case one has \(e' \tilde{z}(t)=\tilde{x}(t) \). We use the differential equation (6.14) to rewrite (6.15). This leads to
where we use \(\gamma =\mu R^{-1} p\) and \( \tilde{x}(t)+ \beta =e' ( \tilde{z}(t)+ \beta \gamma )\). It follows from Lemma 1 that we can choose \(\kappa \) large so that \(e e'R +R'ee'+ \kappa (Q R + R' Q)\) is positive definite. This immediately yields part (a) of the statement in case 1.2.
By definition of \(g\), again using \(e'\tilde{z}(t)=\tilde{x}(t)\), we also have
Since \(ee'+\kappa Q\) is also positive definite, the proof for the case \(\beta \ge 0\) and \(\tilde{x}(t) < 0\) is also complete.
Case 2: \(\beta < 0\).
In this case, we obtain from (4.1) that
As in Case 1, we discuss two subcases.
Case 2.1: \(\beta < 0, \tilde{x}(t) \ge 0\). We use the differential equation (6.13) to rewrite the expression in (6.17). For the first term, this yields
The rest of the argument is almost identical to the one for Case 1.1. Increasing \(\kappa \) if necessary, one can show that
This leads to
The first inequality immediately establishes part (a) for \(\beta <0,\,\tilde{x}(t)\ge 0\). For part (b), one uses these two inequalities with the same arguments as in Case 1.1.
Case 2.2: \(\beta <0, \tilde{x}(t) < 0\). In this case we have \(e' \tilde{z}(t)= \tilde{x}(t)\). We use the differential equation (6.14) to rewrite the expression in (6.17). This leads to
where we use \(\tilde{x}(t)= e' \tilde{z}(t)\). We next use an argument similar to the one used in Case 1.1. Since \(\beta <0,\,\tilde{z}(t)'e<0\), we have
As a result, we obtain that
In view of (6.17), we, therefore, find that
Increasing \(\kappa \) if necessary so that \( -2\alpha (\alpha {\vee }\mu ) |e'R| I +\kappa [Q R +R'Q]\) is positive definite, we readily obtain part (a) of the lemma. For part (b), we need to make a comparison with \(g\). By definition of \(g\) and (6.18), we obtain from \(e'\tilde{z}(t) =\tilde{x}(t)\) that
which also yields part (b) of the claim in Case 2.2.
Combining the four cases, we have completed the proof of the lemma. \(\square \)
1.3 Appendix 3: Negative drift condition for the diffusion-scaled processes
It is the goal of this appendix to establish the negative drift condition for the diffusion-scaled processes, i.e., to prove Lemma 4. For this, we use the negative drift condition for the fluid model from Lemma 3.
Following Sects. 4 and 5 in [7], we can use the map \(\Psi \) in Lemma 2 to represent the diffusion-scaled state processes given in (2.5) and (2.6):
where the exact form of the processes \(\tilde{U}^n\) and \(\tilde{V}^n\) is not important at this point; they are specified in the proof of Lemma 10 below. In view of this identity, we establish the negative drift condition for the diffusion-scaled processes by comparing the diffusion-scaled inputs \(\tilde{U}^n\) and \(\tilde{V}^n\) of the map \(\Psi \) with their fluid analogs \(\tilde{u}^n\) and \(\tilde{v}^n\) and then leveraging the negative drift condition of the fluid model.
Our negative drift result allows the diffusion-scaled process \((\tilde{A}^n,\tilde{x}^n,\tilde{z}^n)\) to start from an arbitrary initial condition \((\tilde{A}^n(0),\tilde{x}^n(0),\tilde{z}^n(0)) =(a,x,z)\in \tilde{\mathcal{S}}^n\). We initialize the fluid model with the same point \((x,z)\), i.e., \((\tilde{x}(0),\tilde{z}(0)) = (x,z)\). As a result, the fluid model depends on \(n\) through the state space \(\tilde{\mathcal{S}}^n\) of its initial point. Throughout this appendix, we stress this dependence by writing \((\tilde{x}^n,\tilde{z}^n)\) for the fluid model instead of \((\tilde{x},\tilde{z})\). Similarly, we write \(\tilde{u}^n\) and \(\tilde{v}^n\) instead of \(\tilde{u}\) and \(\tilde{v}\), as defined through (4.4).
The following auxiliary lemma insures that the inputs to \(\Psi \) are close to their fluid analogs. Its proof is deferred to the end of this appendix.
Lemma 10
Fix \(t_0 \ge 0\). There exists a constant \(C=C(t_0)>0\) such that for each \(n\) large enough and each initial state \((a,x,z)=(\tilde{a}^n(0), \tilde{x}^n(0), \tilde{z}^n(0))\in \tilde{\mathcal{S}}^n\), we have
With Lemma 10 at our disposal, we are ready to prove the negative drift condition for diffusion-scaled processes.
Proof of Lemma 4
Throughout this proof, when using constants from auxiliary lemmas, their subscript again denotes the lemma they originated from.
Let \(n\) be large enough as in Lemma 10, and let \((a,x,z)=(\tilde{a}^n(0), \tilde{x}^n(0), \tilde{z}^n(0))\in \tilde{\mathcal{S}}^n\). We first note that
where the first inequality follows from Lemma 5, the equality follows from the fact that \((\tilde{x}^n, \tilde{z}^n)= \Psi (\tilde{U}^n, \tilde{V}^n)\) and \((\tilde{x}^n, \tilde{z}^n)= \Psi (\tilde{u}^n, \tilde{v}^n)\), and the last inequality follows from the Lipschitz continuity of the map \(\Psi \) as in part (c) of Lemma 2.
It follows from (6.22), Lemma 3, and Lemma 10 that
Pick some \(C'>0\) such that, for any \(b\in \mathbb {R}\) with \( b\ge C'\),
The constants \(C\) and \(\epsilon \) in the statement of the lemma are chosen as follows:
and we now verify the statement of the lemma with these definitions. If \((x,z)\) satisfies \(g(x,z)<C'\), then the right-hand side of (6.23) is bounded from above by
If \((x,z)\) satisfies \(g(x,z)\ge C'\), then it is bounded from above by
We have thus obtained (5.1) in both cases. \(\square \)
1.3.1 Proof of auxiliary lemma
We now prove Lemma 10.
Proof of Lemma 10
In this proof, the constant \(C\) is a generic constant independent of \(n\), but may vary line from line. Fix \(t_0>0\). We start by specifying the processes \(\tilde{U}^n\) and \(\tilde{V}^n\) for which (6.19) holds. Following (5.10) and (5.11) in [7], we have
The processes \(\tilde{E}^n, \tilde{M}^{n}, \tilde{G}^{n}, \tilde{\Phi }^{0,n},\,\bar{X}^n\), and \(\bar{B}^{n}\) are defined as follows, see Sect. 5.2 of [7]. First, \(\tilde{E}^n\) is given in (2.11). For each \(k = 1, \ldots , K\), let \(S_k\) be a Poisson process with rate \(\nu _k\), and let \(G\) be a Poisson process with rate \(\alpha \). For each \(n\ge 1\) define the diffusion-scaled processes:
Moreover, for each \(N \ge 1\) and \(k = 0, \ldots , K\), define the routing processes
where \(\{\phi ^k (j): j=1, 2, \ldots \}\) are i.i.d. Bernoulli random vectors with mean \(p^k\). Here, \(p^0=p,\) and \(p^k\) is the \(k\)th column of matrix \(P'\). For each \(n\ge 1\), set
where, for an \(x\in \mathbb {R},\,\lfloor x \rfloor \) is the largest integer that is less than or equal to \(x\). Let \(T_k^n (t)\) be the cumulative amount of service effort received by customers in phase \(k\) service in \((0, t ],\,B^n (t)\) be the cumulative number of customers who have entered into service by time \(t\). Then, \(\tilde{M}^n(t)\) is defined via
where \(\bar{S}^{n}(t)=S(nt)/n\) and \(\bar{T}^{n}(t)=T_n(t)/n\) for \(t\ge 0\). We also let \(\bar{B}^{n}(t)=B^n(t)/n\) for \(t\ge 0\). Finally, we have
where \(X^n(t)\) is given in (2.4). As in [7], we have that
Having explained the meaning of all processes involved, we now proceed and prove the statement of Lemma 10. By (6.24), (6.25), and (4.4) we have
We first establish (6.20). The proof is similar to that of Lemma 3.5 in [3], and we only highlight the main differences. We start with inequality (6.29). We bound the three terms in the right side of (6.29) separately. Let \(\{{E}^*(t): t \ge 0\}\) be a renewal process associated with i.i.d. sequence \(\{u(i):i\ge 1\}\) that was given in Assumption 1, where \(u(1)\) is the first renewal time. It follows from Assumption 1 that for each \(t \ge 0,\)
Since \(E^*(\cdot )\) is independent of \((A^n(0), X^n(0), Z^n(0))\) for any \(n,\) using the definition of \({\tilde{E}^{n}}\) in (2.11) and Eq. (6.31), we deduce that there exists a constant \(C\) independent of \(n\) and of initial states \((a,x,z)\) such that
where the last inequality follows from Lemma 3.5 in [3] and the fact that the sequence \(\{{\lambda ^n}/{n}: n \ge 1\}\) is bounded. Hence, we have
Moreover, we know from (6.28) and Lemma 3.5 in [3] that
where we use the fact that for each \(k, \bar{T}_k^n (t) \le t\) for all \(t \ge 0\). This immediately implies
Finally, we show there is a constant \(C(t_0)\) which depends on \(t_0\) but is independent of \(n\) and any initial state \((a,x,z)\tilde{\mathcal{S}}^n\) such that
To see this, we know from (2.4) that for all \(0 \le s \le t\)
where \(x = \tilde{x}^n(0) = \sqrt{n} \bar{X}^n(0)\) and \(\bar{E}^{n}(t) = \frac{1}{n} {E}^{n}(t)\) for \(t \ge 0\). In conjunction with (6.31) we obtain
We have on each sample path
Since \(G(\cdot )\) is a Poisson process, \(\tilde{G}^n\) defined in (6.26) is a martingale. In addition, the random variable \(E^*( \lambda ^n t_0)\) is independent of \(\tilde{G}^n\) and the age \(A^n(0)\) associated with the arrival process \(E^n\). Furthermore, it follows again from Lemma 3.5 in [3] that there is some constant \(C\) independent of \(n,\) such that for \(t \ge 0,\)
Therefore, we deduce from (6.35) that
where in the second last inequality we use Doob’s maximal inequality for martingales (see, e.g., Theorem II.1.7 in [24]), and in the last inequality we use (6.36). Since there is a constant \(C\) independent of \(n\) such that the sequence \(\{{\lambda ^n}/{n}: n \ge 1\}\) is bounded by \(C\) and
we obtain (6.34). On combining (6.32), (6.33), and (6.34), we deduce from (6.29) that (6.20) holds.
To prove (6.21), we start from inequality (6.30). Since \(B^n (t)\) is the cumulative number of customers who have entered into service by time \(t\), we obtain that
In addition, it is clear that \(\tilde{\Phi }^{0,n}\) defined in (6.27) is a martingale; thus, we can proceed in a similar fashion as the proof for (6.34) and show that there is a constant \(C(t_0)\) depending on \(t_0,\) but is independent of \(n\) and any initial state \((a,x,z)\) such that
On combining (6.33) we obtain (6.21) from (6.30). \(\square \)
Rights and permissions
About this article
Cite this article
Dai, J.G., Dieker, A.B. & Gao, X. Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Syst 78, 1–29 (2014). https://doi.org/10.1007/s11134-014-9394-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-014-9394-x
Keywords
- Diffusion approximations
- Stationary distribution
- Geometric Lyapunov function
- Weak convergence
- Multi-server queues
- Customer abandonment
- Halfin–Whitt regime
- Phase-type distribution
- Piecewise OU processes