MAP/M/c and M/PH/c queues with constant impatience times

This paper considers stationary MAP/M/c and M/PH/c queues with constant impatience times. In those queues, waiting customers leave the system without receiving their services if their elapsed waiting times exceed a predefined deterministic threshold. For the MAP/M/c queue with constant impatience times, Choi et al. (Math Oper Res 29:309–325, 2004) derive the virtual waiting time distribution, from which the loss probability and the actual waiting time distribution are obtained. We first refine their result for the virtual waiting time and then derive the stationary queue length distribution. We also discuss the computational procedure for performance measures of interest. Next we consider the stationary M/PH/c queue with constant impatience times and derive the loss probability, the waiting time distribution, and the queue length distribution. Some numerical results are also provided.

We are grateful to the referee(s) and the associate editor for their valuable comments and suggestions which have improved this paper. This research was supported in part by Grant-in-Aid for Scientific Research (C) of Japan Society for the Promotion of Science under Grants Nos. 25330027 and 26350416.

Authors and Affiliations

1. Division of Electronics and Informatics, Gunma University, Kiryu, 376-8515, Japan

   Ken’ichi Kawanishi

2. Department of Information and Communications Technology, Graduate School of Engineering, Osaka University, Suita, 565-0871, Japan

   Tetsuya Takine

Corresponding author

Correspondence to Ken’ichi Kawanishi.

Appendix 1: Proof of Lemma 1

Let \(\theta _C\) denote the maximum absolute value of diagonal elements of \({\varvec{C}}_{\mathrm {A}}\).

Since \({\varvec{C}}_{\mathrm {A}}+{\varvec{D}}_{\mathrm {A}}\) is irreducible, \({\varvec{C}}_{\mathrm {A}}+ (\mu /(\theta _c+\mu )) {\varvec{D}}_{\mathrm {A}}\) is also irreducible. On the other hand, it follows from (10) that

We thus have \({\varvec{C}}_{\mathrm {A}}+ \mu {\varvec{Y}}_{\mathrm {A}}\ge {\varvec{C}}_{\mathrm {A}}+ (\mu /(\theta _c+\mu )) {\varvec{D}}_{\mathrm {A}}\). Therefore, \({\varvec{C}}_{\mathrm {A}}+ \mu {\varvec{Y}}_{\mathrm {A}}\) is irreducible, from which the irreducibility of \(\varvec{U}_{1,1}\) follows. The irreducibility of \(\varvec{U}_{2,2}\) immediately follows from Lemma 2 in [8].

Next we prove \(\varvec{U}_{i,j} \varvec{e} = \varvec{0}\) (\(i,j=1,2\)) when \(\rho =1\). We first show \(\varvec{U}_{1,2} \varvec{e} = \varvec{0}\). Post-multiplying both sides of (10) by \(\varvec{e}\) and using (1), we obtain

On the other hand, because \({\varvec{\pi }}_{\mathrm {A}}{\varvec{Y}}_{\mathrm {A}}= {\varvec{\pi }}_{\mathrm {A}}\) for \(\rho \ge 1\) (see Lemma 2 in [8]), we have

The difference of the above two equations becomes \([\varvec{e}{\varvec{\pi }}_{\mathrm {A}}- ({\varvec{Y}}_{\mathrm {A}}-\varvec{I})] ({\varvec{D}}_{\mathrm {A}}-\mu {\varvec{Y}}_{\mathrm {A}}) \varvec{e} = \varvec{0}\). Because \(\varvec{e}{\varvec{\pi }}_{\mathrm {A}}- ({\varvec{Y}}_{\mathrm {A}}-\varvec{I})\) is nonsingular, we obtain

so that \(\varvec{U}_{1,2} \varvec{e} =\varvec{0}\).

Next we consider \(\varvec{U}_{1,1} \varvec{e} = \varvec{0}\). Owing to (1) and (78), \(({\varvec{C}}_{\mathrm {A}}+\mu {\varvec{Y}}_{\mathrm {A}})\varvec{e} = (\mu {\varvec{Y}}_{\mathrm {A}}- {\varvec{D}}_{\mathrm {A}})\varvec{e} = \varvec{0}\). Therefore, \(\varvec{U}_{1,1}\varvec{e} = \varvec{0}\) is equivalent to

