Queueing Theory 2. Nikolaos Limnios

Q(t) is a stochastically bounded process, i.e.

      2 ii)

      CONDITION 1.5.– If

, then for any ϵ > 0 there exists nϵ such that for n > n_ϵ

[1.8]

1.4. Instability result for the case ρ ≥ 1

      THEOREM 1.1.– Let conditions 1.3 and 1.1 (1.2) for the continuous-time (for the discrete-time) case be fulfilled. If ρ ≥ 1, then

      [1.9]

PROOF.– Consider the embedded process Qn = Q(Tn) and denote

      Define the auxiliary sequence

recursion

      Because of the equality

and condition 1.3 we get the stochastic inequality

It is well known (Feller 1971) that

      and in distribution

      For ρ ≥ 1, the sequence

is a random walk with a non-negative drift. Hence, except when

(c is a constant),

(w.p.1) (Feller 1971) that completes the proof. ■

1.5. Stochastic boundedness for the case ρ < 1

      Our objective here is to establish stochastic boundedness of the process Q when the traffic rate ρ < 1. Under some additional assumptions providing the regenerative structure of the process Q, this property has its stability as a consequence.

      THEOREM 1.2.– Let conditions 1.4and 1.5 and condition 1.1 (1.2) for the continuoustime (for the discrete-time) case be fulfilled. If ρ < 1, then Q is a stochastically bounded process.

      PROOF.– Because of condition 1.4 there are two possible cases: Qn = Q(Tn) is either stochastically bounded or

Assume that the second case takes place and ρ < 1. Because of condition 1.5 for

there is nϵ such that for n > nϵ

      that contradicts our assumption that

■

In the next sections, we discuss some examples to verify our results and to compare them with previous works. First, we consider two queueing models with service interruptions. These models occur in numerous applications and there is extensive literature concerning queueing system with interruptions. Let us mention some papers in which detail description of the literature in this sphere is given (Krishnamoorthy et al. 2012; Fiems and Bruneel 2013; Pechinkin et al. 2009; Morozov et al. 2011). However, to the best of our knowledge there are no papers that study the stability problem for multichannel systems with heterogeneous servers for the non-Markovian case: with general input flow and general distribution of blocked and available periods.

1.6. Queueing system with unreliable servers and preemptive resume service discipline

      We consider a continuous-time queueing system with regenerative input flow X and m heterogeneous servers that may be not available for operation from time to time. We also propose that the velocity of the service may be dependent on the state of the server. Assume that for the ith server a stochastic process ni(t) with state space

is defined. If ni(t) = 0, then the ith server is in unavailable state, for instance it is broken; if

then the ith server is working with the velocity

Service times of customers by the ith server in the case when the velocity of the service is equal to one constitute a sequence

of iid random variables, which does not depend on the input flow and service times by other servers,

      It is possible that an unavailable period starts while a customer is receiving service. Then service of the customer is immediately interrupted. There are various disciplines for continuation of the service after restoration (Gaver 1962). Here, we consider the preemptive resume service discipline assuming that interrupted service continues when the server returns from a blocked period and the service velocity is the next state of the process ni(t).

      CONDITION 1.6.–The stochastic process

is strongly regenerative with regeneration points

with an exponential phase

so that

We also assume that

      It follows from condition 1.6 and Smith’s (1955) theorem that there exist the limits

and

      where ji takes values

      To define an auxiliary process Yi(t) for the ith server, we introduce a counting process

      Then

[1.10]