qsys_mmk_qed.h File Reference

Halfin-Whitt QED approximation for the M/M/s queue, and the square-root staffing rule that inverts it. More...

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

Include dependency graph for qsys_mmk_qed.h:

Go to the source code of this file.

Classes
struct	line::qsys::QsysQedResult< T >
	QED measures of the M/M/s queue. More...
struct	line::qsys::QsysQedStaffingResult< T >
	Outcome of the square-root staffing rule. More...

Namespaces
namespace	line
namespace	line::qsys

Enumerations
enum class	line::qsys::QedCriterion { line::qsys::Delay , line::qsys::MeanWait , line::qsys::ServiceLevel }
	Which target the staffing rule is asked to meet. More...

Functions
template<class T>
T	line::qsys::qsys_mmk_qed_alpha (const T &beta)
	The Halfin-Whitt delay-probability function alpha(beta); 1 at beta <= 0.
template<class T>
T	line::qsys::qsys_mmk_qed_erlangc (unsigned s, const T &lambda, const T &mu)
	Erlang C by the Erlang B recursion B_j = a B_{j-1}/(j + a B_{j-1}), which never forms a^j/j!
template<class T>
QsysQedResult< T >	line::qsys::qsys_mmk_qed (const T &lambda, const T &mu, unsigned s)
	Halfin-Whitt QED approximation for the M/M/s queue, and the square-root staffing rule that inverts it.
template<class T>
QsysQedStaffingResult< T >	line::qsys::qsys_mmk_qed_staffing (const T &lambda, const T &mu, const T &target, QedCriterion crit=QedCriterion::Delay, const T &deadline=num_traits< T >::from_int(0), const T &level=num_traits< T >::from_int(0), bool exact=false)
	Square-root staffing of the M/M/s queue.

Detailed Description

Halfin-Whitt QED approximation for the M/M/s queue, and the square-root staffing rule that inverts it.

Templated port of matlab/src/api/qsys/qsys_mmk_qed.m, qsys_mmk_qed_alpha.m and qsys_mmk_qed_staffing.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_mmk_qed.java.

Let s grow with the offered load a = lambda/mu so that the SERVER SLACK stays of order sqrt(s), i.e. beta = (1-rho) sqrt(s) = (s-a)/sqrt(s) is held fixed. The delay probability then has the non-degenerate limit

alpha(beta) = [ 1 + beta Phi(beta)/phi(beta) ]^(-1)

with phi and Phi the standard normal density and cdf. Servers are busy a fraction 1 - beta/sqrt(s) of the time, so efficiency tends to 1, and yet the delay probability tends to a constant strictly between 0 and 1, so quality does not collapse. Staffing inverts that: s = ceil(a + beta sqrt(a)).

ARITHMETIC. erfc and exp put this in the transcendental family; the staffing search is a bisection against a tolerance, so there is nothing exact to preserve.

NUMERICS. alpha is evaluated as phi/(phi + beta Phi) rather than as the reciprocal of 1 + beta Phi/phi: the two agree, but the quotient overflows once phi underflows (beta beyond about 38), whereas this form degrades to 0/(0+beta) = 0, which is the correct limit. The exact Erlang C used by the refinement goes through the Erlang B recursion for the same reason, a^j/j! being infinite well below the s these rules propose.

Reference: S. Halfin, W. Whitt (1981). Heavy-traffic limits for queues with many exponential servers. Operations Research 29(3), 567-588.

Definition in file qsys_mmk_qed.h.