This paper is concerned with the systematic design of efficient Jacobi and Gauss-Seidel relaxations, and their over-relaxed variants, for the computation of the stationary distributions of continuous-time Markov processes. An important factor in the design of Gauss-Seidel relaxations is the order in which the states of the Markov process is scanned in each iteration; proper designs outperform other relaxations many times over. The analysis shows that in essence each relaxation evolves identically in law with an explicitly identified discrete-time Markov chain, and its convergence rate is given by the ergodic coefficient of the chain. The ergodic coefficient is in turn determined by the connectivity of the graph of a random walk, which is considerably influenced by the ordering selected. Woven into the general theory is the specific analysis of a tandem connection of several machines with finite buffers in which each machine is subject to blocking. Examples of orderings for this system and their salient, comparative properties are given. The authors report on extensive numerical investigations on various relaxations. The largest system solved has over a million states. The authors delineate an important class of large problems, which they call ‘rapidly converging,’ which are tractable by relaxations in the sense that the time constant of the relaxations is 0(logℝSℝ) as ℝSℝ⇒•, where ℝSℝ is the number of states in Markov process. The authors give evidence that one of the Gauss-Seidel relaxations for the production line with many machines is rapidly converging.