We thus show \((-\varvec{B}_i)^{-1}{\varvec{D}}_{\mathrm {A}}\varvec{e} = \varvec{e}\) (\(i=0,1,\ldots ,c-1\)) below. For \(i=0\), \(\varvec{B}_0={\varvec{C}}_{\mathrm {A}}\), so that from (1), we have \((-\varvec{B}_0)^{-1}{\varvec{D}}_{\mathrm {A}}\varvec{e} = \varvec{e}\). Suppose \((-\varvec{B}_i)^{-1}{\varvec{D}}_{\mathrm {A}}\varvec{e} = \varvec{e}\) holds for some \(i=n-1\) (\(n=1,\ldots ,c-1\)). Post-multiplying both sides of (6) by \(\varvec{e}\) yields

We thus have \((-\varvec{B}_i)^{-1}{\varvec{D}}_{\mathrm {A}}\varvec{e} = \varvec{e}\) for \(i=n\).

The equality \(\varvec{U}_{2,1} \varvec{e} = \varvec{0}\) immediately follows from (79) and \({\varvec{Z}}_{\mathrm {A}}\varvec{e}=\varvec{e}\) (see Lemma 2 in [8]). Finally, \(\varvec{U}_{2,2} \varvec{e} = \varvec{0}\) follows from (1) and \({\varvec{Z}}_{\mathrm {A}}\varvec{e}=\varvec{e}\). \(\Box \)

Appendix 2: Proof of Lemma 2

It follows from (1), (2), and (79) that

On the other hand, it follows from (2) and (3) that

We thus have \(\varvec{u}_{3,1} \varvec{e} = - \varvec{u}_{3,2} \varvec{e}\). Furthermore, using \(\mu =\lambda = {\varvec{\pi }}_{\mathrm {A}}{\varvec{D}}_{\mathrm {A}}\varvec{e}\) and \({\varvec{\kappa }}_{\mathrm {A}}^* \varvec{e} = 0\), we have

which completes the proof of the equalities.

Next we prove \(1 - {\varvec{\kappa }}_{\mathrm {A}}^* {\varvec{D}}_{\mathrm {A}}\varvec{e} \ge 1/2\). From (16), we have

where we use \(\mu =\lambda \). Let A(0, t] denote the number of arrivals in an interval (0, t] given that the distribution of the initial state J(0) of the underlying Markov chain is given by \({\varvec{\pi }}_{\mathrm {A}}\). The variance of A(0, t] is known to be [26]

where

Substituting (80) into (81), we have

By definition, \(\mathrm {Var}(A(0,t]) \ge 0\) and \(\lim _{t \rightarrow \infty } \exp [({\varvec{C}}_{\mathrm {A}}+{\varvec{D}}_{\mathrm {A}})t] = \varvec{e}{\varvec{\pi }}_{\mathrm {A}}\). We thus have

from which \(1 - {\varvec{\kappa }}_{\mathrm {A}}^* {\varvec{D}}_{\mathrm {A}}\varvec{e} \ge 1/2\) follows. \(\square \)

Appendix 3: Proof of Lemma 3

Let \(\varvec{a}_{\mathrm {cond}}(x)\) (\(x > 0\)) denote a \(1 \times m\) vector whose jth (\(j \in \mathscr {M}\)) element represents

By definition, \(\varvec{a}(x) = Pr(L(0) \ge c) \cdot \varvec{a}_{\mathrm {cond}}(x)\), where

Note that every customer who finds \(L(t-)=c-1\) or \(0 < V(t-) < \tau \) at his/her arrival epoch t will become customer #c when their service starts. Furthermore, once their service starts, they remain customer #c for an exponentially distributed interval with mean \(1/\mu \). Because of the memoryless property of the exponential distribution, the elapsed service time of customer #c follows an exponential distribution with mean \(1/\mu \) and it is independent of the waiting time. Based on these observations and conditional PASTA, we obtain

where \(\lambda _c\) denotes the arrival rate of customers who will become customer #c.

Applying Little’s law to the mean number of customer #c, we have \(\lambda _c (\mu ^{-1}) = 1 \times Pr(L(0) \ge c) + 0 \times Pr(L(0) < c)\), from which we obtain

It then follows from (83) and (85) that

Note here that for \(x > \tau \), (86) is rewritten to be

