Numerical Solution of Piecewise-Stationary M t / G t /1 Queues

Gagan L. Choudhury, David M. Lucantoni and Ward Whitt
Additional contact information
Gagan L. Choudhury: AT&T Laboratories, Holmdel, New Jersey
David M. Lucantoni: Isoquantic Technologies, Wayside, New Jersey
Ward Whitt: AT&T Laboratories, Murray Hill, New Jersey

Operations Research, 1997, vol. 45, issue 3, 451-463

Abstract: We develop an algorithm for computing the (exact) cumulative distribution function of the time-dependent workload in a piecewise-stationary M t / G t /1 queue with a work-conserving service discipline and general service-time distributions, where service times are determined at arrival instants. The t subscripts indicate that the arrival rate and the general service-time distribution may change with time, but we allow changes only at finitely many time points. The algorithm is based on numerical transform inversion, using the classical Takács double-transform of the transient workload in an M / G /1 queue recursively over the successive stationary intervals. In particular, we apply our recently developed Fourier-series-based inversion algorithms for two-dimensional transforms and nested one-dimensional transforms. We also do additional work to greatly speed up the computation while tightly controlling the error. As a consequence, the computation time grows only quadratically with the number of intervals. The algorithm is effective for ten or fewer intervals, where the intervals may have unlimited and possibly unequal lengths, typically running in at most a few minutes and maintaining high accuracy. We have also demonstrated that the algorithm can solve a 21-interval example with 7-to-10-digit accuracy in about half an hour. Models with only a few intervals are useful to study overload control strategies.

Keywords: queues; nonstationary; numerical solution of single-server models; queues; algorithms; numerical transform inversion for nonstationary queues; queues; transient results; two-dimensional numerical transform inversion (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.3.451 (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:45:y:1997:i:3:p:451-463

Access Statistics for this article

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