Package jline.api.qsys

Class Qsys_tandem_lindley

java.lang.Object
jline.api.qsys.Qsys_tandem_lindley
public final class Qsys_tandem_lindley extends Object
Tandem network Lindley recursion on a sample path.

Propagates the waiting times of a series of K single-server FCFS stations in tandem, driven by the primitives of the sample path: the interarrival times at the first station and the per-station service times.

At the first station this is Lindley's recursion, W(n+1,1) = max(W(n,1) + S(n,1) - A(n), 0). Downstream the interarrival time is not a primitive: the arrival epoch of customer n at station k is its departure epoch from station k-1, so the interarrival time at station k is the interdeparture time upstream. Writing G(n,k) for the interarrival time at station k between customers n and n+1, with G(n,1) = A(n), the exact interdeparture identity is 

   G(n,k+1) = G(n,k) + W(n+1,k) - W(n,k) + S(n+1,k) - S(n,k),

equivalently and more transparently 

   G(n,k+1) = max(G(n,k) - W(n,k) - S(n,k), 0) + S(n+1,k),

an idle period at station k followed by the next customer's service there. The recursion at station k is then W(n+1,k) = max(W(n,k) + S(n,k) - G(n,k), 0).

Nothing here is distributional, so the recursion is exact for arbitrary interarrival and service times, dependent or not, and is the reference a simulated tandem sample path can be checked against directly. It reproduces a direct event-driven tandem simulation to 1e-12 over four stations.

Note that proposition 1 of the reference states this identity without the S(n+1,k) - S(n,k) term, which makes it wrong as a sample-path identity: the omitted difference has mean zero, so the mean interdeparture time survives, but individual waiting times do not. Implementing it as published gives station-1 waiting times that are correct and downstream ones that are not, by up to several mean service times. The form above is used instead.

Port of MATLAB qsys_tandem_lindley.m.

Reference: S. Palomo, J. Pender, "Learning the Tandem Network Lindley Recursion", Proc. Winter Simulation Conference, 2021, equations 2 and 3 and proposition 1, the last corrected as described above; D. V. Lindley, "The Theory of Queues with a Single Server", Proc. Camb. Phil. Soc. 48, 1952.

Since:
LINE 3.1.0

  • Method Details

    • qsys_tandem_lindley

      public static QsysTandemPathResult qsys_tandem_lindley(double[] A, double[][] S)
      Propagates the waiting times from an empty network.
      Parameters:
      A - interarrival times at the first station, A[n] separating customers n and n+1
      S - service times, S[n][k] for customer n at station k
      Returns:
      the waiting times and derived epochs

    • qsys_tandem_lindley

      public static QsysTandemPathResult qsys_tandem_lindley(double[] A, double[][] S, double[] W0)
      Propagates the waiting times from a given initial state.
      Parameters:
      A - interarrival times at the first station
      S - service times, S[n][k] for customer n at station k
      W0 - waiting times of customer 1 at each station, null for an empty network
      Returns:
      the waiting times and derived epochs