Workload Process, Waiting Times, and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.

Key Words:

• Queueing systems
• M/G/1 type Markov chain
• Waiting times
• Sojourn times
• Workload
• Mean-drift method
• Matrix analytic methods
• Ergodicity
• Semi-Markov chain

Mathematics Subject Classification:

• Primary 60K25
• Secondary 60J10

Acknowledgments

The author would like to thank K-C Wang Foundation and Chinese Academy of Science for their support on this research project. The author would like to thank Dr. Blake for proofreading the paper. The author would also like to thank two anonymous referees for their valuable comments and suggestions. This research was partially supported by a NSERC research grant.