Sojourn-time distribution of the G I/M S P/1 queueing system

Abstract

In this paper, we present an explicit closed-form expression for the sojourn-time distribution of an arrival customer in the G I/M S P/1 queueing system. We also derive the correlation coefficient of the lagged inter-departure intervals. Computational experiences with a variety of numerical results are presented.

1 Introduction

The interest to analyze sojourn-time distribution for the G I/M S P/1 queue is attributed to its importance in the area of communication, transportation, and manufacturing systems. The analysis of finite- and infinite-buffer G/M S P/1 queue has been carried out by Bocharov et al. [1] based on the method of imbedded Markov chain, wherein they derived sojourn-time distribution (in the form of sum of the service phases) of an arbitrary customer. Gupta and Banik [2] have analyzed G I/M S P/1 queue with finite as well as infinite buffer using a combination of the matrix-geometric method, the imbedded Markov chain, and the supplementary variable techniques. Recently, Chaudhry et al. [3] investigated G I/C- M S P/1 queue through the calculation of roots of the associated characteristic equation of the vector-generating function of system-length distribution at prearrival epoch. However, Gupta and Banik [2], and Chaudhry et al. [3] do not discuss the sojourn-time distribution of the G I/M S P/1 queueing system. They obtained Laplace-Stieltjes transform (LST) of the sojourn-time distribution and then carried out mean sojourn time. This paper presents an explicit closed-form expression for the sojourn-time distribution (service phase-wise) of an arrival customer in the G I/M S P/1 queueing system using the matrix-geometric method. Computational experiences with a variety of numerical results are presented. The purpose of the present paper is twofold: (i) present an alternative derivation of the sojourn-time distribution (phase-wise) given in Bocharov et al. [1]. (i i) Essentially, this paper complements the work that has been presented in [2, 3].

This paper is organized as follows. We give the description of the model in Section 2. The sojourn-time distribution of an arrival customer is analyzed in Section 3. The correlation coefficient of the lagged inter-departure intervals is obtained in Section 4. Numerical results are presented in Section 5. Section 6 concludes the paper.

2 Model description

A detailed description of the G I/M S P/1 queue is given in Chaudhry et al. [3], Gupta and Banik [2], and Bocharov et al. [1]. We give a brief account of the model for the sake of completeness. We consider a single-server infinite-buffer G I/M S P/1 queueing system wherein interarrival times are independently identically distributed (i.i.d.) random variables (r.vs.) with distribution function (DF) A(x), Laplace-Stieltjes transform (LST) $\widetilde {A}(s)$ and mean interarrival time $1/\lambda =-\frac {d}{ds}\widetilde {A}(s)|_{s=0}$. The customers are served according to an m-state continuous-time Markovian service process (MSP) with matrix representation (L ₀, L ₁), called service process. Note that the matrix L ₀ = [(L ₀) _{i j} ] has non-negative off-diagonal and negative diagonal elements, and the matrix L ₁ = [(L ₁) _{i j} ] has non-negative elements. The sum (L ₀ + L ₁) is an irreducible infinitesimal generator of the Markov chain underlying MSP so that (L ₀ + L ₁)e = 0, where e is an m × 1 column vector with all its elements equal to 1. Let $\overline {\boldmath {\pi }}=[\overline {\pi }_{1},\overline {\pi }_{2}, \ldots ,\overline {\pi }_{m}]$ be the stationary probability vector of the Markov process with an infinitesimal generator (L ₀ + L ₁), where $\overline {\pi }_{j}$ denotes the steady-state probability of service process being in phase j. The stationary probability row-vector $\overline {\boldmath {\pi }}$ can be calculated from $\overline {\boldmath {\pi }}(\textbf {L}_{0} + \textbf {L}_{1}) = \textbf {0}$ with $\overline {\boldmath {\pi }}\textbf {e}=1$. The fundamental service rate for the service process is given by $\mu ^{\star }=\overline {\boldmath {\pi }}{\textbf {L}}_{1}\textbf {e}$. The traffic intensity is then given by ρ = λ/μ ^⋆ < 1. Let N(t) denote the number of customers served in the first t time units when the server is busy and I(t) the state of the underlying Markov chain (called service phase) after the same amount of time. Then {N(t), I(t)} _{t ≥ 0} is a two-dimensional Markov process with state space {(n, i):n ≥ 0, 1 ≤ i ≤ m}.