which completes the proof. \(\square \)

Appendix 4: Generality of (29)

In this Appendix, we prove that (29) holds for the stationary FCFS MAP/G/c queue, where the same notation as for the MAP/M/c+D queue are used for the MAP/G/c queue. In the proof, we only assume that \(\{V(t),J(t)\}\) is jointly stationary under the probability measure P, and the waiting time of a customer arriving at time t is given by \(V(t-)\) (i.e., FCFS). Therefore, (29) is fairly general. We define \(N_{i,j,0}\) (\(i,j \in \mathscr {M}\), \(i \ne j\)) and \(N_{i,j,1}\) (\(i,j \in \mathscr {M}\)) as the point process associated with state transitions of J(t) from state i to state j without arrivals and with arrivals, respectively, and let \(P_{i,j,0}\) (\(i,j \in \mathscr {M}\), \(i \ne j\)) and \(P_{i,j,1}\) (\(i,j \in \mathscr {M}\)) denote the Palm measures obtained by conditioning on an atom of \(N_{i,j,0}\) and an atom of \(N_{i,j,1}\), respectively, at time zero. We define \(\mathbb {I}(\chi )\) as an indicator function of event \(\chi \). Let \({E}\), \({E}_{i,j,0}\) (\(i,j \in \mathscr {M}\), \(i \ne j\)) and \({E}_{i,j,1}\) (\(i,j \in \mathscr {M}\)) denote the expectation with respect to P, \(P_{i,j,0}\) and \(P_{i,j,1}\), respectively.

We define \(v_j(s)\), \(v_j^+(s)\), \(a_j(s)\), and \(a_j^+(s)\) as

where \(T_c(t) = t\) if \(A(t)=0\). By definition,

We also define \(w_{i,j}^q(s)\) and \(w_{i,j}(s)\) as

Owing to conditional PASTA, we have

