Efficiency of Time Segmentation Parallel Simulation of Finite Markovian Queueing Networks

Sigrún Andradóttir () and Mehdi Hosseini-Nasab ()
Additional contact information
Sigrún Andradóttir: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Mehdi Hosseini-Nasab: AT&T Laboratories, 200 Laurel Avenue, D5-3D15, Middletown, New Jersey 07748

Operations Research, 2003, vol. 51, issue 2, 272-280

Abstract: We present an approach for using parallel processors to simulate long sample paths of Markovian queueing networks with finite buffers and both loss and blocking stations. Parallelism is achieved by distributing the available processors among segments of the time domain of the simulation. We conduct the simulation in such a way that all sample paths of the system will eventually couple (i.e., become identical), regardless of their starting states. This coupling property is exploited to generate valid sample paths of the system by combining the information collected on consecutive time segments of the simulation. The efficiency of our approach depends heavily on the magnitude of the coupling times of the sample paths. We study how the expected coupling times depend on the system parameters through a variety of theoretical and numerical results. Our main results give conditions under which the expected coupling times grow slowly (no faster than linearly) with respect to the number of stations and buffer capacities in the system. These results suggest that our time segmentation approach is likely to perform well on a substantial class of finite Markovian queueing networks.

Keywords: Simulation; efficiency: analysis of the time segmentation parallel simulation method; Queues; Markovian: analysis of the expected coupling time of all sample paths (search for similar items in EconPapers)
Date: 2003
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.2.272.12778 (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:oropre:v:51:y:2003:i:2:p:272-280

Access Statistics for this article

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