Package jline.api.qsys

Class Qsys_mm1_tandem_lindley

java.lang.Object
jline.api.qsys.Qsys_mm1_tandem_lindley
public final class Qsys_mm1_tandem_lindley extends Object
Conditional downstream waiting time in an M/M/1 tandem.

The conditional mean waiting time of customer n+1 at the downstream station of a two-station single-server tandem queue, given that customer n waited Wk upstream and Wk1 downstream.

The point of the tandem recursion is that the interarrival time at the downstream station is the interdeparture time upstream, not an independent draw. With A ~ Exp(lambda) the interarrival time upstream and S1, S1' the service times upstream of customers n and n+1, that interdeparture time is 

   D = max(A - Wk - S1, 0) + S1',

an idle period followed by the next service, and the downstream Lindley step is W2_{n+1} = (Wk1 + S2 - D)^+ with S2 ~ Exp(mu2) independent of D.

Because A is exponential, max(A - Wk - S1, 0) is zero with probability 1-q and Exp(lambda) with probability q = e^{-lambda Wk} mu1/(lambda+mu1), the probability the upstream server goes idle, so D is either Exp(mu1) or the sum of Exp(mu1) and Exp(lambda). Averaging the downstream step over both cases needs only two elementary transforms of 

   g(d) = E[(Wk1 + S2 - d)^+] = Wk1 - d + 1/mu2      for d <= Wk1,
                              = e^{-mu2 (d-Wk1)}/mu2  for d > Wk1,

namely J(c) = int_0^inf e^{-cu} g(u) du and Jw(c) = int_0^inf u e^{-cu} g(u) du, both closed form, giving 

   E[W2_{n+1} | Wk, Wk1] = (1-q) mu1 J(mu1) + q C,
   C = lambda mu1 (J(mu1) - J(lambda))/(lambda-mu1)  if lambda != mu1,
     = mu1^2 Jw(mu1)                                 if lambda == mu1.

As Wk grows the upstream server never idles, q vanishes, and the mean tends to mu1 J(mu1) = E[g(S1')], as it must.

Two caveats, both inherited from the reference and both quantified here.

First, this is exact for the step taken in isolation, that is when the conditioning pair is independent of the four primitives that drive the step. In a running tandem it is not: the downstream wait Wk1 was itself determined by an interdeparture time containing S1, so conditioning on (Wk, Wk1) is not conditioning on a Markov state of the tandem. Measured against a 4e6-customer simulation of the real tandem at lambda = 0.8, mu1 = mu2 = 1, the formula is within 0.4% to 1.3% away from the empty state and 7% at Wk = Wk1 = 0, where the entanglement is strongest. Treat it as exact for one isolated step and as a good approximation in a running tandem.

Second, this closed form was derived rather than transcribed from the reference's theorem 4, because that theorem rests on its proposition 1, which omits a service-time difference and so does not describe a tandem queue; see Qsys_tandem_lindley. The two differ: at lambda = 0.8, mu1 = mu2 = 1 and Wk = Wk1 = 0 the published route gives 0.3016 against 0.3457 here, the latter matching simulation of the step to 6e-4 relative error.

As in the reference, the upstream interarrival time is taken to be Exp(lambda), which by Burke's theorem is also the stationary interdeparture law, so the same formula is applied at any pair of consecutive stations of a longer M/M/1 tandem, with the caveat above compounding.

Port of MATLAB qsys_mm1_tandem_lindley.m.

Reference: S. Palomo, J. Pender, "Learning the Tandem Network Lindley Recursion", Proc. Winter Simulation Conference, 2021, proposition 1 and theorem 4, corrected as described above.

Since:
LINE 3.1.0

  • Method Details

    • qsys_mm1_tandem_lindley

      public static QsysTandemLindleyResult qsys_mm1_tandem_lindley(double lambda, double mu1, double mu2, double Wk, double Wk1)
      Conditional downstream mean at a single pair of current waiting times.
      Parameters:
      lambda - external arrival rate upstream, positive
      mu1 - upstream service rate, positive
      mu2 - downstream service rate, positive
      Wk - current upstream waiting time, finite and nonnegative
      Wk1 - current downstream waiting time, finite and nonnegative
      Returns:
      the conditional means

    • qsys_mm1_tandem_lindley

      public static QsysTandemLindleyResult qsys_mm1_tandem_lindley(double lambda, double mu1, double mu2, double[] Wk, double[] Wk1)
      Conditional downstream mean at several pairs of current waiting times.
      Parameters:
      lambda - external arrival rate upstream, positive
      mu1 - upstream service rate, positive
      mu2 - downstream service rate, positive
      Wk - current upstream waiting times, finite and nonnegative
      Wk1 - current downstream waiting times, same length as Wk
      Returns:
      the conditional means