On the \(M_t/M_t/K_t+M_t\) queue in heavy traffic

The focus of this paper is on the asymptotics of large-time numbers of customers in time-periodic Markovian many-server queues with customer abandonment in heavy traffic. Limit theorems are obtained for the periodic number-of-customers processes under the fluid and diffusion scalings. Other results concern limits for general time-dependent queues and for time-homogeneous queues in steady state.

I am thankful to the referees for the careful reading of the manuscript and insightful comments.

Authors and Affiliations

1. University of Colorado Denver, Denver, CO, USA

   Anatolii A. Puhalskii

2. Institute for Problems in Information Transmission, Moscow, Russia

   Anatolii A. Puhalskii

Corresponding author

Correspondence to Anatolii A. Puhalskii.

Appendix

Lemma 5

Let \((F(t),\,t\in \mathbb R _+)\) be a function of locally bounded variation and \((f(t),\,t\in \mathbb R _+)\) be a locally bounded Lebesgue measurable function. If a locally integrable function \((y(t),\,t\in \mathbb R _+)\) is such that \(y(t)\prec F(t)-\int _0^t f(s)y(s)\,ds\), then

Proof

Let \(g(t)=F(t)-\int _0^t f(s)y(s)\,ds-y(t)\). The function \((g(t))\) is nondecreasing, \(g(0)\ge 0\), and

Hence,

\(\square \)

The next lemma provides the bounds that have been used for the analysis of large-time behaviour. Let \(T>0\) and \( \sigma ^n_s=|\alpha ^n_s-\gamma ^n_s(q_s-\kappa _s)^+-\beta ^n_s(q_s\wedge \kappa _s)| +|(\theta ^n_s-\mu ^n_s)\delta ^n_s|.\) Let me recall that \(q_t\) is defined by (2.6).

Lemma 6

1. 1.
   1. (a)

      If the functions \((\lambda _t,\,t\in \mathbb R _+), (\mu _t,\,t\in \mathbb R _+)\), and \((\theta _t,\,t\in \mathbb R _+)\) are \(T\)-periodic and \(\int _0^T(\mu _s\wedge \theta _s)\,ds>0\) , then, for all \(t\in \mathbb R _+\),

      $$\begin{aligned} q_t\le e^{-\lfloor t/T\rfloor \int _0^T (\mu _s\wedge \theta _s)\,ds}\, q_0 +\frac{ e^{\int _0^{T} (\mu _s\wedge \theta _s)\,ds}}{1-e^{-\int _0^{T} (\mu _s\wedge \theta _s)\,ds}}\int \limits _{0}^{T}\lambda _s\,ds. \end{aligned}$$
   2. (b)

      If the functions \((\lambda ^n_t,\,t\in \mathbb R _+), (\mu ^n_t,\,t\in \mathbb R _+)\), and \((\theta ^n_t,\,t\in \mathbb R _+)\) are \(T\)-periodic and \(\int \limits _0^T(\mu ^n_s\wedge \theta ^n_s)\,ds>0\) , then, for all \(t\in \mathbb R _+\) and \(V>0\),

      $$\begin{aligned} \mathbf E Q^n_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,&\le e^{-\lfloor t/T\rfloor \int _0^T (\mu ^n_s\wedge \theta ^n_s)\,ds} \, \mathbf E Q^n_0\,\mathbf 1 _{\{Q^n_0\le V\}}\,\\&+ \frac{ e^{\int _0^{T} (\mu ^n_s\wedge \theta ^n_s)\,ds}}{1-e^{-\int _0^{T} (\mu ^n_s\wedge \theta ^n_s)\,ds}}\int \limits _{0}^{T}\lambda ^n_s\,ds. \end{aligned}$$

      .

   3. (c)

      If the functions \((\lambda ^n_t,\,t\in \mathbb R _+), (\mu ^n_t,\,t\in \mathbb R _+), (\theta ^n_t,\,t\in \mathbb R _+), (\lambda _t,\,t\in \mathbb R _+), (\mu _t,\,t\in \mathbb R _+)\), and \((\theta _t,\,t\in \mathbb R _+)\) are \(T\)-periodic, \(\int _0^T(\mu _s\wedge \theta _s)\,ds>0\) , and, for some \(\epsilon >0, \int _0^{T}\left(2(\mu ^n_s\wedge \theta ^n_s)- \epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n})\right)\,ds>0\), then, for all \(t\in \mathbb R _+\) and \(V>0\),

      $$\begin{aligned}&\mathbf E (X^n_t)^2\,\mathbf 1 _{\{|X^n_0|\le V\}}\,\\&\quad \le e^{-\lfloor t/T\rfloor \int _0^T \left(2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n}) \right)\,ds +\int _0^T |2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n})|\,ds}\\&\qquad \times \mathbf E (X^n_0)^2\,\mathbf 1 _{\{|X^n_0|\le V\}}\, + \frac{ e^{2\int _0^{T}|2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n})|\,ds}}{1-e^{-\int _0^{T}\left(2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n})\right)\,ds}}\\&\qquad \times \int \limits _0^{T}\left(\frac{1}{\epsilon }\,\sigma ^n_s +\frac{\lambda ^n_s}{n} \right. \left. + (\mu ^n_s\vee \theta ^n_s)\sup _{u\in \mathbb R _+}q_u+ \frac{1}{2\sqrt{n}}(\mu ^n_s\vee \theta ^n_s)\right)\,ds. \end{aligned}$$
