Queueing Systems with Unreliable Servers in a Random Environment

Abstract

A single-server queueing system with a Poisson input and an unreliable server is studied. The breakdowns of the server are connected to a certain external factor, defined by a regenerative stochastic process. In this paper one assumes that the arrival process, customers’s service times, and an external environment are mutually independent. The service was interrupted by the breakdown of the server is continued after its reconstruction from the point at which it was interrupted. The Laplace–Stiltjese transform of the stationary distribution of virtual waiting time as well as ergodicity condition is given. The limit theorem in heavy traffic situation is established. Two examples of the applications are considered.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1.1 Introduction

We consider a single-server queueing system with unreliable server operating in a random environment. One would like to point out that the systems with unreliable servers have been intensively investigated for a long time now. Corresponding models are systems with interruptions of the service. This direction of research is represented by a vast collection of literature. The setting of the problems and the solutions can be found in the paper of Krishnamoorty et al. [7].

In this paper one assumes that the breakdowns of the server are connected to a certain external factor. The external environment is a regenerative stochastic process and the breakdowns of the server occur in accordance with the points of regeneration of this process. The similar model was investigated in the pioneering paper [5]. It was assumed that a breakdown can appear only if the server is occupied by a customer. The notion of completion time, which is the generalization of the service time was introduced. This notion made it possible to apply results for a queueing system $M\vert G\vert 1\vert \infty$ with a reliable server to investigate a system subjected to interruptions, i.e. with unreliable server.

Key elements of our analysis are the coupling of renewal processes [4] based on the structure of the random environment, construction of auxiliary processes, and relations between their characteristics and characteristics of the basic process. Note that more general models were investigated in [1]. All the statements of this paper are fulfilled for the model under consideration. But here we focus on another problems. Namely, we find the stationary distribution of the virtual waiting time process and prove the limit theorem for this distribution in heavy traffic situation.

The paper is organized as follows. In the next section the queueing system and the random environment are described and basic relations are established. The ergodic condition is also given. In Sect. 1.3 Laplace–Stiltjese transform (LST) for the stationary distribution of the virtual waiting time is obtained and heavy traffic situation is investigated. Section 1.4 is devoted to two examples. The first one concerns the system operating in a Markov random environment. The model can be applied for analysis of systems with a preemptive priority discipline. The second example arose as a mathematical model of unregulated crossroads [2, 6]. The random environment is described by the number of customers in a queueing system with infinite number of servers.

1.2 Model Description: Basic Relations

A single-server queueing system with a Poisson input A(t) with an intensity λ and an unreliable server is considered. In such a system the service of a customer is subjected to interruptions that are caused by a random environment U(t) not depending on A(t). It is assumed that U(t) is a regenerative stochastic process and $\{u_{j}\}_{j=1}^{\infty }$ is a sequence of its regeneration periods (see, e.g., [4, 10]). Besides, we suppose that

$$\displaystyle{u_{j} = u_{j}^{(1)} + u_{ j}^{(2)}}$$

where u _j ⁽¹⁾ and u _j ⁽²⁾ are independent random variables and

$$\displaystyle{\mathsf{P}(u_{j}^{(1)}\leqslant x) = 1 - e^{-\alpha x},\quad \mathsf{P}(u_{ j}^{(2)}\leqslant x) = G(x).}$$

Let us introduce the sequences

$$\displaystyle{s_{n}^{(2)} =\sum \limits _{ j=1}^{n}u_{ j}^{(2)},\quad s_{ 0}^{(2)} = 0,\quad s_{ n}^{(1)} = s_{ n-1}^{(2)} + u_{ n}^{(1)},\quad n = 1,2,\ldots }$$

so that

$$\displaystyle{0 = s_{0}^{(2)} < s_{ 1}^{(1)} < s_{ 1}^{(2)},\ldots }$$

and

$$\displaystyle{u_{n}^{(1)} = s_{ n}^{(1)} - s_{ n-1}^{(2)},\quad u_{ n}^{(2)} = s_{ n}^{(2)} - s_{ n}^{(1)}.}$$

The breakdowns of the server occur at time moments s _n ⁽¹⁾ and the server is repairing till the moments $s_{n}^{(2)},n = 1,2,\ldots$. We suppose that the service was interrupted by the breakdown of the server is continued after reconstruction from the point at which it was interrupted. Service times $\{\eta _{j}\}_{j=1}^{\infty }$ are independent identically distributed random variables not depending on A(t) and U(t).

