Complexity of simulation models: A graph theoretic approach

In this article, we introduce complexity measures for simulation models. The framework of simulation graphs sets the context. A quantifiable measure of complexity is useful in an a priori evaluation of proposed simulation studies that must be completed within a specified budget. They can also be useful in classifying simulation models to obtain a thorough test bed of models to be used in simulation methodology research. The metrics introduced in this article have a rigorous theoretical, as well as empirical, grounding in software engineering. As such, simulation modeling and analysis represent a new area of application. Some surrogate measures of run time complexity are also developed. In particular, we provide estimates for the size of the future events list (or the pending event set). The proposed metrics are illustrated and compared through a limited set of examples. Limitations of the current approach as well as directions for future research are discussed.