IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v44y1998i12-part-1p1709-1722.html
   My bibliography  Save this article

Limit Theory for Performance Modeling of Future Event Set Algorithms

Author

Listed:
  • 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)

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.

Suggested Citation

  • Halim Damerdji & Peter W. Glynn, 1998. "Limit Theory for Performance Modeling of Future Event Set Algorithms," Management Science, INFORMS, vol. 44(12-Part-1), pages 1709-1722, December.
    • Handle: RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1709-1722
    DOI: 10.1287/mnsc.44.12.1709
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.44.12.1709
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.44.12.1709?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Karl Sigman, 1990. "One-Dependent Regenerative Processes and Queues in Continuous Time," Mathematics of Operations Research, INFORMS, vol. 15(1), pages 175-189, February.
    2. Richard Engelbrecht-Wiggans & William L. Maxwell, 1978. "Analysis of the Time Indexed List Procedure for Synchronization of Discrete Event Simulations," Management Science, INFORMS, vol. 24(13), pages 1417-1427, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Alsmeyer, Gerold, 1996. "Superposed continuous renewal processes A Markov renewal approach," Stochastic Processes and their Applications, Elsevier, vol. 61(2), pages 311-322, February.
    2. Nieuwenhuis, G., 1996. "Ergodicity Conditions and Cesaro Limit Results for Marked Point Processes," Research Memorandum 736, Tilburg University, School of Economics and Management.
    3. Evsey Morozov & Vladimir Rykov, 2023. "On the Positive Recurrence of Finite Regenerative Stochastic Models," Mathematics, MDPI, vol. 11(23), pages 1-11, November.
    4. Nieuwenhuis, G., 1996. "Ergodicity Conditions and Cesaro Limit Results for Marked Point Processes," Other publications TiSEM e9963ce3-420e-49b5-88cc-9, Tilburg University, School of Economics and Management.
    5. Bardhan, Indrajit & Sigman, Karl, 1995. "Stationary regimes for inventory processes," Stochastic Processes and their Applications, Elsevier, vol. 56(1), pages 77-86, March.
    6. Irina Peshkova & Evsey Morozov & Michele Pagano, 2024. "Regenerative Analysis and Approximation of Queueing Systems with Superposed Input Processes," Mathematics, MDPI, vol. 12(14), pages 1-22, July.
    7. Bazsa-Oldenkamp, E.M. & den Iseger, P., 2003. "A two level decentralized distribution system with compound renewal demand," Econometric Institute Research Papers EI 2002-45, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. Konstantin Avrachenkov & Evsey Morozov, 2014. "Stability analysis of GI/GI/c/K retrial queue with constant retrial rate," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 79(3), pages 273-291, June.
    9. Bazsa-Oldenkamp, E.M. & den Iseger, P., 2002. "A two level decentralized distribution system with compound renewal demand," Econometric Institute Research Papers EI 2002-45, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Bazsa-Oldenkamp, E.M. & den Iseger, P., 2003. "Wide sense one-dependent processes with embedded Harris chains and their applications in inventory management," Econometric Institute Research Papers EI 2002-44, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    11. Peter Glynn & Yanlin Qu, 2023. "On a New Characterization of Harris Recurrence for Markov Chains and Processes," Mathematics, MDPI, vol. 11(9), pages 1-7, May.
    12. Xiaowei Zhang & Peter W. Glynn, 2018. "Affine Jump-Diffusions: Stochastic Stability and Limit Theorems," Papers 1811.00122, arXiv.org.
    13. Glynn, Peter & Sigman, Karl, 1998. "Independent sampling of a stochastic process," Stochastic Processes and their Applications, Elsevier, vol. 74(2), pages 151-164, June.
    14. E. Morozov & B. Steyaert, 2013. "Stability analysis of a two-station cascade queueing network," Annals of Operations Research, Springer, vol. 202(1), pages 135-160, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:44:y:1998:i:12-part-1:p:1709-1722. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.