Queueing Theory 1. Nikolaos Limnios

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