Читать книгу Queueing Theory 2 - Nikolaos Limnios - Страница 17

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]

and

CONDITION 1.7.– Service times have the first exponential phase, i.e.

where and independent random variables and

As regeneration points for Y we take subsequence of the sequence such that at time interrupted services for processes are in the exponential phase. Because of conditions 1.6 and 1.7, Y is a strongly regenerative flow and we may define the common sequence of regeneration points for both processes X and Y with the help of formula [1.4]. We need only to take instead of

Because of [1.10] we can easily obtain from the renewal theory the formula for the rate of the auxiliary process

[1.11]

Now we may calculate the traffic rate ρ and under some assumptions we get the necessary and sufficient stability condition for the system based on theorems 1.1 and 1.2. As an example, we consider the famous case (Morozov et al. 2011) when i.e. a server may be in an available or unavailable state. Let be moments of breakdowns and moments of restorations for the ith server. Here

[1.12]

Then denote the length of the nth blocked and the nth available period for the ith server, respectively, The sequence consists of iid random vectors (for all ) and these sequences do not depend on the input flow X and service times. Let be the length of the nth cycle for the server i. A cycle consists of a blocked period followed by an available period. We assume that

We put ni(t) = 0 if the ith server is in an unavailable state at time t and ni(t) = 1, otherwise If a blocked period has an exponential phase, i.e. where are independent random variables and has an exponential distribution with a parameter αi, then we may define the sequence of regeneration points for the regenerative process as above. Therefore, condition 1.6 holds. Under condition 1.7, the auxiliary process Y is strongly regenerative and we can construct the common points of regeneration for X and Y and apply theorems 1.1 and 1.2 for this model. Since

we have from [1.11]

If bi = b, then we get the same stability condition as obtained in Morozov et al. (2011) for a queueing system GI|G|m with a common distribution function of service times for all servers.

COROLLARY 1.1.– For a queueing system with

if ρ > I.

Under condition 1.4, the process is stochastically bounded if ρ < 1.

PROOF.– Let, as before, be the number of customers actually served on the ith server up to time t. It is evident that stochastic inequality

for t > 0 takes place and hence

Since

To prove the second statement, we first assume that conditions 1.6 and 1.7 hold. Then condition 1.1 for the process Y takes place. We also may organize the performance of the systems S and S₀ in such a way that inequality [1.8] is realized when Thus, conditions 1.1, 1.4 and 1.5 are satisfied and because of theorem 1.2 the process Q is stochastically bounded.

If conditions 1.6 and 1.7 (or one of them) are not valid, we construct a system Sδ satisfying conditions 1.6 and 1.7 and majorising our system S, so that in distribution

[1.13]

Here, Qδ(t) is the number of customers in the system Sδ at instant t. Let us introduce independent sequences of iid random variables with exponential distribution with a rate δ. Assume that repair time in the system Sδ has the form and service time by the ith server has the form

Then Sδ satisfies conditions 1.6 and 1.7. Since and we may choose δ so that ρδ < 1.

The proof of [1.13] is based on the “so-called” probability space method (Belorusov 2012).

Let us note that condition 1.4 may be provided in various ways. For instance, assume that blocked (or available) period has an exponential phase and

[1.14]

Then Q is a regenerative process with points of regeneration that is a subsequence of the sequence such that and all servers are in the exponential phase of their blocked (or available) periods. Now condition 1.4 follows directly from theorem 1 in Afanasyeva and Tkachenko (2014). We also note that in this case Q is a stable process if ρ < 1. If only assumption [1.14] takes place with the help of the majorising system Sδ, we obtain the stochastic boundedness Q when ρ < 1. ■