Let P(n, t) = [P _{i j} (n, t)], n ≥ 0, t ≥ 0 denote the matrix of order m × m whose (i, j)-th element represents the probability that n customers are served in (0, t] with the service process being in phase j at time t, provided initially there were at least (n + 1) customers (including the one in service) in the system and the service process was in phase i. Then, the probabilities

$$\begin{array}{@{}rcl@{}} P_{ij}(n,t) = Pr\{N(t) = n,I(t) = j|N(0) = 0,I(0) = i\},\quad 1\leq i,j\leq m \end{array} $$

lead to the following differential-difference equations in matrix notation as:

$$\begin{array}{@{}rcl@{}} \frac{d}{dt}\textbf{P}(0,t)&=&\textbf{P}(0,t)\textbf{L}_{0},\quad t>0 \end{array} $$

(1)

$$\begin{array}{@{}rcl@{}} \frac{d}{dt}\textbf{P}(n,t)&=&\textbf{P}(n,t)\textbf{L}_{0}+{\textbf{P}}(n-1,t)\textbf{L}_{1}, n\geq 1, t>0, \end{array} $$

(2)

with P(0, 0) = I _m and P(n, 0) = 0 , n ≥ 1, where I _m is the identity matrix of order m × m.

Let us define the matrix-generating function P ^∗(z, t) as

$$\begin{array}{@{}rcl@{}} \textbf{P}^{\ast}(z,t) = \sum\limits_{n=0}^{\infty}\textbf{P}(n,t)z^{n},\quad |z|\leq 1, t\geq 0. \end{array} $$

(3)

Multiplying (1) by z ⁰ and (2) by z ⁿ and summing over n = 0 to ∞, after using Eq. 3, we get

$$\begin{array}{@{}rcl@{}} \frac{d}{dt}\textbf{P}^{\ast}(z,t)&=&\textbf{P}^{\ast}(z,t)\left(\textbf{L}_{0}+z\textbf{L}_{1}\right),\quad |z|\leq 1, t>0, \end{array} $$

with P ^∗(z, 0) = I _m . Solving the above matrix-differential equations, we get

$$\begin{array}{@{}rcl@{}} \textbf{P}^{\ast}(z,t)&=&e^{\left(\textbf{L}_{0}+z\textbf{L}_{1}\right)t},\quad |z|\leq 1, t\geq 0. \end{array} $$

(4)

Now, we can write (4) as

$$\begin{array}{@{}rcl@{}} \sum\limits_{n=0}^{\infty}\textbf{P}(n,t)z^{n}&=&\sum\limits_{n=0}^{\infty}\left(\sum\limits_{k=n}^{\infty}\frac{t^{k}}{k!}\textbf{S}_{n}^{(k)}\right)z^{n},\quad |z|\leq 1, t\geq 0, \end{array} $$

(5)

where

$$\begin{array}{@{}rcl@{}} \textbf{S}_{0}^{(k)}&=&\textbf{S}_{0}^{(k-1)}\textbf{L}_{0},\quad k\geq 1 \end{array} $$

(6)

$$\begin{array}{@{}rcl@{}} \textbf{S}_{n}^{(k)}&=&\textbf{S}_{n}^{(k-1)}\textbf{L}_{0}+\textbf{S}_{n-1}^{(k-1)}\textbf{L}_{1},\quad n\geq 1, k\geq 1, \end{array} $$

(7)

with $\textbf {S}_{0}^{(0)}=\textbf {I}_{m}$ and $\textbf {S}_{n}^{(k)}=\textbf {0}$ , n > k ≥ 0.

Now, collecting the coefficient of z ⁿ from both sides of Eq. 5, we obtain

$$\begin{array}{@{}rcl@{}} \textbf{P}(n,t) = \sum\limits_{k=n}^{\infty}\frac{t^{k}}{k!}\textbf{S}_{n}^{(k)},\quad n\geq 0, t\geq 0. \end{array} $$

(8)

Note that the matrices $\textbf {S}_{n}^{(k)}$ do not depend on t and hence these have to be computed only once.

According to the definition of S _n , n ≥ 0, defined in Chaudhry et al. [3, p. 225], we have

$$\begin{array}{@{}rcl@{}} \textbf{S}_{n}={\int}_{\!\!\!0}^{\infty}\textbf{P}(n,t)dA(t), n\geq 0. \end{array} $$

(9)

The matrices S _n , n ≥ 0, can be carried out for phase-type interarrival-time distribution along the lines given in Chaudhry et al. [3, p. 243].

For deterministic interarrival-time distribution with mean interarrival time h = 1/λ, using Eq. 8, we have

