The Library
Perfect simulation of M/G/c queues
Tools
Connor, Stephen B. and Kendall, W. S. (2015) Perfect simulation of M/G/c queues. Advances in Applied Probability, 47 (4). pp. 1039-1063. doi:10.1239/aap/1449859799 ISSN 0001-8678.
An open access version can be found in:
Official URL: http://dx.doi.org/10.1239/aap/1449859799
Abstract
In this paper we describe a perfect simulation algorithm for the stable M/G/c queue. Sigman (2011: Exact Simulation of the Stationary Distribution of the FIFO M/G/c Queue. Journal of Applied Probability, 48A, 209--213) showed how to build a dominated CFTP algorithm for perfect simulation of the super-stable M/G/c queue operating under First Come First Served discipline, with dominating process provided by the corresponding M/G/1 queue (using Wolff's sample path monotonicity, which applies when service durations are coupled in order of initiation of service), and exploiting the fact that the workload process for the M/G/1 queue remains the same under different queueing disciplines, in particular under the Processor Sharing discipline, for which a dynamic reversibility property holds. We generalize Sigman's construction to the stable case by comparing the M/G/c queue to a copy run under Random Assignment. This allows us to produce a naive perfect simulation algorithm based on running the dominating process back to the time it first empties. We also construct a more efficient algorithm that uses sandwiching by lower and upper processes constructed as coupled M/G/c queues started respectively from the empty state and the state of the M/G/c queue under Random Assignment. A careful analysis shows that appropriate ordering relationships can still be maintained, so long as service durations continue to be coupled in order of initiation of service. We summarize statistical checks of simulation output, and demonstrate that the mean run-time is finite so long as the second moment of the service duration distribution is finite.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||||
Library of Congress Subject Headings (LCSH): | Monte Carlo method, Queuing theory, Markov processes | ||||||||
Journal or Publication Title: | Advances in Applied Probability | ||||||||
Publisher: | Applied Probability Trust | ||||||||
ISSN: | 0001-8678 | ||||||||
Official Date: | 31 December 2015 | ||||||||
Dates: |
|
||||||||
Volume: | 47 | ||||||||
Number: | 4 | ||||||||
Page Range: | pp. 1039-1063 | ||||||||
DOI: | 10.1239/aap/1449859799 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | EP/J009180 (EPSRC), EP/K013939 (EPSRC) | ||||||||
Related URLs: | |||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |