A comparison of simulation event list algorithms

TLDR

The study proposes that an adaptive routine is needed for general‑purpose simulators, yet the algorithm’s performance warrants further investigation. Four event‑scheduling algorithms were evaluated, including two novel methods—an end‑order tree and an indexed linear list—using stochastic distributions to assess their strengths and weaknesses. The end‑order tree algorithm proved to be an effective immediate replacement, while the indexed list approach emerged as the most promising.

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.