$$\begin{array}{@{}rcl@{}} \textbf{S}_{n}=\sum\limits_{k=n}^{\infty}\frac{h^{k}}{k!}\textbf{S}_{n}^{(k)},\quad n\geq 0. \end{array} $$

(10)

We assume that the service process is interrupted during idle periods of the system, that is, the service phase does not change during idle periods of the system. Then according to the definition of $\widehat {\textbf {S}}_{n}$, n ≥ 1, defined in Chaudhry et al. [3, p. 226-227], we have

$$\begin{array}{@{}rcl@{}} \widehat{\textbf{S}}_{n}={\int}_{\!\!\!0}^{\infty}\widetilde{\textbf{P}}(n,t)dA(t),\quad n\geq 1, \end{array} $$

where

$$\begin{array}{@{}rcl@{}} \frac{d}{dt}\widetilde{\textbf{P}}(n,t) = \textbf{P}(n-1,t)\textbf{L}_{1},\quad n\geq 1,\quad \text{with}\quad \widetilde{\textbf{P}}(n,0) = \textbf{0}, n\geq 1. \end{array} $$

(11)

See Chaudhry et al. [3, p. 227] for details derivation of $\widehat {\textbf {S}}_{n}$, n ≥ 1.

In order to obtain the sojourn-time distribution, we first present the system-length distribution just before an arrival epoch. Let the k-th customer arrive at time instant τ _k , k = 0, 1, … , with τ ₀ = 0, and let $\tau ^{-}_{k}$ denote the prearrival epoch, i.e., the time epoch just before the arrival instant τ _k . Then the state of the system at $\tau ^{-}_{k}$ defined as $\left \{Y_{\tau ^{-}_{k}}, J_{\tau ^{-}_{k}}\right \}$ is a Markov chain, where $Y_{\tau ^{-}_{k}}$ represents the number of customers in the system and $J_{\tau ^{-}_{k}}$ the phase of the service process at the imbedded point $\tau ^{-}_{k}$. In the limiting case, let us define $\pi ^{-}_{j}(n) = \lim _{k\to \infty }P\left (Y_{\tau ^{-}_{k}}=n,J_{\tau ^{-}_{k}}=j\right ), n\geq 0, 1\leq j\leq m$, where $\pi ^{-}_{j}(n)$ represents the prearrival epoch probability that there are n customers in the system and the server is busy in phase j, when n ≥ 1, and idle in phase j, when n = 0. Let π ⁻(n) be the 1 × m vector whose j-th component is $\pi ^{-}_{j}(n)$, n ≥ 0. Now observing the state of the system at two consecutive imbedded points, we have

$$\begin{array}{@{}rcl@{}} {\boldmath{\pi}}^{-}(0)&=&\sum\limits_{r=0}^{\infty} {\boldmath{\pi}}^{-}(r)\widehat{\textbf{S}}_{r+1} \end{array} $$

(12)

$$\begin{array}{@{}rcl@{}} {\boldmath{\pi}}^{-}(n)&=&\sum\limits_{r=n-1}^{\infty} {\boldmath{\pi}}^{-}(r)\textbf{S}_{r-n+1}, n \geq 1. \end{array} $$

(13)

Based on the matrix-geometric method given in Neuts [4], we have

$$\begin{array}{@{}rcl@{}} {\boldmath{\pi}}^{-}(n) = \boldmath{\pi}^{-}(0)\textbf{R}^{n}, n\geq 0,~~\text{with}~~\textbf{R}^{0}=\textbf{I}_{m}, \end{array} $$

(14)

and π ⁻(0) is obtained from π ⁻(0) = π ⁻(0)S[R] with the normalizing condition π ⁻(0)(I _m − R)⁻¹ e = 1, where $\textbf {S}[\textbf {R}]=\sum \nolimits _{k=1}^{\infty }\textbf {R}^{k-1}\widehat {\textbf {S}}_{k}$. The square matrix R of order m is the minimal non-negative solution to the matrix polynomial equation $\textbf {R}=\sum \nolimits _{k=0}^{\infty }\textbf {R}^{k}\textbf {S}_{k}$ with all eigenvalues of R lie inside the unit disk. This matrix R is evaluated numerically by a simple iterative scheme given in Alfa et al. [5] as follows:

$$\begin{array}{@{}rcl@{}} \textbf{R}(n+1) = \left(\textbf{S}_{0}+\sum\limits_{k=2}^{\infty}\textbf{R}^{k}(n)\textbf{S}_{k}\right)(\textbf{I}-\textbf{S}_{1})^{-1}, ~~\text{with}~~ \textbf{R}(0) = \textbf{0}, \end{array} $$

