A fast computational algorithm for simulating round-robin service

D Finley, J R Ramos, V Rego and J Sang

Journal of Simulation, 2009, vol. 3, issue 1, 29-39

Abstract: An efficient computation-based algorithm for effecting round-robin (RR) service in discrete-event simulation systems is presented. The new algorithm improves upon an older computational algorithm which itself is an improvement over naive RR scheduling currently in use in process-oriented simulation systems. The naive approach can be prohibitively expensive due to process context switch overhead. The original computational algorithm avoids much of this context switching but offers a run-time complexity of only O(n2), where n is the size of the job pool. This is because the processing of each arrival and departure event requires a traversal of the entire pool. In this paper, we propose an improved algorithm which reduces run-time complexity to O(n log n) by using tree-based data structures. The expected computation to process each arrival or departure event is proportional to O(log n). Empirical evidence suggests that, except for very small size of job pool, this algorithm is considerably faster than other methods.

Date: 2009
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1057/jos.2008.10 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjsmxx:v:3:y:2009:i:1:p:29-39

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjsm20

DOI: 10.1057/jos.2008.10

Access Statistics for this article

Journal of Simulation is currently edited by Christine Currie

More articles in Journal of Simulation from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().