Package jline.api.qsys

Class Qsys_mmk_qed

java.lang.Object
jline.api.qsys.Qsys_mmk_qed
public final class Qsys_mmk_qed extends Object
Halfin-Whitt QED approximation for the M/M/s queue, and the square-root staffing rule that inverts it.

THE REGIME. 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. That is the point of the regime: 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.

Useful even though M/M/s is exactly solvable, because Erlang C needs a sum of s terms a^j/j! that overflows in double precision well before the thousands of servers a large contact centre or thread pool has.

Port of MATLAB qsys_mmk_qed.m, qsys_mmk_qed_alpha.m and qsys_mmk_qed_staffing.m.

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

Since:
LINE 3.1.0

  • Method Details

    • qsys_mmk_qed_alpha

      public static double qsys_mmk_qed_alpha(double beta)
      The Halfin-Whitt delay-probability function alpha(beta).

      Evaluated as phi/(phi + beta*Phi) rather than as the reciprocal of 1 + beta*Phi/phi: the two are the same function, but the quotient Phi/phi overflows once phi underflows (beta beyond about 38), whereas this form degrades to 0/(0+beta) = 0, the correct limit.

      Parameters:
      beta - the QED server-slack parameter
      Returns:
      alpha(beta), and 1 for a non-positive beta

    • qsys_mmk_qed

      public static Map<String,Double> qsys_mmk_qed(double lambda, double mu, int s)
      QED approximation for the M/M/s queue.
      Parameters:
      lambda - arrival rate
      mu - service rate of one server
      s - number of servers
      Returns:
      map with offeredLoad, trafficIntensity, beta, probDelay, meanWaitDelayed, meanWait, meanQueueLength, meanNumber and utilization; an overloaded model has probDelay 1 and infinite waits

    • qsys_mmk_qed_staffing

      public static Map<String,Double> qsys_mmk_qed_staffing(double lambda, double mu, double target)
      Square-root staffing for a delay-probability target.
      Parameters:
      lambda - arrival rate
      mu - service rate of one server
      target - the largest acceptable P(W > 0), in (0,1)
      Returns:
      map with numServers, beta, betaTarget, offeredLoad, probDelay and meanWait

    • qsys_mmk_qed_staffing

      public static Map<String,Double> qsys_mmk_qed_staffing(double lambda, double mu, double target, String criterion, double deadline, double level, boolean exact)
      Square-root staffing under one of the three criteria.

      Invert alpha(beta) = target for the server slack and staff s = ceil(a + beta sqrt(a)) with a = lambda/mu: the base a erlangs of work plus a cushion that grows only as the square root of the load.

      Parameters:
      lambda - arrival rate
      mu - service rate of one server
      target - the largest acceptable P(W > 0) for "delay", the largest acceptable E[W] for "meanwait", ignored for "servicelevel"
      criterion - "delay", "meanwait" or "servicelevel"
      deadline - the deadline of the service-level criterion
      level - the probability the deadline must be met with
      exact - walk s until the EXACT Erlang C measure meets the target
      Returns:
      map with numServers, beta, betaTarget, offeredLoad, probDelay, meanWait, exactUsed and, for "servicelevel", serviceLevel

    • qsys_mmk_qed_erlangc

      public static double qsys_mmk_qed_erlangc(int s, double lambda, double mu)
      Erlang C by the recursion B_j = a B_(j-1)/(j + a B_(j-1)) on the Erlang B blocking probability, which never forms a^j/j! and so never overflows. That matters here: this is called at the s the staffing rule proposes, routinely in the thousands, where the factorial form is already infinite.
      Parameters:
      s - number of servers
      lambda - arrival rate
      mu - service rate of one server
      Returns:
      the probability that an arrival is delayed