2. 2.
   1. (a)

      If \(\sup _{t\in \mathbb R _+}\lambda _t<\infty \) and \(\inf _{t\in \mathbb R _+}( \mu _t\wedge \theta _t)>0\), then, for all \(t\in \mathbb R _+\),

      $$\begin{aligned} q_t\le e^{-\int _0^t (\mu _s\wedge \theta _s)\,ds} q_0+ \frac{\sup _{s\in \mathbb R _+}\lambda _s}{\inf _{s\in \mathbb R _+} (\theta _s\wedge \mu _s)}. \end{aligned}$$
   2. (b)

      If \(\sup _{t\in \mathbb R _+}\lambda ^n_t<\infty \) and \(\inf _{t\in \mathbb R _+}( \mu ^n_t\wedge \theta ^n_t)>0\), then, for all \(t\in \mathbb R _+\) and \(V>0\) ,

      $$\begin{aligned} \mathbf E Q^n_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,\le e^{-\int _0^t (\mu ^n_s\wedge \theta ^n_s)\,ds}\, \mathbf E Q^n_0\,\mathbf 1 _{\{Q^n_0\le V\}}\, +\frac{\sup _{s\in \mathbb R _+}\lambda ^n_s}{\inf _{s\in \mathbb R _+} (\theta ^n_s\wedge \mu ^n_s)}. \end{aligned}$$
   3. (c)

      If \(\sup _{t\in \mathbb R _+}\lambda _t<\infty , \inf _{t\in \mathbb R _+}( \mu _t\wedge \theta _t)>0, \sup _{t\in \mathbb R _+}\lambda ^n_t<\infty , \sup _{t\in \mathbb R _+}\theta ^n_t<\infty , \sup _{t\in \mathbb R _+}\mu ^n_t<\infty , \sup _{t\in \mathbb R _+}\sigma ^n_t<\infty \), and \(\inf _{t\in \mathbb R _+}\left(2(\mu ^n_t\wedge \theta ^n_t)-\epsilon \,\sigma ^n_t\right.\left.- (\mu ^n_t\vee \theta ^n_t)/(2\sqrt{n})\right)>0\) for some \(\epsilon >0\) , then, for all \(t\in \mathbb R _+\) and \(V>0\),

      $$\begin{aligned}&\mathbf E (X^n_t)^2\,\mathbf 1 _{\{|X^n_0|\le V\}}\,\\&\quad \le e^{-\int _0^t \left(2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \,\sigma ^n_s- (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n}) \right)\,ds} \,\mathbf E (X^n_0)^2\,\mathbf 1 _{\{|X^n_0|\le V\}}\, \\&\qquad + \dfrac{\sup _{s\in \mathbb R _+}\left(\sigma ^n_s/\epsilon +\lambda ^n_s/n+ (\mu ^n_s\vee \theta ^n_s)q_s+ (\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n})\right)}{\inf _{s\in \mathbb R _+}\left(2(\mu ^n_s\wedge \theta ^n_s)-\epsilon \, \sigma ^n_s -(\mu ^n_s\vee \theta ^n_s)/(2\sqrt{n}) \right)}. \end{aligned}$$

Proof

