Perfect and nearly perfect sampling of work-conserving queues

In this paper, we explore algorithms for perfect and nearly perfect sampling from the stationary distribution of the waiting times in various Poisson arrival multi-class and multi-server queues with non-preemptive work-conserving service disciplines. The service duration distributions of these class...

Full description

Saved in:
Bibliographic Details
Published in:Queueing systems 2015-07, Vol.80 (3), p.197-222
Main Authors: Xiong, Yaofei, Murdoch, Duncan J., Stanford, David A.
Format: Article
Language:English
Subjects:
Algorithms
Arrivals
Business and Management
Computer Communication Networks
Computer simulation
Construction
Control
Customer services
Joining
Operations Research/Decision Theory
Probability Theory and Stochastic Processes
Queues
Queuing
Sampling
Sampling techniques
Servers
Simulation
Studies
Supply Chain Management
Systems Theory
Texts
Workloads
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we explore algorithms for perfect and nearly perfect sampling from the stationary distribution of the waiting times in various Poisson arrival multi-class and multi-server queues with non-preemptive work-conserving service disciplines. The service duration distributions of these classes may be identical or may vary from class to class. The algorithms follow the idea of dominated coupling from the past (Kendall, Adv Appl Probab 32:844–865 2000 ) and are variations on an algorithm of Sigman (J Appl Prob 48A:37–43, 2011 ). A coupled first come first serve queue is constructed for each work-conserving queue. When the service duration distributions do not vary, we achieve perfect simulation by finding times when the system is known to be totally idle. When the distributions differ, the totally idle times may be impossible to determine exactly, but we can achieve simulations with a specified error limit ϵ > 0 .
ISSN:0257-0130
1572-9443
DOI:10.1007/s11134-015-9437-y