where R(n) is the value of R at the n ^th iteration.

3 Sojourn-time distribution

In this section, we obtain an explicit closed-form expression for the sojourn-time distribution of an arrival customer in the system. By the sojourn time we mean the total time spent by a customer in the system (from its arrival until departure). Let W(x) = [W ₁(x), W ₂(x), … , W _m (x)], x ≥ 0, denote the 1 × m vector whose i-th component W _i (x) represents the steady-state joint probability that an arrival customer has to wait at most a time x before complete service with the service process being in phase i. Noting that an arrival customer waits more than x units of time to complete service iff he sees upon arrival some n ≥ 0 customers ahead of him and n service completions occur in the interval (0, x]. The elementary probability vector d W(x) that an arrival customer completes his service in the time interval (x, x + d x] is given by

$$\begin{array}{@{}rcl@{}} d\textbf{W}(x)&=&\sum\limits_{n=0}^{\infty}{\boldmath{\pi}}^{-}(n)\textbf{P}(n,x)\textbf{L}_{1}dx. \end{array} $$

(15)

Now, using Eqs. 8 and 14 in Eq. 15, we obtain the vector probability density function $\textbf {w}(x) = \frac {d}{dx}\textbf {W}(x)$ which is given by

$$\begin{array}{@{}rcl@{}} \textbf{w}(x)&=&{\boldmath{\pi}}^{-}(0)\sum\limits_{n=0}^{\infty}\textbf{R}^{n}\sum\limits_{k=n}^{\infty}\frac{x^{k}}{k!}\textbf{S}^{(k)}_{n}\textbf{L}_{1}\\&=&{\boldmath{\pi}}^{-}(0)\sum\limits_{k=0}^{\infty}\frac{x^{k}}{k!}\sum\limits_{n=0}^{k}\textbf{R}^{n}\textbf{S}^{(k)}_{n}\textbf{L}_{1}\\&=&\boldmath{\pi}^{-}(0)e^{(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})x}\textbf{L}_{1},\quad x>0, \end{array} $$

(16)

where $\sum \nolimits _{n=0}^{k}\textbf {R}^{n}\textbf {S}_{n}^{(k)}=(\textbf {L}_{0}+\textbf {R}\textbf {L}_{1})^{k}$, k ≥ 0, taking into account (6), (7) and the fact that the matrices R and (L ₀ + R L ₁) commute, see Horv$\acute {\mathrm {a}}$th et al. [6].

Hence, the actual sojourn-time distribution is obtained as

$$\begin{array}{@{}rcl@{}} \textbf{W}(x)&=&{{\int}_{\!\!\!0}^{x}}\textbf{w}(t)dt\\ &=&\boldmath{\pi}^{-}(0){{\int}_{\!\!\!0}^{x}}e^{(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})t}\textbf{L}_{1}dt\\ &=&\boldmath{\pi}^{-}(0)\left[e^{(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})x}-\textbf{I}_{m}\right](\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})^{-1}\textbf{L}_{1},\quad x\geq 0. \end{array} $$

Further, let $\widetilde {\textbf {w}}(s)$ be the Laplace-transform of w(x) which is given by

$$\begin{array}{@{}rcl@{}} \widetilde{\textbf{w}}(s) = {\int}_{\!\!\!0}^{\infty}e^{-sx}\textbf{w}(x)dx,\quad \mathfrak{R}(s)\geq 0. \end{array} $$

Now, taking the Laplace-transform of (16), we have

$$\begin{array}{@{}rcl@{}} \widetilde{\textbf{w}}(s)&=&\boldmath{\pi}^{-}(0)\left[s\textbf{I}_{m}-(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})\right]^{-1}\textbf{L}_{1}. \end{array} $$

Differentiating the above expression at the point s = 0, we obtain the mean sojourn time W of an arrival customer and it is given by

$$\begin{array}{@{}rcl@{}} W&=&\boldmath{\pi}^{-}(0)\left(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1}\right)^{-2}\textbf{L}_{1}\textbf{e}. \end{array} $$

From the Little’s law, we also have the mean number of customers in the system L as L = λ W.

Remark 1

