Analysis of the Time Indexed List Procedure for Synchronization of Discrete Event Simulations

Abstract

Increasingly simulations have been required as supportive evidence to management of proposed system changes. It has long been recognized that the computer running costs of simulations are strongly influenced by the synchronization mechanism used. Recently the time indexed list has been proposed as a superior alternative to existing event synchronization mechanisms for computer simulations. Intuition and empirical data indicate that such a mechanism should result in substantial savings of computer time; the mathematical results of this paper substantiate this. This paper undertakes a rigorous mathematical and probabilistic analysis of the mechanism. Several different probabilistic event arrival models and arbitrary event schedule time distributions are considered. Results for several specific cases are calculated. It is shown that the distribution is quite insensitive to the arrival process and is usually a simple integral of the interarrival time distribution. Next, the cost of scheduling new arrivals is calculated and shown to be approximately independent of the probabilistic details; the first order term depends only on the mean arrival rate. The robustness of these results, and the considerable savings in computer time realized, strongly recommend the time indexed list procedure.