The Waiting Time Distribution of a Type k Customer in a Discrete-Time MMAP[K]/PH[K]/c (c = 1, 2) Queue Using QBDs

Abstract

This paper presents an improved method to calculate the delay distribution of a type k customer in a first-come-first-serve (FCFS) discrete-time queueing system with multiple types of customers, where each type has different service requirements, and c servers, with c = 1, 2 (the MMAP[K]/PH[K]/c queue). The first algorithms to compute this delay distribution, using the GI/M/1 paradigm, were presented by Van Houdt and Blondia [Van Houdt, B.; Blondia, C. The delay distribution of a type k customer in a first come first served MMAP[K]/PH[K]/1 queue. J. Appl. Probab. 2002, 39 (1), 213–222; The waiting time distribution of a type k customer in a FCFS MMAP[K]/PH[K]/2 queue. Technical Report; 2002]. The two most limiting properties of these algorithms are: (i) the computation of the rate matrix R related to the GI/M/1 type Markov chain, (ii) the amount of memory needed to store the transition matrices A _l and B _l . In this paper we demonstrate that each of the three GI/M/1 type Markov chains used to develop the algorithms in the above articles can be reduced to a QBD with a block size which is only marginally larger than that of its corresponding GI/M/1 type Markov chain. As a result, the two major limiting factors of each of these algorithms are drastically reduced to computing the G matrix of the QBD and storing the 6 matrices that characterize the QBD. Moreover, these algorithms are easier to implement, especially for the system with c = 2 servers. We also include some numerical examples that further demonstrate the reduction in computational resources.

Key Words:

• Queueing theory
• Waiting time
• Multiple customer types
• FCFS
• QBD

Acknowledgments

Notes

^#B. Van Houdt is a postdoctoral Fellow of the FWO Flanders.

^aHere, the delay is defined as the waiting time plus the service time. One can obtain the waiting time distribution from d _k by means of a deconvolution, as the service time is independent from the waiting time.

^bNotice, we do not know which customer occupies which server. We can easily add this information to the MC by stating that the type k _i customer occupies server i. However, this would imply that the condition k ₁ ≥ k ₂ is lost, hence, the number of states that are part of each level increases (up to a factor 2). Adding this additional info would however simplify the description of the transition probabilities.

^cOf course, both systems, have a different R matrix.