Analysis of future event set algorithms for discrete event simulation

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.

REFERENCES

• 1: I. Adiri , B. Avi-Itzhak, A Time-Sharing Queue with a Finite Number of Customers, Journal of the ACM (JACM), v.16 n.2, p.315-323, April 1969 [doi>10.1145/321510.321523]
• 2: Barlow, R.E., and Proschan, F. Mathematical Theory of Reliability. John Wiley and Sons, New York, 1969.
• 3: Barlow, R.E., and Proschan, F. Statistical Theory of Reliability and Life Testing: Probability Models. Holt, Rinehart and Winston, Inc., New York, 1975.
• 4: Biles, W.E. Computer simulation of material handling configurations in production systems. TIMS/ORSA Bulletin, 5, (May 1978) p. 289.
• 5: John Craig Comfort, A taxonomy and analysis of event set management algorithms for discrete event simulation, Proceedings of the 12th annual symposium on Simulation, p.115-146, March 14-16, 1979, Tampa, Florida, United States
• 6: Dahl, O., Myhrhaug, B., and Nygaard, K. Common Base Language. Publ. No. 5-22, Norwegian Computing Center, Oslo, Norway, Oct. 1970.
• 7: Davey, D., and Vaucher, J. Self-optimizing partition sequencing sets for discrete event simulation. INFOR 18, 1 (Feb. 1980) 21-41.
• 8: Emshoff, J.R., and Sisson, R.L. Design and Use of Computer Simulation Models. The MacMillan Co., New York, 1970.
• 9: Englebrecht-Wiggans, R., and Maxwell, W.L. Analysis of the time indexed list procedure for synchronization of discrete event simulations. Management Sci., 24, 13 (Sept. 1978) 1417-1427.
• 10: Fishman, G.S. Concepts and Methods in Discrete Event Digital Simulation. John Wiley and Sons, New York, 1973.
• 11: Franta, W.R., and Maly, K. An event scanning algorithm of nearly constant complexity. Tech. Rept. 75-18, Computer, Information, and Control Sciences Department, University of Minnesota, Minneapolis, MN, Nov. 1975.
• 12: W. R. Franta , Kurt Maly, An efficient data structure for the simulation event set, Communications of the ACM, v.20 n.8, p.596-602, Aug. 1977 [doi>10.1145/359763.359801]
• 13: W. R. Franta , Kurt Maly, A comparison of heaps and the TL structure for the simulation event set, Communications of the ACM, v.21 n.10, p.873-875, Oct. 1978 [doi>10.1145/359619.359637]
• 14: W. R Franta, The process view of simulation (Operating and programming systems series), North-Holland, 1977
• 15: Gaston H. Gonnet, Heaps applied to event driven mechanisms, Communications of the ACM, v.19 n.7, p.417-418, July 1976 [doi>10.1145/360248.360261]
• 16: Hardy, G.H., Littlewood, J.E., and Polya, G. Inequalities. 2nd Ed., University Press, Cambridge, 1964.
• 17: James O. Henriksen, An improved events list algorithm, Proceedings of the 9th conference on Winter simulation, p.546-557, December 05-07, 1977, Gaitersburg, MD
• 18: Frederick S. Hillier , Gerald J. Lieberman, Introduction to operations research, 4th ed., Holden-Day, Inc., San Francisco, CA, 1986
• 19: Jonassen, A., and Dahl, O.J. Analysis of an algorithm for priority queue administration. BIT 15, 4 (Dec. 1975) 409--422.
• 20: Kiviat, P.J., Villanueva, R., and Markowitz, H.M. Simscript 11.5 Programming Language. Edited by E.C. Russell, CACI, Inc., Arlington, Virginia, 1973.
• 21: Kleine, H. A second survey of user's views of discrete simulation languages. Simulation, 17, 2 (Aug. 1971) 89-94.
• 22: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 23: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 24: Laughlin, G.W. Reducing the run ratio of a multiprocessor software system simulator. Proc. 8th Ann, Simulation Syrup., Orlando, FL, 1975, 115-134.
• 25: Lavenberg, S.S., Moeller, T.L., and Welch, P.D. Control variates applied to the simulation of queueing models of computer systems. In Computer Pe(formance. Edited by K.M. Chandy and Martin Reiser, North-Holland, New York, 1977, 459-467.
• 26: Law, A.M. Statistical analysis of the output data from terminating simulations. Tech. Rept. No. 78-4, Department of Industrial Engineering, University of Wisconsin, Madison, WI, 1978.
• 27: William Michael Mccormack, Analysis of future event set algorithms for discrete event simulation, 1979
• 28: McCormack, W.M., and Sargent, R.G. Comparison of future event set algorithms for simulations of closed queueing systems. In Current Issues in Simulation. Edited by N.R. Adam, and A. Dogramaci, Acadelnic Press, New York, 1979.
• 29: Moore, C.G. Network models for large-scale time-sharing systems. Tech. Rept. No. 71-1, Department of Industrial Engineering, University of Michigan, Ann Arbor, MI, April, 1971.
• 30: Morse, P.M. Queues, Inventory and Maintenance. John Wiley and Sons, Inc., New York, 1958.
• 31: Parmelee, W. Personal communication, August 1978.
• 32: Porter, T., and Simon, I. Random insertion into a priority queue structure. IEEE Trans. Software Engineering, SE-1 3, (Sept. 1975) 292-298.
• 33: Pritsker, A.A.B. The GASP IV Simulation Language. John Wiley and Sons, New York, 1974.
• 34: A. Alan. B. Pritsker, Ongoing developments in GASP, Proceedings of the 76 Bicentennial conference on Winter simulation, p.81-83, December 06-08, 1976, Gaithersburg, MD
• 35: Russell, E.C. Simulating with Processes and Resources in Simscript 11.5 ( User's Manual). CACI, Arlington, Virginia, 1976.
• 36: Thomas J. Schriber, An introduction to simulation using GPSS/H, John Wiley & Sons, Inc., New York, NY, 1991
• 37: Taneri, D. The use of subcalendars in event driven simulations. Proc. Summer Simulation Conf., Washington, D.C., July 1976, 63-66.
• 38: Ernst G. Ulrich, Event manipulation for discrete simulations requiring large numbers of events, Communications of the ACM, v.21 n.9, p.777-785, Sept. 1978 [doi>10.1145/359588.359611]
• 39: Jean G. Vaucher , Pierre Duval, A comparison of simulation event list algorithms, Communications of the ACM, v.18 n.4, p.223-230, April 1975 [doi>10.1145/360715.360758]
• 40: Vaucher, J.G. On the distribution of event times for the notices in a simulation event list. 1NFOR 15, 2 (May 1977) 171-182.
• 41: Wyman, F.P. Simulation Modeling: A Guide to Using Simscript. John Wiley and Sons, New York, 1970.
• 42: F. Paul Wyman, Improved event-scanning mechanisms for discrete event simulation, Communications of the ACM, v.18 n.6, p.350-353, June 1975 [doi>10.1145/360825.360873]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Design, Performance

Keywords:
data structures, simulation event set, time flow mechanisms