qsys_ggnm_diffusion.h File Reference

Diffusion approximation for the G/GI/n/m queue. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <functional>
#include <limits>
#include "line/api/qsys/qsys_types.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for qsys_ggnm_diffusion.h:

Go to the source code of this file.

Classes
struct	line::qsys::QsysGgnmResult< T >
	Steady-state measures of the G/GI/n/m diffusion approximation. More...

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
QsysGgnmResult< T >	line::qsys::qsys_ggnm_diffusion (const T &lambda, const T &mu, unsigned n, double m, const T &ca, const T &cs, const std::function< T(const T &)> &serviceCcdf=std::function< T(const T &)>(), double tol=1e-12, std::size_t panels=4000)
	Diffusion approximation for the G/GI/n/m queue.

Detailed Description

Diffusion approximation for the G/GI/n/m queue.

Templated port of matlab/src/api/qsys/qsys_ggnm_diffusion.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_ggnm_diffusion.java.

ONE DIFFUSION WITH TWO REGIONS. Below the staffing level the queue behaves like an infinite-server system, whose limit is NORMAL with variance-to-mean ratio the ASYMPTOTIC PEAKEDNESS

z = 1 + (ca^2 - 1) omega_G, omega_G = int G^c(x)^2 dx / int G^c(x) dx (1.6)-(1.7)

above it like a single-server queue, whose limit is EXPONENTIAL with variability v = (ca^2 + cs^2)/2 (3.7). The steady-state law is a normal piece spliced to an exponential piece and every measure is an integral of it (3.14):

P(delay) = [1 + b Phi(b)/(phi(b)(1 - e^{-beta gamma/v}))]^-1, b = beta/sqrt(z) P(block) = f(gamma) v / sqrt(n) (7.5)

with beta = sqrt(n)(1-rho) and gamma = m/sqrt(n).

WHAT z SAYS. The service law enters the delay probability ONLY through omega_G: 1 for deterministic service, 1/2 for exponential, falling toward 0 as service gets more variable. At ca^2 = 1 the delay probability does not depend on the service law at all (z = 1), the long-standing M/GI/n-by-M/M/n approximation; away from ca^2 = 1 it does, and this is how much.

At m = Inf this reduces to alpha(beta/sqrt(z)) with the Halfin-Whitt alpha, i.e. to qsys_mmk_qed when the service is exponential and ca^2 = 1.

ARITHMETIC. erfc, exp and a quadrature: transcendental only.

DIVERGENCE. The finite-waiting-room delay function is eq. (3.2) of the paper, whose printed form the available scan does not resolve. What is implemented is the unique form that (i) reduces to eq. (3.10) as gamma -> Inf and (ii) reproduces the exact M/M/n/m delay probability in the QED limit, which was checked numerically against the birth-death chain at n = 100, 400 and 1000.

Reference: W. Whitt (2004). A diffusion approximation for the G/GI/n/m queue. Operations Research 52(6), 922-941.

Definition in file qsys_ggnm_diffusion.h.