Suppose a customer arrives at time t with a state transition from state \(J(t-)=i\) to \(J(t)=j\). If \(V(t-) < V(t)\), this customer will be a customer \(\#c\) during an interval from time \(t+V(t-)\) to time \(t+V(t)\). Note that \(V(t-)=V(t)\) can happen if \(L(t-) < c-1\) or the service time of the arriving customer is equal to zero. We thus have

where we use the invariance relation \(H=\lambda G\) [14] in the first equality.

We define \(f_j(t)\) (\(j \in \mathscr {M}\), \(-\infty < t < \infty \)) as \(f_j(t)=\exp (-s V(t))\mathbb {I}(J(t)=j)\). Applying Miyazawa’s rate conservation law [24, Lemma 3.1] to \({E}[f_j(t)]\), we have

It then follows that

or equivalently,

which implies (29).

Appendix 5: Proof of Lemma 4

We first consider the case \(x \ge \tau \). By definition, we have

from which (45) follows. Note that (45) implies

On the other hand, for \(0 < x < \tau \),

and therefore, we have

(44) follows from (87) and the above equation. \(\square \)

Appendix 6: Proof of Lemma 5

We can show the irreducibility of \({\varvec{C}}_{\mathrm {S}}+ \lambda {\varvec{Y}}_{\mathrm {S}}\) in exactly the same way as \({\varvec{C}}_{\mathrm {A}}+ \lambda {\varvec{Y}}_{\mathrm {A}}\) (cf. Appendix 1), from which the irreducibility of \(\varvec{V}_{1,2}\) follows. Next we consider \(\varvec{V}_{2,1} = \varvec{S}_2 \varvec{N} -\varvec{I}\), where \(\varvec{N}\) is defined as \(\varvec{N}=\varvec{Q}_{c,2} (-\varvec{H}_{c-1})^{-1} \varvec{Q}_{c-1,0}\). We can show the irreducibility of \(\lambda {\varvec{Z}}_{\mathrm {S}}+ {\varvec{C}}_{\mathrm {S}}\) in exactly the same way as in Lemma 2 in [8]. Therefore, \(\exp [(\lambda {\varvec{Z}}_{\mathrm {S}}+ {\varvec{C}}_{\mathrm {S}}) x]\) (\(x > 0\)) is a positive matrix, so that \(\varvec{S}_2\) is also a positive matrix. On the other hand, \(\varvec{N}\) can be regarded as a transition rate matrix, so that it is a non-zero, nonnegative matrix (i.e., \(\varvec{N} \ge \varvec{O}\) and \(\varvec{N} \ne \varvec{O}\)).

In general, columns of a non-zero, nonnegative matrix \(\varvec{N}\) can be classified into two groups: a nonempty set \(\mathscr {C}^+\) of columns with at least one positive element and the other set \(\mathscr {C}^{\mathrm {null}}\) of columns whose elements are all equal to zero. Because \(\varvec{S}_2\) is a positive matrix, \(\varvec{S}_2 \varvec{N}\) is a nonnegative matrix, where all elements of columns in \(\mathscr {C}^+\) are positive and all elements of columns in \(\mathscr {C}^{\mathrm {null}}\) are equal to zero. Therefore, \(\varvec{S}_2 \varvec{N}\) has a single irreducible class. As a result, \(\varvec{V}_{2,1}=\varvec{S}_2\varvec{N}-\varvec{I}\) has a single irreducible class, where states corresponding to columns in \(\mathscr {C}^+\) form an irreducible class and all other states are transient.

Next we consider \(\varvec{V}_{i,j} \varvec{e} = \varvec{0}\) (\(i,j=1,2\)) for \(\rho =1\). To prove \(\varvec{V}_{1,1}\varvec{e}= \varvec{e}\), we first show

For \(i=0\), \(\varvec{H}_0=\varvec{Q}_{0,1}\), so that from (40) we have \((-\varvec{H}_0)^{-1} \varvec{Q}_{0,0} \varvec{e} = \varvec{e}\). Suppose \((-\varvec{H}_i)^{-1} \varvec{Q}_{i,0} \varvec{e} = \varvec{e}\) holds for some \(i=n-1\) (\(n=1,\ldots ,c-1\)). Post-multiplying both sides of (50) by \(\varvec{e}\) and using (40) yields

We thus have \((-\varvec{H}_n)^{-1} \varvec{Q}_{n,0} \varvec{e} = \varvec{e}\) for \(i=n\).

From (41), we also have \(\varvec{Q}_{c,2} \varvec{e} = {\varvec{D}}_{\mathrm {S}}\varvec{e}\). It then follows from the definition of \(\varvec{V}_{1,1}\) that

Furthermore, from the definition of \(\varvec{S}_1\) and (41), we have

We can show that if \(\rho =1\), \({\varvec{D}}_{\mathrm {S}}\varvec{e} = \lambda {\varvec{Y}}_{\mathrm {S}}\varvec{e}\), in exactly the same way as (78). We thus have

As a result, we have

Next we consider \(\varvec{V}_{2,1}\varvec{e}= \varvec{0}\). It follows from (41) and (88) that

Note here that \(\varvec{S}_2\) in Theorem 3 is calculated to be

Therefore, noting (41) and \({\varvec{Z}}_{\mathrm {S}}\varvec{e} = \varvec{e}\), we have

Owing to (41), \(\varvec{V}_{1,2} \varvec{e} = \varvec{0}\) and \(\varvec{V}_{2,2} \varvec{e} = \varvec{0}\) immediately follow from \(\lambda {\varvec{Y}}_{\mathrm {S}}\varvec{e} = {\varvec{D}}_{\mathrm {S}}\varvec{e} = -{\varvec{C}}_{\mathrm {S}}\varvec{e}\) and \({\varvec{Z}}_{\mathrm {S}}\varvec{e} =\varvec{e}\), respectively. \(\square \)

Appendix 7: Proof of Lemma 6

From (41), (65), (70), (71), and (88), we have

from which the first equality follows. Further, from (60), (61), \(\mu =\lambda \), and \({\varvec{\kappa }}_{\mathrm {S}}^* \varvec{e}=0\), we have

from which the second equality follows. Finally, we can show \(1 - {\varvec{\kappa }}_{\mathrm {S}}^* {\varvec{D}}_{\mathrm {S}}\varvec{e} \ge 1/2\) in exactly the same way as \(1 - {\varvec{\kappa }}_{\mathrm {A}}^* {\varvec{D}}_{\mathrm {A}}\varvec{e} \ge 1/2\) in Lemma 2, from which the inequality follows. \(\square \)

Reprints and permissions