Analysis of future event set algorithms for discrete event simulation
- 1 December 1981
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 24 (12), 801-812
- https://doi.org/10.1145/358800.358803
Abstract
New analytical and empirical results for the performance of future event set algorithms in discrete event simulation are presented. These results provide a clear insight to the factors affecting algorithm performance, permit evaluation of the hold model, and determine the best algorithm(s) to use. The analytical results include a classification of distributions for efficient insertion scanning of a linear structure. In addition, it is shown that when more than one distribution is present, there is generally an increase in the probability that new insertions will have smaller times than those in the future event set. Twelve algorithms, including most of those recently proposed, were empirically evaluated using primarily simulation models. Of the twelve tested, four performed well, three performed fairly, and five performed poorly.Keywords
This publication has 11 references indexed in Scilit:
- COMPARISON OF FUTURE EVENT SET ALGORITHMS FOR SIMULATIONS OF CLOSED QUEUEING SYSTEMSPublished by Elsevier BV ,1979
- A comparison of heaps and the TL structure for the simulation event setCommunications of the ACM, 1978
- Event manipulation for discrete simulations requiring large numbers of eventsCommunications of the ACM, 1978
- An efficient data structure for the simulation event setCommunications of the ACM, 1977
- Heaps applied to event driven mechanismsCommunications of the ACM, 1976
- Analysis of an algorithm for priority queue administrationBIT Numerical Mathematics, 1975
- Improved event-scanning mechanisms for discrete event simulationCommunications of the ACM, 1975
- A comparison of simulation event list algorithmsCommunications of the ACM, 1975
- A second survey of users' views of discrete simulation languages bySIMULATION, 1971
- A Time-Sharing Queue with a Finite Number of CustomersJournal of the ACM, 1969