Limit Theory for Performance Modeling of Future Event Set Algorithms

Halim Damerdji and Peter W. Glynn
Additional contact information
Halim Damerdji: Department of Industrial Engineering, North Carolina State University, Raleigh, North Carolina 27695-7906
Peter W. Glynn: Department of Engineering-Economic Systems and Operations Research, Stanford University, Stanford, California 94305-4023

Management Science, 1998, vol. 44, issue 12-Part-1, 1709-1722

Abstract: In a discrete-event simulation, the information related to the events scheduled to occur in the future is kept in a data structure called the future event set (FES). In this paper, we study the interaction hold model, a popular stochastic model for FES performance analysis, corresponding to the superposition of a (fixed) number of renewal processes. The general state-space Markov chain formed by the discrete-time process that keeps track, at event times, of the residual lifetimes is shown here to be recurrent in the sense of Harris, and its stationary distribution is obtained. Linked lists and indexed lists, two popular FESs, are investigated using this model. For the interaction hold model, we make rigorous certain published results as well as introduce new ones. For example, we derive the distribution of the relative position of the event to be inserted in the data structure. In the exponential case, our analytic and empirical results confirm that when events with relatively short lifetimes often get regenerated upon their occurrence, it is better to scan a list (or sublist) from its head rather than tail. In the same context and for indexed lists with sublists with constant sizes, our results suggest that subsequent sublists should be of larger sizes, i.e., the first sublist should contain the smallest number of records, the second sublist the second smallest number of records, etc.

Keywords: Simulation; Future Event Set; Performance Evaluation; Linked List; Indexed List; Interaction Hold Model; Harris Chain (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.12.1709 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1709-1722

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().