Abstract
An approach has been developed for making use of the repeated structure of Q to construct fast algorithms for the solution of the queueing system and
in Part I of this paper. We apply this approach to develop fast algorithms for solving some complex queueing problems in this second part of the paper. Based on the approach, we develop fast algorithms for solving the stationary distributions of the multi-class MMPP/M/1/L queue (preemptive LCFS, non-preemptive LCFS, and FCFS) and the 2 class priority queue. When we compare these fast algorithms with those developed by the conventional approach, we find that the operation count is reduced by several degrees of order. For example, the time complexity of the elimination process for the d-class MMPP/M/1/L LCFS preemptive queue is
where m is the number of states in the arrival process. By contrast, sparse block Gaussian elimination requires a time complexity of
. However, it is not always true that the new approach gives the algorithm with the minimum operation count. The difference in the performance of algorithms based on different approaches are discussed by means of examples of the MMPP/M/1/L system with bursty arrivals and examples of the 2-class priority system.
1The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E. Please send all correspondence to this author
1The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E. Please send all correspondence to this author
Notes
1The work of this author was supported in part by the Research Grant Council of Hong Kong under Earmarked Grant CUHK 271/94E. Please send all correspondence to this author