Aggregation/Disaggregation Methods for Computing the Stationary Distribution of Markov Chains with Application to Multiprogramming System
Saudi Arabia · 1994
ABSTRACf. This paper studies the aggregation/disaggregation of nearly completely decomposable Markov chains that have many applications in queueing networks and packet switched networks. A general class of simi larity transformation that transforms the stochastic transition probability matrix into a reduced order aggregated matrix is presented. This transfor mation is used to develop an aggregation algorithm to compute the exact stationary probability distribution, as weB as O( e k ) approximation of it. The proposed aggregation method is applied to a multiprogramming computer system with six active terminals and the capacity of the CPU and the secon dary memory is 3. This example is used to compare our algorithm with three well-known algorithms. The simulation studies showed that our algorithm usually converges in less number of iterations and CPU time. Moreover, it is shown that the other algorithms do not converge in some cases while our algorithm usually converges.