Gupta and Banik [2] considered a new service restart phase distribution, that is, if the server becomes idle at a certain point with the service phase changes during the idle period of the system, then when a new customer arrives, the service process starts with a new phase distribution f = [f ₁, f ₂, … , f _m ] such that ${\sum }_{j=1}^{m}f_{j}=1$ independent of the path followed by the previous service process. From the result by Gupta and Banik [2], we have π ⁻(n) = C f R ⁿ, n ≥ 0, where C = [f(I _m − R)⁻¹ e]⁻¹. Thus, the actual sojourn-time distribution is

$$\begin{array}{@{}rcl@{}} \textbf{W}(x) = C\textbf{f}\left[e^{(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})x}-\textbf{I}_{m}\right](\textbf{L}_{0}+\textbf{R}\textbf{L}_{1})^{-1}\textbf{L}_{1},\quad x\geq 0. \end{array} $$

The mean sojourn time W of an arrival customer is given by

$$\begin{array}{@{}rcl@{}} W&=&C\textbf{f}\left(\textbf{L}_{0}+\textbf{R}\textbf{L}_{1}\right)^{-2}\textbf{L}_{1}\textbf{e}. \end{array} $$

4 Correlation coefficient of inter-departure times

The inter-departure times in MSP are dependent. The joint probability density function of the inter-departure times X ₀, … , X _i , … , X _n is

$$\begin{array}{@{}rcl@{}} f_{X_{0},\ldots,X_{n}}(x_{0},\ldots,x_{n}) = \boldmath{\theta}\left(\prod\limits_{i=0}^{n}e^{\textbf{L}_{0}x_{i}}\textbf{L}_{1}\right)\textbf{e}, \end{array} $$

where $\boldmath {\theta }=\frac {\overline {\boldmath {\pi }}\textbf {L}_{1}}{\mu ^{\star }}$ is the stationary phase probability vector immediately following an arbitrary service completion, that is, $\boldmath {\theta }=\frac {\overline {\boldmath {\pi }}\textbf {L}_{1}}{\mu ^{\star }}$ is the solution of θ(−L ₀)⁻¹ L ₁ = θ with θ e = 1 as

$$\begin{array}{@{}rcl@{}} \boldmath{\theta}(-\textbf{L}_{0})^{-1}\textbf{L}_{1}&=&\frac{\overline{\boldmath{\pi}}\textbf{L}_{1}(-\textbf{L}_{0})^{-1}\textbf{L}_{1}}{\mu^{\star}}\\ &=&\frac{\overline{\boldmath{\pi}}(-\textbf{L}_{0})(-\textbf{L}_{0})^{-1}\textbf{L}_{1}}{\mu^{\star}}, \text{since}\;\; \overline{\boldmath{\pi}}(\textbf{L}_{0}+\textbf{L}_{1}) = \textbf{0}\\ &=&\frac{\overline{\boldmath{\pi}}\textbf{L}_{1}}{\mu^{\star}}\\ &=&\boldmath{\theta}. \end{array} $$

Now, the expectation of a random variable X _i , i = 0, 1, … , n, is

$$\begin{array}{@{}rcl@{}} E[X_{i}]&=&\boldmath{\theta}\left(\prod\limits_{j=0}^{i-1}{\int}_{0}^{\infty} e^{\textbf{L}_{0}x_{j}}dx_{j}\textbf{L}_{1}\right){\int}_{\!\!\!0}^{\infty} x_{i}e^{\textbf{L}_{0}x_{i}}dx_{i}\textbf{L}_{1}\left(\prod\limits_{j=i+1}^{n}{\int}_{0}^{\infty} e^{\textbf{L}_{0}x_{j}}dx_{j}\textbf{L}_{1}\right)\textbf{e}\\ &=&\boldmath{\theta}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{i} \left[(-\textbf{L}_{0})^{-2}\textbf{L}_{1}\right]\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n-i}\textbf{e}\\ &=&\frac{1}{\mu^{\star}},~~\text{since}~~\overline{\boldmath{\pi}}(\textbf{L}_{0}+\textbf{L}_{1}) = \textbf{0}~~ \text{and}~~(\textbf{L}_{0}+\textbf{L}_{1})\textbf{e}=\textbf{0}, \end{array} $$

where ${\prod }_{j=0}^{i-1}~{\int }_{0}^{\infty } e^{\textbf {L}_{0}x_{j}}dx_{j}\textbf {L}_{1}=\textbf {I}_{m}$, for i = 0.

The variance of a random variable X _i , i = 0, 1, … , n, is

