Computational Markovian analysis of large systems

摘要

Purpose - Markov chains and queuing theory are widely used analysis, optimization and decision-making tools in many areas of science and engineering. Real life systems could be modelled and analysed for their steady-state and time-dependent behaviour. Performance measures such as blocking probability of a system can be calculated by computing the probability distributions. A major hurdle in the applicability of these tools to complex large problems is the curse of dimensionality problem because models for even trivial real life systems comprise millions of states and hence require large computational resources. This paper describes the various computational dimensions in Markov chains modelling and briefly reports on the author's experiences and developed techniques to combat the curse of dimensionality problem. Design/methodology/approach - The paper formulates the Markovian modelling problem mathematically and shows, using case studies, that it poses both storage and computational time challenges when applied to the analysis of large complex systems. Findings - The paper demonstrates using intelligent storage techniques, and concurrent and parallel computing methods that it is possible to solve very large systems on a single or multiple computers. Originality/value - The paper has developed an interesting case study to motivate the reader and have computed and visualised data for steady-state analysis of the system performance for a set of seven scenarios. The developed methods reviewed in this paper allow efficient solution of very large Markov chains. Contemporary methods for the solution of Markov chains cannot solve Markov models of the sizes considered in this paper using similar computing machines.