To investigate the model we employ coupling method as it was done for more general model in [1]. Introduce the following notation

$$\displaystyle\begin{array}{rcl} & & \qquad \qquad \qquad B(x) = \mathsf{P}(\eta _{j}\leqslant x), {}\\ & & b(s) =\int \limits _{ 0}^{\infty }e^{-sx}dB(x),\quad g(s) =\int \limits _{ 0}^{\infty }e^{-sx}dG(x), {}\\ & & \quad \qquad b = \mathsf{E}\eta _{1},\quad a = \frac{1} {\alpha },\quad g_{1} = \mathsf{E}u_{1}^{(2)} {}\\ \end{array}$$

and assume that $b < \infty$ and $g_{1} < \infty$.

Let W(t) be the virtual waiting time process and q(t) be the number of customers in the system at a time t.

Theorem 1.1.

Processes W(t) and q(t) are ergodic if and only if traffic coefficient

$$\displaystyle{ \rho =\lambda (1 +\alpha g_{1})b < 1. }$$

(1.1)

This result follows from Theorem 3 in [1]. The proof is based on the following representation that will be also applied later on.

We introduce two auxiliary processes $\tilde{W}(t)$ and $\tilde{W}^{{\ast}}(t)$ by the relations

$$\displaystyle{ \tilde{W}(t) = W\left (t + S_{N_{1}(t)}^{(2)}\right ),\quad \tilde{W}^{{\ast}}(t) = W\left (t + S_{ N_{2}(t)}^{(1)}\right ) }$$

(1.2)

where

$$\displaystyle{S_{k}^{(i)} =\sum \limits _{ j=1}^{k}u_{ j}^{(i)},\quad N_{ i}(t) =\sup \{ k: S_{k}^{(i)}\leqslant t\},\,\,i = 1,2.}$$

We see that $\tilde{W}(t)(\tilde{W}^{{\ast}}(t))$ is obtained from W(t) by the deletion of time intervals when the server is restored (is in the working state). To express W(t) by means of $\tilde{W}(t)$ and $\tilde{W}^{{\ast}}(t)$ we define the event

$$\displaystyle{ C_{t} =\bigcup \limits _{ n=0}^{\infty }\{t \in [s_{ n}^{(2)},s_{ n+1}^{(1)})\} }$$

(1.3)

and random variables

$$\displaystyle{r_{t} = (t - S_{N}(t))\chi (C_{t}),\quad r_{t}^{{\ast}} = (t - u_{ N(t)+1}^{(1)} - S_{ N}(t))\chi (\overline{C}_{t})}$$

where

$$\displaystyle{N(t) =\sup \{ k: S_{k}\leqslant t\},\quad S_{k} = S_{k}^{(1)} + S_{ k}^{(2)}.}$$

Then one can easily obtain from (1.2) and (1.3)

$$\displaystyle{ W(t) =\tilde{ W}(r_{t} + S_{N(t)}^{(1)})\chi (C_{ t}) +\tilde{ W}^{{\ast}}(r_{ t}^{{\ast}} + S_{ N(t)}^{(2)})\chi (\overline{C}_{ t}). }$$

(1.4)

Note that the event C _t means that the server is in the working state at a time t. Let

$$\displaystyle{V (t) = \vert \tilde{W}(r_{t} + S_{N(t)}^{(1)}) -\tilde{ W}^{{\ast}}(r_{ t}^{{\ast}} + S_{ N(t)}^{(2)})\vert.}$$

It follows from Lemma 1 in [1] that for any fixed $t\geqslant 0$

$$\displaystyle{ \lim \limits _{y\rightarrow \infty }\mathsf{P}(\limsup \limits _{T\rightarrow \infty }V (tT < y)) = 1. }$$

(1.5)

This relation was employed in [1] for the proof of the ergodic theorem as well as for the asymptotic analysis of W(t) and q(t) in heavy traffic situation. Functional limit theorems for these processes were also established. All the statements from [1] are valid for our model but here we focus on the limit distribution

$$\displaystyle{\varPhi (x) =\lim \limits _{t\rightarrow \infty }\mathsf{P}(W(t)\leqslant x).}$$