$$\begin{array}{@{}rcl@{}} Var[X_{i}]&=&E\left[{X_{i}^{2}}\right]-(E\left[X_{i}\right])^{2}\\ &=&\boldmath{\theta}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{i}{\int}_{0}^{\infty} {x_{i}^{2}}e^{\textbf{L}_{0}x_{i}}dx_{i}\textbf{L}_{1}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n-i}\textbf{e}-\frac{1}{\mu^{\star 2}}\\ &=&2\boldmath{\theta}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{i} \left[(-\textbf{L}_{0})^{-3}\textbf{L}_{1}\right]\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n-i}\textbf{e}-\frac{1}{\mu^{\star 2}}\\ &=&\frac{2\overline{{\boldmath{\pi}}}(-\textbf{L}_{0})^{-1}\textbf{e}}{\mu^{\star}}-\frac{1}{\mu^{\star 2}}. \end{array} $$

The expectation of X ₀ X _n is

$$\begin{array}{@{}rcl@{}} E[X_{0}X_{n}]&=&\boldmath{\theta}{\int}_{\!\!\!0}^{\infty} x_{0}e^{\textbf{L}_{0}x_{0}}dx_{0}\textbf{L}_{1}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n-1}{\int}_{\!\!\!0}^{\infty} x_{n}e^{\textbf{L}_{0}x_{n}}dx_{n}\textbf{L}_{1}\textbf{e}\\ &=&\boldmath{\theta}\left[(-\textbf{L}_{0})^{-2}\textbf{L}_{1}\right]\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n-1}\left[(-\textbf{L}_{0})^{-2}\textbf{L}_{1}\right]\textbf{e}\\ &=&\frac{\overline{{\boldmath{\pi}}}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n}(-\textbf{L}_{0})^{-1}\textbf{e}}{\mu^{\star}}, \quad n\geq 1. \end{array} $$

The auto covariance function of two inter-departure times X ₀ and X _n with n lags apart is given by

$$\begin{array}{@{}rcl@{}} E[(X_{0}-E[X_{0}])(X_{n}-E[X_{n}])]&=&E[X_{0}X_{n}]-E[X_{0}]E[X_{n}]\\ &=&\frac{\overline{{\boldmath{\pi}}}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n}(-\textbf{L}_{0})^{-1}\textbf{e}}{\mu^{\star}}-\frac{1}{\mu^{\star 2}}. \end{array} $$

The lag-n correlation coefficient of inter-departure times for a stationary MSP is computed as

$$\begin{array}{@{}rcl@{}} Corr[X_{0},X_{n}]&=&\frac{E[(X_{0}-E[X_{0}])(X_{n}-E[X_{n}])]}{\sqrt{Var[X_{0}]}\sqrt{Var[X_{n}]}}\\ &=&\frac{\mu^{\star}\overline{{\boldmath{\pi}}}\left[(-\textbf{L}_{0})^{-1}\textbf{L}_{1}\right]^{n}(-\textbf{L}_{0})^{-1}\textbf{e}-1}{2\mu^{\star}\overline{{\boldmath{\pi}}}(-\textbf{L}_{0})^{-1}\textbf{e}-1}, \quad n\geq 1. \end{array} $$

5 Numerical result

We have carried out numerical work based on the procedure discussed in this paper. Several outputs were generated and it is found that the mean sojourn time W and the mean number of customers in the system L were matched against some existing results, for examples, Chaudhry et al. [3], and Gupta and Banik [2]. In order to study the behavior of G I/M S P/1 queue on various performance measures, we present some numerical results. The sojourn-time distribution has been presented in Tables 1, 2, and 3. We also show the effect of traffic intensity ρ on the mean sojourn time W and the mean number of customers in the system L in Figs. 1, 2, 3, 4, 5, and 6.

Table 1 Sojourn-time distribution of an arrival customer in case of deterministic interarrival-time distribution

Table 2 Sojourn-time distribution of an arrival customer in case of Chaudhry et al. [3]

Table 3 Sojourn-time distribution of an arrival customer in case of Gupta and Banik [2]

Fig. 1

Comparison of mean sojourn time (W) under different traffic intensity (ρ) in three interarrival-time distributions and the same mean service rate μ ^⋆ = 1

Fig. 2

Comparison of mean number of customers in the system (L) under different traffic intensity (ρ) in three interarrival-time distributions and the same mean service rate μ ^⋆ = 1.

Fig. 3

Comparison of mean sojourn time (W) under different traffic intensity (ρ) in different correlations of service processes

Example 1

