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

Consider a single-server queue with service times distribution vector, given as s of M dimension and K independent interarrival times, from which a customer’s next interarrival is selected based on the service time experienced by customers. It is clear that the true interarrival times is Markovian Arrival Process (MAP), which is constructed from the K interarrival times and the probability vector ψ of dimension K that was created by mapping service distribution as shown in section 1.4.1. The PH representation of interarrival times has κ = k₁ + k₂ + ... + kK, where kj is the number of phases of the jth interarrival time. We let the service times be represented by an elapsed time PH distribution with representation (β, B) of order M. Also let b = 1 – B1.

At time n = 0, 1, 2, 3, ∙∙∙, let Xn be the number of customers in the system, Y_n the phase of arrival and J_n the phase of the ongoing service. The stochastic process {(Xn,Jn,Yn),n≥ 0} is a DTMC with transition matrix P given as

where

This Markov chain is a simple Quasi-Birth-Death (QBD), which can be analyzed using the matrix-analytical methods for discrete time queues (Neuts 1981; Alfa2016).

If this system is stable, which we will assume it is, then there is a unique probability vector for which we have

Further, we have and

It is known that for a stable system, there exists a matrix R, with spectral radius less than 1, which is the minimal non-negative solution of the matrix quadratic equation

The R matrix has a counterpart stochastic matrix G for a stable system, a minimal non-negative solution to the matrix quadratic equation

and there is a simple relationship between the two as follows

Given the matrix R, we can then use the matrix-geometric results of Neuts (1981) to obtain

after solving for the boundary equations as

This is then normalized by .

As one sees the matrix, R could be of huge dimension, so solving it using the well-known methods could still be time consuming. However, because of the structure presented by the matrix G, we could exploit it and then obtain R directly from G. Due to the structure of the matrix A₂, we see that the matrix G has only one 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.