An Optimal Termination Testing Procedure for Discrete Event Simulations

In this paper the authors consider discrete-event simulations which yield results until a termination condition is satisfied. The simulation can proceed beyond this time, but no useful information is generated. The time at which the termination condition will be satisfied is not known initially, and is taken to be randomly distributed with some prescribed density. It is necessary, therefore, to periodically check the termination condition, and this consumes CPU time. The question that is addressed in this paper is how to distribute checking time to minimize expected CPU expenditure. The authors do this by taking a limit in which the cost of checking is small, and then minimizing the limiting expected CPU expenditure. In general, uniformly distributed checking times are not optimal. The layouts of checking times which are generated by the minimization procedure can significantly outperform constant checking intervals.