The sojourn-time distribution has been presented in Table 1, when the interarrival-time distribution is deterministic with λ = 3.333333. The sojourn-time distribution has been presented in Table 2, when the interarrival-time distribution is phase-type. We have used the following matrices L ₀ and L ₁ of order 4 of the Markovian service process for Tables 1 and 2. The matrices L ₀ and L ₁ of the Markovian service process and the interarrival-time distribution are same as considered in Chaudhry et al. [3]:

$$\textbf{L}_{0}\,=\,\left[ \begin{array}{cccc} -15.449&0.116&0.052&0.000\cr 0.092&-5.069&0.000&0.062\cr 0.000&0.213&-4.832&4.430\cr 0.059&5.033&0.000&-5.321 \end{array} \right], \textbf{L}_{1}\,=\,\left[ \begin{array}{cccc} 15.068&0.157&0.000&0.056\cr 0.123&0.047&4.745&0.000 \cr 0.084&0.000&0.000&0.105\cr 0.051&0.000&0.077&0.101 \end{array} \right].$$

This leads to $\overline {\boldmath {\pi }}=\left [\begin {array}{cccc} 0.264645&0.253046&0.254961&0.227348 \end {array}\right ]$ with μ ^⋆ = 5.388016. The phase-type interarrival-time representation P H(α, T) is given by

$${\boldmath{\alpha}}=\left[ \begin{array}{ccc} 0.22 & 0.33 & 0.45 \end{array} \right], \textbf{T}=\left[ \begin{array}{ccc} -7.423 & 0.000 & 3.812 \cr 8.542 & -9.942 & 1.000 \cr 5.210 & 0.000 & -8.640 \end{array} \right].$$

This leads to λ = 3.198147 so that ρ = 0.593567.

Example 2

The sojourn-time distribution has been presented in Table 3 for a new service restart phase distribution considered in Gupta and Banik [2]. The following matrices L ₀ and L ₁ of order 2 of the Markovian service process (MSP), $\textbf {f}=\left [\begin {array}{cc}0.6&0.4 \end {array}\right ]$and the phase-type interarrival-time distribution are same as considered in Gupta and Banik [2]:

$$\textbf{L}_{0}=\left[ \begin{array}{cccc} -3.39&0.00\cr 0.00&-0.21 \end{array} \right], \textbf{L}_{1}=\left[ \begin{array}{cccc} 3.19&0.20\cr 0.20&0.01 \end{array} \right].$$

This leads to $\overline {\boldmath {\pi }}=\left [\begin {array}{cc}0.5&0.5 \end {array}\right ]$ with μ ^⋆ = 1.8. The phase-type interarrival-time representation P H(α, T) is given by

$$\begin{array}{@{}rcl@{}}{\boldmath{\alpha}}=\left[\begin{array}{cc}0.3&0.7 \end{array}\right]\quad \textbf{T}=\left[ \begin{array}{cccc} -0.60& 0.074 \cr 0.0575&-0.45 \end{array} \right].\end{array} $$

This leads to λ = 0.430391 so that ρ = 0.239106.

Example 3

The following three interarrival-time distributions, and the Markovian service process (MSP) are used to obtain Figs. 1 and 2.

• (i) Deterministic (D) with mean 1/λ.

• (i i) Erlang (E ₂) with representation $\boldmath {\alpha }=\left [\begin {array}{cc}1&0 \end {array}\right ]$, $\textbf {T}=\left [ \begin {array}{cccc} -2\lambda & 2\lambda \cr 0&-2\lambda \end {array} \right ]$.

• (i i i) PH-type with representation $\boldmath {\alpha }=\left [\begin {array}{cc}0.2&0.8 \end {array}\right ]$, $\textbf {T}=\left [ \begin {array}{cccc} -2\lambda & \lambda \cr 4\lambda &-5\lambda \end {array} \right ]$.

• The MSP is taken as

  $$\textbf{L}_{0}=\left[ \begin{array}{cccc} -1.625&0.25\cr 0.875&-1.375 \end{array} \right], \textbf{L}_{1}=\left[ \begin{array}{cccc} 0.875&0.5\cr 0.125&0.375 \end{array} \right]~ \text{with}~~ \mu^{\star}=1.$$

We consider a service rate of 60 aircraft per hour which implies that the service time has a mean of 1 minute. With this service rate, we use the arrival rate to capture the various traffic intensity ρ. In particular, we use an arrival rate of 6, 12, 18, 24, 30, 36, 42, 48 and 54 aircraft per hour which leads to ρ = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, and 0.9, respectively. Figures 1 and 2 indicate that both W and L for an E ₂/M S P/1 system lie between P H/M S P/1 and D/M S P/1. It is evident from these graphs that the differences among E ₂/M S P/1, P H/M S P/1 and D/M S P/1 increase as the level of congestion in the system ρ increases. We further observe that for all distributions considered here, both W and L consistently increase as the level of congestion in the system increases. Again, deterministic interarrival-time distribution yields the lowest W and L both.