In view of Theorem 1.1 this distribution exists if and only if ρ < 1. First we obtain the expression for

$$\displaystyle{\varphi (s) =\int \limits _{ 0}^{\infty }e^{-sx}d\varPhi (x)}$$

and then we investigate the behavior of the function Φ(x) in the heavy traffic situation ($\rho \uparrow 1$). Our proofs are based on the results for a queueing system $M\vert G\vert 1\vert \infty$ with a reliable server (see, e.g., [8]) and relations (1.4) and (1.5).

1.3 Limit Distribution of Virtual Waiting Time

Theorem 1.2.

Let ρ < 1. Then the following relation takes place

$$\displaystyle{ \varphi (s) =\tilde{\varphi } (s)\left ( \frac{1} {1 +\alpha g_{1}} + \frac{\alpha g_{1}} {1 +\alpha g_{1}}v(s)\right ) }$$

(1.6)

where

$$\displaystyle{ \tilde{\varphi }(s) = (1-\rho )\left (1 - (\lambda +\alpha )\frac{1 -\tilde{ b}(s)} {s} \right )^{-1}, }$$

(1.7)

$$\displaystyle{ \tilde{b}(s) = \frac{\lambda } {\lambda +\alpha }b(s) + \frac{\alpha } {\lambda +\alpha }g(\lambda (1 - b(s))), }$$

(1.8)

$$\displaystyle{ v(s) = \frac{1 - g(\lambda (1 - b(s)))} {g_{1}\lambda (1 - b(s))}. }$$

(1.9)

Proof.

Denote by

$$\displaystyle{\tilde{\varPhi }(x) =\lim \limits _{t\rightarrow \infty }\mathsf{P}(\tilde{W}(t)\leqslant x),\quad \tilde{\varPhi }^{{\ast}}(x) =\lim \limits _{ t\rightarrow \infty }\mathsf{P}(\tilde{W}^{{\ast}}(t)\leqslant x),}$$

where $\tilde{W}(t)$ and $\tilde{W}^{{\ast}}(t)$ are defined by (1.2). Let $\varphi (s)$ and $\tilde{\varphi }(s)$ be LST of the distribution functions Φ(x) and $\tilde{\varPhi }(x)$, respectively. It follows from (1.4) that

$$\displaystyle{ \mathsf{E}e^{-sW(t)} = \mathsf{E}e^{-s\tilde{W}(r_{t}+S_{N(t)}^{(1)}) }\chi (C_{t}) + \mathsf{E}e^{-s\tilde{W}^{{\ast}}(r_{ t}^{{\ast}}+S_{ N(t)}^{(2)}) }\chi (\overline{C}_{t}). }$$

(1.10)

Now employing (1.5) and well-known limit theorems from the renewal theory (see, e.g., [4, 10]) one can take a limit (as $t \rightarrow \infty$ ) in (1.10). It gives the relation

$$\displaystyle{\varphi (s) = \frac{1} {1 +\alpha g_{1}}(\tilde{\varphi }(s) +\alpha g_{1}\tilde{\varphi }^{{\ast}}(s)).}$$

To find $\tilde{\varphi }(s)$ we consider an auxiliary queueing system M | G | 1 with input intensity $\tilde{\lambda }=\lambda +\alpha$ and $\tilde{b}(s)$, defined by (1.8), as the LST of the service time distribution. Since

