A comparison of simulation event list algorithms

ABSTRACT

Four algorithms are considered which can be used to schedule events in a general purpose discrete simulation system. Two of the algorithms are new, one is based on an end-order tree structure for event notices, and another uses an indexed linear list. The algorithms are tested with a set of typical stochastic scheduling distributions especially chosen to show the advantages and limitations of the algorithms. The end-order tree algorithm is shown to be an advantageous, immediate replacement for the algorithm in use with current simulation languages. The most promising algorithm uses the indexed list concept. It will require an adaptive routine before it can be employed in general purpose simulators, but its performance is such that further study would be fruitful.

REFERENCES

• 1: Buxton, J.N. (Ed.) Simulation Programming Languages. North- Holland, Amsterdam, 1968.
• 2: Ole-Johan Dahl, SIMULA 67 common base language, (Norwegian Computing Center. Publication), 1968
• 3: Genuys, F. (Ed.) Programming Languages. Academic Press, New York, 1968, pp. 349-395.
• 4: Geoffrey Gordon, System Simulation, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 5: Kiviat, P.J., Villanueva, R., and Markowitz, H.H. The SIMSCRIPT I1 Programming Language. Prentice-Hall, Englewood Cliffs, N.J., 1968.
• 6: 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
• 7: Myhrhaug, B. Sequencing set efficiency. Pub. A9, Norwegian Computing Centre, Forskningsveien, 1B, Oslo 3.
• 8: Nance, R.W. On time flow mechanisms for discrete system simulation. Management Sci. 18 (Sept. 1971), 59-73.
• 9: Pritsker, A.A., and Kiviat, P.J. Simulation with GASP II. Prentice-Hall, Englewood Cliffs, N.J., 1969.
• 10: Stephen A. Szygenda , Cliff W. Hemming , John M. Hemphill, Time flow mechanisms for use in digital logic simulation, Proceedings of the 5th conference on Winter simulation, p.488-495, December 08-10, 1971, New York, NY [doi>10.1145/800294.811476]
• 11: Ernst G. Ulrich, Exclusive simulation of activity in digital networks, Communications of the ACM, v.12 n.2, p.102-110, Feb. 1969 [doi>10.1145/362848.362870]
• 12: Jean G. Vaucher, A “WAIT UNTIL” algorithm for general purpose simulation languages, Proceedings of the 6th conference on Winter simulation, p.77-83, January 17-19, 1973, San Francisco, CA [doi>10.1145/800293.811565]
• 13: Wirth, N. The programming language PASCAL. Acta lnformatica (Jan 1971).
• 14: General Purpose Simulation System 360--User's Manual Pub. H20-0326, IBM Corp., White Plain, N.Y., 1968.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

General Terms:
Algorithms, Design, Theory

Keywords:
discrete system simulation, event list algorithm, event scheduling routine, simulation, simulation executive, sorting, time flow mechanism