An Algorithm to Compute the Waiting Time Distribution for the M/G/1 Queue

In many modern applications of queueing theory, the classical assumption of exponentially decaying service distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2004-03, Vol.16 (2), p.152-161
Main Authors: Shortle, John F, Brill, Percy H, Fischer, Martin J, Gross, Donald, Masi, Denise M. B
Format: Article
Language:English
Subjects:
Algorithms
Approximation
communications
Laplace transforms
queues
Queuing theory
Services
Studies
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 many modern applications of queueing theory, the classical assumption of exponentially decaying service distributions does not apply. In particular, Internet and insurance risk problems may involve heavy-tailed distributions. A difficulty with heavy-tailed distributions is that they may not have closed-form, analytic Laplace transforms. This makes numerical methods, which use the Laplace transform, challenging. In this paper, we develop a method for approximating Laplace transforms. Using the approximation, we give algorithms to compute the steady state probability distribution of the waiting time of an M/G/1 queue to a desired accuracy. We give several numerical examples, and we validate the approximation with known results where possible or with simulations otherwise. We also give convergence proofs for the methods.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1030.0045