Example 4

The following PH-type interarrival-time distribution, and the service matrices L ₀ and L ₁ of order 2 of the service process MSP with the same mean μ ^⋆ = 0.5 are used to obtain Figs. 3 and 4.

• PH: The PH-type representation is taken as

  $${\boldmath{\alpha}}=\left[\begin{array}{cc}0.2& 0.8 \end{array}\right], \quad \textbf{T}=\left[ \begin{array}{cccc} -2\lambda& \lambda \cr 4\lambda&-5\lambda \end{array} \right].$$

• MSP₁: The MSP is taken as

  $$\textbf{L}_{0}=\left[ \begin{array}{ccc} -6.899999& 0.9\\ 0.06& -0.193333 \end{array} \right], \textbf{L}_{1}=\left[ \begin{array}{cc} 5.999999&0.0\\ 0.0&0.133333 \end{array} \right]$$

  with correlation coefficient 0.148261.

• MSP₂: The MSP is taken as

  $$\textbf{L}_{0}=\left[ \begin{array}{cccc} -0.42& 0.10\cr 0.38& -1.24 \end{array} \right], \textbf{L}_{1}=\left[ \begin{array}{cccc} 0.21& 0.11\cr 0.04& 0.82 \end{array} \right]$$

  with correlation coefficient 0.017338.

• MSP₃: The MSP is taken as

  $$\textbf{L}_{0}=\left[ \begin{array}{cccc} -1.5125& 0.750\cr 0.875& -1.025 \end{array} \right], \textbf{L}_{1}=\left[ \begin{array}{cccc} 0.7625& 0.0\cr 0.125& 0.025 \end{array} \right]$$

  with correlation coefficient 0.00005.

We consider a service rate of 30 aircraft per hour which implies that the service time has a mean of 2 minutes. With this service rate, we use the arrival rate to capture the various traffic intensity ρ. In particular, we use an arrival rate of 3, 6, 9, 12, 15, 18, 21, 24 and 27 aircraft per hour which leads to ρ = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, and 0.9, respectively. The effect of the level of congestion in the system ρ on both W and L for various correlation coefficients (Corr) with lag-2 is shown in Figs. 3 and 4, respectively. It is seen that correlation has a big impact. For fixed ρ, both W and L increase with the increase in the value of correlation coefficient. Further, it can be seen that for fixed value of correlation coefficient both W and L increase as ρ increases. It is evident that both W and L are higher for MSP₁. This is due to the high correlation among the services considered here. This study tells that not only interarrival times and the level of congestion in the system play an important role in queueing processes, but also the correlation among all sides of ground/terminal operations, efficient management of various air traffic and technological improvements at airport plays a major role.

Fig. 4

Comparison of mean number of customers in the system (L) under different traffic intensity (ρ) in different correlations of service processes

Example 5

The PH-type interarrival-time distribution, and the service matrices L ₀ and L ₁ of order 2 of MSP₁ and MSP₂ in Example 4 along with the vector $\textbf {f}=\left [\begin {array}{cc}0.6& 0.4 \end {array}\right ]$ are used to obtain Figs. 5 and 6. These figures also display the mean sojourn time and the mean number of customers in the system, respectively, as a function of the level of congestion in the system for two situations of service (i) phase does not change during idle period, and (i i) a new service restart phase distribution models with same mean service time. We observe the similar behavior as seen in Figs. 3 and 4 when the level of congestion in the system increases. Furthermore, phase does not change during idle period queueing system gives the better performance as compared to a new service restart phase distribution queueing system.

Fig. 5

Comparison of mean sojourn time (W) under different traffic intensity (ρ) in two situations of service with different correlations

Fig. 6

Comparison of mean number of customers in the system (L) under different traffic intensity (ρ) in two situations of service with different correlations

6 Conclusion

In this paper, we have presented a procedure to obtain closed-form expression of the actual sojourn-time distribution of an arrival customer in the G I/M S P/1 queueing system. This may be useful to estimate air traffic delays at airport. An airport can be interpreted as a queueing system where landing of aircrafts on the runways may be arriving customers. The Markovian service process (MSP) may be used for better tracking of actual flight paths, all sides of ground/terminal operations, efficient management of various air traffic and technological improvements in aircraft monitoring.