Queueing Theory 1. Nikolaos Limnios

Queueing Theory 1

column block of non-zero matrix, hence the computation of matrix G is more efficient. The matrix is of the form

In what follows, we present a case of a single-server queueing model in discrete time, with interdependent interarrival and service times based on bivariate geometric distribution.

1.5. Interdependent interarrival and service times

Chao (1995) discussed the case of bivariate exponential distributions for joint interarrival and service times queues and showed the waiting time is monotonically decreasing in the dependency in increasing convex ordering sense. sun and Basu (1995) introduced a class of bivariate geometric distribution originally presented by Hawkes (1972). Omey and Minkova (2013) presented a bivariate geometric distribution, which we extend to the general matrix structure. In what follows, we consider the case where the service and the interarrival times are interdependent and represented by a bivariate geometric distribution as in Omey and Minkova (2013).

Omey and Minkova (2013) consider a bivariate geometric distribution described by two random variables X (with two possible states S1, S2) and F · S1 is success of type 1 and S₂ is success of type 2, and F is a failure. Let

where

be defined as

, then

It is straightforward to see that if r is fixed, then as p increases q decreases and vice versa. Hence, there is negative correlation between type 1 and type 2 successes in that case. Equally, if we say p is fixed, then q can be allowed to increase or decrease at the expense of r. These types of effects of interarrival and service times have not received much attention in queueing theory;

. This makes sense as an increase in S1 leads to a decrease in S2 and vice versa.

1.5.1. A discrete time queueing model with bivariate geometric distribution

If we study a single-server queue in discrete time, with success of type 1 signifying an arrival and type 2 a service completion if there is a customer in the system, and letting a failure represent no event. Then keeping in mind that the event of having both type 1 and type 2 successes at the same time is zero, then our DTMC is

The system is stable if p < q. Letting the number in the system at steady state be X and defining

with

, then we have

Letting

we end up with

Letting

, we have

and

REMARK 1.4.– The bivariate geometric distribution is the discrete analogue of the bivariate exponential distribution. From the result of the mean number in the system, it is clear that by holding q constant and varying r, this mean is monotonically decreasing in the dependency in increasing convex ordering sense as expected. It is conjectured that this is also transferrable to the mean waiting time.

Let W be the waiting time in the system, i.e. the time spent waiting in the queue, plus the service time. If we define

, then the waiting time distribution can be written as

1.5.2. Matrix equivalent model

Consider three square matrices D₀, D₁ and D₂, with

capturing the probability of transition from state i to state j, with k = 0, 1, 2 event occurring. The event 1 is type 1 success, event 2 is type 2 success and event 0 is no success of either type. We assume that the matrix D = D₀ + D₁ + D₂ is a stochastic matrix, which is irreducible. Further, we define π = πD, π1 = 1. Keeping in mind that the event of having both type 1 and type 2 successes at the same time is zero, then our DTMC is

If the DTMC is positive recurrent, which we assume it is, then we have

where

From the matrix-geometric theorem of Neuts (1981), we know that there is a matrix R, which is the minimal non-negative solution to the matrix quadratic equation

and because of the theorem and the special structure of the boundary of the DTMC we have

From this result, all the other performance measures such as the waiting time and busy period can be obtained.

1.6. Conclusion

In this chapter, we have introduced some queueing models that incorporate some form of interdependence between interarrival times and service times. We mainly considered the case where the interarrival times depend on the service times, before extending the idea to the interdependence of both. We show that the standard matrix-analytic methods can be used for analyzing such queues. Still there is a considerable amount of work to be done in the exact representations of the interdependencies when it comes to the phase type-based models. That will be the focus of future work on this subject.

1.7. Acknowledgements

The author thanks the reviewer for useful comments that have assisted in improving the presentation of the work. The author’s research is supported in part by the NRF (South Africa) SARChI ASN Chair programme.

1.8. References

Alfa, A.S. (2004). Markov chain representations of discrete time distributions applied to

Скачать книгу