ABSTRACT
This paper presents two methods to calculate the response time distribution of impatient customers in a discrete-time queue with Markovian arrivals and phase-type services, in which the customers’ patience is generally distributed (i.e., the D-MAP/PH/1 queue). The first approach uses a GI/M/1 type Markov chain and may be regarded as a generalization of the procedure presented in Van HoudtCitation [14] for the D-MAP/PH/1 queue, where every customer has the same amount of patience. The key construction in order to obtain the response time distribution is to set up a Markov chain based on the age of the customer being served, together with the state of the D-MAP process immediately after the arrival of this customer. As a by-product, we can also easily obtain the queue length distribution from the steady state of this Markov chain.
We consider three different situations: (i) customers leave the system due to impatience regardless of whether they are being served or not, possibly wasting some service capacity, (ii) a customer is only allowed to enter the server if he is able to complete his service before reaching his critical age and (iii) customers become patient as soon as they are allowed to enter the server. In the second part of the paper, we reduce the GI/M/1 type Markov chain to a Quasi-Birth-Death (QBD) process. As a result, the time needed, in general, to calculate the response time distribution is reduced significantly, while only a relatively small amount of additional memory is needed in comparison with the GI/M/1 approach. We also include some numerical examples in which we apply the procedures being discussed.
Mathematics Subject Classification:
Notes
Such customers can easily be taken into account by modifying the characteristics of the arrival process.
When the next customer arrival occurs at time n − i + 1, the MC remains at the same level. In this case we define the subexpression (…) equal to one.
Due to the definition of the levels of the MC, the age of this customer equals i time units.
Recall, a customer who reaches his critical age on the exact moment that the server becomes available, leaves the system nevertheless.
Actually, for i − k = 0 we split the transition into k steps instead of k + 1.
If i − k = 0, we have only k transitions, the kth one going from artificial state j k at level one to state j k+1 at level zero.
The QBD is in an original state of level one at time n.