$$\displaystyle{-\tilde{b}'(0) = \frac{\lambda b} {\lambda +\alpha }(1 +\alpha g_{1})}$$

the traffic coefficient of the system $\tilde{\rho }= (\lambda +\alpha )(-\tilde{b}'(0)) =\rho < 1.$ Therefore the system is ergodic and LST of the limit distribution of the virtual waiting time in this system is given by (1.7) (see, e.g., [8]).

Since the input flow A(t) of the initial system is a Poisson process and u _n ⁽¹⁾ has an exponential distribution with a parameter α the process $\tilde{W}(t)$ is the virtual waiting time process in the auxiliary system M | G | 1 with input intensity λ +α. Besides, one can easy verify that LST of the service time distribution is defined by (1.8).

To find $\tilde{\varphi }^{{\ast}}(s)$ let us denote by γ a random variable with the distribution function $g_{1}^{-1}\int \limits _{0}^{x}(1 - G(y))dy$ not depending on the sequence $\{\eta _{j}\}_{j=1}^{\infty }$ as well as on input A(t). Then the LST of the distribution of the total service time of customers arriving during time interval (0, γ) is given by the relation

$$\displaystyle{v(s) = \mathsf{E}e^{-s\sum \limits _{j=1}^{A(\gamma )}\eta _{ j}} = \frac{1 - g(\lambda (1 - b(s)))} {g_{1}\lambda (1 - b(s))}.}$$

Since A(t) is a Poisson process, then for any sequence $\{t_{n}\}_{n=1}^{\infty }$, $t_{n}\mathop{ \rightarrow }\limits _{n\rightarrow \infty }\infty$ we have

$$\displaystyle{\lim \limits _{n\rightarrow \infty }\mathsf{P}(\tilde{W}(t_{n})\leqslant x) =\varPhi (x).}$$

In view of results from the renewal theory it means that

$$\displaystyle{\tilde{\varphi }^{{\ast}}(s) =\tilde{\varphi } (s)v(s).}$$

To describe the heavy traffic situation we introduce a family of queueing systems $\{S_{\varepsilon }\}$ with input flow $A_{\varepsilon }(t)$ with intensity

$$\displaystyle{\lambda _{\varepsilon } = \frac{1-\varepsilon } {b(1 +\alpha g_{1})}}$$

and traffic coefficient $\rho _{\varepsilon } = 1-\varepsilon \rightarrow 1\quad \text{as}\,\,\varepsilon \rightarrow 0.$

For a system $S_{\varepsilon }$ we mark by $\varepsilon$ stochastic processes and functions introduced previously. So that $W_{\varepsilon }(t)$ is the virtual waiting time process for $S_{\varepsilon }$ and

$$\displaystyle{\varPhi _{\varepsilon }(x) =\lim \limits _{t\rightarrow \infty }\mathsf{P}(W_{\varepsilon }(t)\leqslant x).}$$

Theorem 1.3.

If $b_{2} = \mathsf{E}\eta _{i}^{2} < \infty$ , $g_{2} = \mathsf{E}(u_{n}^{(2)})^{2} < \infty$ , then for any x > 0

$$\displaystyle{\lim \limits _{\varepsilon \rightarrow 0}(1 -\varPhi _{\varepsilon }(\varepsilon x)) = e^{-\frac{2x} {\sigma ^{2}} }}$$

where

$$\displaystyle{ \sigma ^{2} = \frac{b_{2}} {b} + \frac{\alpha g_{2}} {(\alpha g_{1} + 1)^{2}}. }$$

(1.11)

Proof. We apply relations (1.6–1.9) to obtain the result. First we note that

$$\displaystyle{v_{\varepsilon }(\varepsilon s) = \frac{1 - g(\lambda _{\varepsilon }(1 - b(\varepsilon s)))} {g_{1}\lambda _{\varepsilon }(1 - b(\varepsilon s))} \rightarrow 1\quad \mbox{ as}\quad \varepsilon \rightarrow 0.}$$

It is known (see, e.g., [3]) that for M | G | 1 system there exists the limit

$$\displaystyle{\tilde{\varphi }_{\varepsilon }(\varepsilon s) \rightarrow \frac{1} {1 + \frac{\tilde{b}_{2}} {2\tilde{b}}s}}$$

where $\tilde{b}_{2} =\tilde{ b}''(0),\quad \tilde{b} = -\tilde{b}'(0)$. Therefore it is necessary only to find these constants from the relation (1.8).

1.4 Examples

Example 1.

Here we assume that a random environment U(t) is an ergodic Markov chain with the set of states $\{0,1,2,\ldots \}$. We define the points of regenerations of U(t) as the instants when U(t) gets over the state zero. Then u _n ⁽¹⁾ has an exponential distribution with a parameter $\alpha = 1/\mathsf{E}u_{n}^{(1)}$. Let $\{\pi _{j}\}_{j=0}^{\infty }$ be a stationary distribution of the process U(t). Taking into account the equality

$$\displaystyle{\pi _{0} = \frac{\mathsf{E}u_{n}^{(1)}} {\mathsf{E}u_{n}^{(1)} + \mathsf{E}u_{n}^{(2)}} = \frac{1} {1 +\alpha g_{1}}}$$

we see that a traffic coefficient of the system M | G | 1 operating in a Markov random environment U(t) is of the form

$$\displaystyle{\rho = \frac{\lambda b} {\pi _{0}}.}$$

Consider a birth and death Process U(t). Let α _i be an intensity of birth, β _i be an intensity of death in the state i ($i = 0,1,\ldots$), β ₀ = 0. Then U(t) is ergodic Markov chain if and only if [8]

$$\displaystyle{ \sum \limits _{j=1}^{\infty }\prod _{ i=1}^{j}\frac{\alpha _{i-1}} {\beta _{i}} < \infty. }$$

(1.12)

In this case

$$\displaystyle{\pi _{0} = \left (1 +\sum \limits _{ j=1}^{\infty }\prod \limits _{ i=1}^{j}\frac{\alpha _{i-1}} {\beta _{i}} \right )^{-1}}$$

so that process W(t) for a system operating in the random environment U(t) is ergodic if and only if

$$\displaystyle{ \lambda b\left (1 +\sum \limits _{ j=1}^{\infty }\prod \limits _{ i=1}^{j}\frac{\alpha _{i-1}} {\beta _{i}} \right ) < 1. }$$

(1.13)

Consider the case α _i  = α, β _i  = β so that U(t) is the number of customers at a time t in a system $M\vert M\vert 1\vert \infty$. It is well known (see, e.g., [8]) that the LST of the distribution of the busy period is of the form

$$\displaystyle{ g(s) = 2\beta (s +\alpha +\beta -\sqrt{(s +\alpha +\beta )^{2 } - 4\alpha \beta })^{-1}. }$$

(1.14)

With the help of Theorems 1.2 and 1.3 one can find the LST of the stationary distribution of the virtual waiting time process for a system $M\vert G\vert 1\vert \infty$ in a random environment U(t) and analyze its asymptotic behavior in heavy traffic situation. It is evident that we consider, indeed, a system with preemptive priority discipline.

Example 2.

Let a random environment U(t) be the number of customers at a time t in a queueing system $M\vert G\vert \infty$ with a Poisson input with intensity α and F(x) as a distribution function of service time with finite mean c. The points of regenerations of U(t) are the instants when U(t) gets over the state zero. Then the nth regeneration period u _n is of the form $u_{n} = u_{n}^{(1)} + u_{n}^{(2)}$. Here u _n ⁽¹⁾ has an exponential distribution with a parameter α, u _n ⁽²⁾ represents the nth busy period. Besides, u _n ⁽¹⁾ and u _n ⁽²⁾ are independent random variables. The LST of distribution of u _n ⁽²⁾ is defined with the help of the relation (see [9])

$$\displaystyle{ g(s) = \mathsf{E}e^{-su_{n}^{(2)} } = 1 - \frac{s\beta (s)} {\alpha (1 -\beta (s))} }$$

(1.15)

where

$$\displaystyle{\beta (s) =\alpha \int \limits _{ 0}^{\infty }e^{-sx-\alpha \int \limits _{0}^{x}\overline{F}(y)dy }\overline{F}(x)dx,\quad \overline{F}(x) = 1 - F(x).}$$

One can verify that

$$\displaystyle{g_{1} = -g'(0) =\alpha ^{-1}(e^{\alpha c} - 1).}$$

and ergodicity condition is of the form

$$\displaystyle{\rho =\lambda be^{\alpha c} < 1.}$$

If the distribution F(x) has the second moment, we may apply (1.15) to calculate g″(0) and describe the asymptotic behavior of the limit distribution of W(t) with the help of Theorem 1.3. But calculations and formulas are too cumbersome to give them here. Therefore we consider $M\vert D\vert \infty$ with a constant service time c. Then

$$\displaystyle{g(s) = \frac{s+\alpha } {se^{(s+\alpha )c}+\alpha }.}$$

One can easily verify that the normalizing coefficient σ ² from Theorem 1.3 is given by the equality

$$\displaystyle{\sigma ^{2} = \frac{b_{2}} {b} + \frac{2} {\alpha } (e^{\alpha c} - 1 -\alpha c).}$$

This model can be applied for description of the number of vehicles at the intersection roads. Some results in this direction were obtained in [2].