Construction of Markov chains for discrete time MAP/PH/K queues

Two GI/M/1 type Markov chains associated with the queue length are often used in analyzing the discrete time MAP/PH/K queue. The first Markov chain is introduced by tracking service phases for servers; a method we call TPFS. The transition probability matrix of the Markov chain can be constructed in a straightforward manner. The second Markov chain is introduced by counting servers for phases; which we call CSFP. An algorithm is developed for the construction of the transition probability matrix of the second Markov chain, which is the main contribution of this paper. Whereas the construction of the matrices for the case of continuous time is available in the literature, it is not available for the discrete time case. The effort in constructing the matrices for the discrete time case is extensively more involved than for the continuous time case. Some basic properties of the constructed transition blocks are shown. We demonstrate that for queueing systems with a large number of servers and many service phases, there is a considerable saving in the matrix sizes. For example, when those values are 30 and 2, respectively, the block size for TPFS is more than 3×107 times that of CSFP; a major saving.