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.
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 1 ≥ k 2 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.