Let me start with part 1(b). Since \(Q^n_t\le Q^n_0+A^n_t\) by (2.1), I have that \(\mathbf E Q^n_t \,\mathbf 1 _{\{Q^n_0\le V\}}\,\le V+\int _0^t\lambda ^n_s\,ds\). By Lemma 1, the processes \((M^{n,A}_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,,\,t\in \mathbb R _+), (M^{n,R}_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,,\,t\in \mathbb R _+)\), and \((M^{n,B}_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,,\,t\in \mathbb R _+)\) are \(\mathbf F ^n\)-locally square integrable martingales with respective predictable quadratic variation processes \((\,\mathbf 1 _{\{Q^n_0\le V\}}\,\int _0^t\lambda ^n_s\,ds\,,t\in \mathbb R _+), (\,\mathbf 1 _{\{Q^n_0\le V\}}\,\int _0^t\theta ^n_s\, (Q^n_s-K^n_s)^+\,ds,\,t\in \mathbb R _+)\), and \((\,\mathbf 1 _{\{Q^n_0\le V\}}\,\int _0^t\mu ^n_s\, (Q^n_s\wedge K^n_s)\,ds,\,t\in \mathbb R _+)\). Since the latter processes are of finite expectation, I obtain that \(\mathbf E (M^{n,A}_t)^2\,\mathbf 1 _{\{Q^n_0\le V\}}\,<\infty , \mathbf E (M^{n,R}_t)^2\,\mathbf 1 _{\{Q^n_0\le V\}}\,<\infty \), and \(\mathbf E (M^{n,B}_t)^2\,\mathbf 1 _{\{Q^n_0\le V\}}\,<\infty \). In particular, \((M^{n,A}_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,,\,t\in \mathbb R _+), (M^{n,R}_t\,\mathbf 1 _{\{Q^n_0\!\le \! V\}}\,,t\!\in \!\mathbb R _+)\), and \((M^{n,B}_t\,\mathbf 1 _{\{Q^n_0\le V\}}\,,t\in \mathbb R _+)\) are martingales. By (2.3),

By Lemma 5,

If \(vT\le t<(v+1)T\), where \(v\in \mathbb Z _+\), then by \(T\)-periodicity,

In addition, \(e^{-\int _0^t (\mu ^n_s\wedge \theta ^n_s)\,ds}\le e^{-\lfloor t/T\rfloor \int _0^T (\mu ^n_s\wedge \theta ^n_s)\,ds}\). Part 1(b) has been proved.

Part 1(a) follows by a similar argument if one observes that by (2.6),

so that, by Lemma 5,

In order to prove part 1(c), let me note that by (2.13),

On noting that

I obtain that, for \(\epsilon >0\),

Hence, for \(V>0\),

where \(M^{n,i,V}_s=M^{n,i}_s\,\mathbf 1 _{\{|X^n_0|\le V\}}\,\), for \(i=A,R,B\).

By Lemma 1, the processes \(M^{n,i,V}=(M^{n,i,V}_t,\,t\in \mathbb R _+)\) are \(\mathbf F ^n\)-locally square integrable martingales with predictable quadratic variation processes \(\langle M^{n,i,V}\rangle =\langle M^{n,i}\rangle \,\mathbf 1 _{\{|X^n_0|\le V\}}\,\). Since \(Q^n_t\le Q^ n_0+A^n_t\) by (2.1) and \(\mathbf E (A^n_t)^2=\int _0^t\lambda ^n_s\,ds+\left(\int _0^t\lambda ^n_s\,ds\right)^2<\infty \), I have that \(\mathbf E (Q^n_t)^2\,\mathbf 1 _{\{|X^n_0|\le V\}}\,<\infty \). Hence, by (2.4a), (2.4b), (2.4c), \(\mathbf E \langle M^{n,i,V}\rangle _t<\infty \), which implies that \(\mathbf E \left(\sup _{s\le t}\left( M^{n,i,V}_s\right) ^2\right)<\infty \), that the \(M^{n,i,V}\) are \(\mathbf F ^n\)-martingales, and that \(\mathbf E ( M^{n,i,V}_t)^2=\mathbf E \langle M^{n,i,V}\rangle _t\). Consequently, the processes \(\left(\int _0^{t} X^n_{s-}\, \,dM^{n,i,V}_s,\,t\in \mathbb R _+\right)\) are \(\mathbf F ^n\)-martingales. Since the \(M^{n,i,V}\) are purely discontinuous locally square integrable martingales by being of locally bounded variation, \(\mathbf E \sum _{0<s\le t}(\Delta M^{n,i,V}_s)^2= \mathbf E \langle M^{n,i,V}\rangle _{t}\).

On taking expectations in (5.4),

By (2.4a), (2.4b), (2.4c), and (2.12),

Thus, for \(t\in \mathbb R _+\),

By Lemma 5,

In analogy with the earlier argument, if \(vT\le t<(v+1)T\), where \(v\in \mathbb Z _+\), recalling that \(\sup _{u\in \mathbb R _+}q_u<\infty \) by part 1(a),

where the last inequality uses the fact that \(\int _0^{T}\left(2(\mu ^n_u\wedge \theta ^n_u)-\epsilon \,\sigma ^n_u- (\mu ^n_u\vee \theta ^n_u)/\right.\left.(2\sqrt{n})\right)\,du>0\). The latter expression furnishes the required bound. Part 1 has been proved.

The assertions of part 2 also follow from the respective inequalities (5.2), (5.3), and (5.5). For instance part 2(b) is obtained by applying the bound

\(\square \)

Reprints and permissions