Heavy-traffic limits for nearly deterministic queues


We establish heavy-traffic limits for "nearly deterministic" queues, such as the <i>G/D/n</i> many-server queue. Waiting times before starting service in the <i>G/D/n</i> queue are equivalent to waiting times in an associated <i>Gn/D/</i>1 model, where the <i>G<sub>n</sub></i> denotes "cyclic thinning" of order <i>n</i>, indicating that the original (possibly general) point process of arrivals is thinned to contain only every <i>n<sup>th</sup></i> point. We thus focus on the <i>Gn/D/</i>1 model and the generalization to <i>Gn/Gn/</i>1, where "cyclic thinning" is applied to both the arrival and service processes. As <i>n</i> ↓ ∞, the <i>Gn/Gn/</i>1 models approach the deterministic <i>D/D/</i>1 model. The classical example is the Erlang <i>En/En/</i>1 queue, where cyclic thinning of order <i>n</i> is applied to both the interarrival times and the service times, starting from a "base" <i>M/M/</i>1 model. We establish different limits in two cases: (i) when (1--ρ<i>n</i>)√<i>n</i> ↓ β as <i>n</i> ↓ ∞ and (ii) (1 -- ρ<i>n</i>)<i>n</i> √ as <i>n</i> ↓ ∞, where ρ<i>n</i> is the traffic intensity in model <i>n</i>, and 0 < β < ∞. The nearly deterministic feature leads to interesting nonstandard scaling. We also establish revealing heavy-traffic limits for the stationary waiting times and other performance measures in the <i>Gn/Gn/</i>1 queues, by letting ρ<i>n</i> ↑ 1 as <i>n</i>↓∞.


    2 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)