Package jline.api.qsys

Class Qsys_mgck_sync

java.lang.Object
jline.api.qsys.Qsys_mgck_sync
public final class Qsys_mgck_sync extends Object
Synchronous approximation of the M/G/c/K queue with dual bounds (German, EPEW 2025).

Port of matlab/src/api/qsys/qsys_mgck_sync.m. The concurrent service clocks of the c servers are replaced by clocks that are synchronized, so that at most one non-Markovian activity is enabled at any time and the process is solved exactly by Markov renewal theory through its embedded Markov chain. Synchronizing is done so that every customer receives either its true service time or a shorter one (variant "faster") or a longer one ("slower"), which brackets the M/G/c/K measures: the faster model gives a lower bound on the mean number in system, on the response time and on P(full), and an upper bound on P(idle) and the throughput; the slower model gives the opposite bounds. The argument is customer-wise and holds without losses; with blocking the bounds are observed, not proven.

MODEL WITHOUT EXPANSION (nphases = 0), state i = jobs in system. All jobs in service share one clock. "faster": an arrival that finds a free server joins the running batch and completes with it. "slower": such an arrival preempts the clock, so the whole batch restarts with it. On expiry min(i,c) jobs depart and the next min(i-c,c) start together. For c = 1 both variants are the exact M/G/1/K queue.

MODEL WITH EXPANSION (nphases = N >= 1, deterministic service only), state (a, B, q): a = 1 when the owner is busy, B the multiset of phases completed by the other busy servers, q the waiting jobs. While the owner is busy, a tick of length d/N advances every phase and the owner completes after N ticks; a newcomer to another server starts at phase 0 ("faster", its first phase is partial) or -1 ("slower", it waits for the next tick). With the owner idle the ticks continue; an arrival takes the owner role and preempts the tick, the other phases being rounded up ("faster") or kept ("slower"). A job taking a server at a tick boundary starts exactly. An arrival to the empty system takes the owner role with probability 1/c.

Embedded chain (German 2000, cascaded embedding for the expansion): 

   P = I_E - diag^{-1}(Q_E) Q_E + Omega*Delta + Psi*Qbar
   C = -diag^{-1}(Q_E) + Psi,   pi = u*C/(u*C*e),  u = u*P
with Omega = I_G E[exp(Q_G S)] and Psi = I_G E[int_0^S exp(Q_G t) dt], both evaluated by uniformization of Q_G at rate lambda with the service-law coefficients of Qsys_mapg1k.

The "slower" expansion counts the jobs in phase -1 as in system. The reference notebooks leave those states out of the aggregation, which is why Table 1 of [1] reports R = 1.04482 at N = 10 for lambda = 0.5, where this function returns 1.05607 (both are upper bounds of the exact 1.0375).

References:
[1] R. German, On Synchronous Approximations of Non-Markovian Processes with Dual Bounds, EPEW 2025.
[2] R. German, Performance Analysis of Communication Systems with Non-Markovian Stochastic Petri Nets, Wiley, 2000.

  • Method Details

    • qsys_mgck_sync

      public static QsysMgckSyncResult qsys_mgck_sync(double lambda, int c, int K, QsysServiceLaw svc, String variant)
      Synchronous approximation without phase expansion, default tolerances.

    • qsys_mgck_sync

      public static QsysMgckSyncResult qsys_mgck_sync(double lambda, int c, int K, QsysServiceLaw svc, String variant, int nphases)
      Synchronous approximation with nphases phases (0 = no expansion), default tolerances.

    • qsys_mgck_sync

      public static QsysMgckSyncResult qsys_mgck_sync(double lambda, int c, int K, QsysServiceLaw svc, String variant, int nphases, double tol, int nmaxCap)
      Synchronous approximation of the M/G/c/K queue.
      Parameters:
      lambda - Poisson arrival rate (> 0)
      c - number of identical FCFS servers (>= 1)
      K - system capacity, jobs in service included (K >= c)
      svc - service law
      variant - "faster" (lower bounds on queue length) or "slower" (upper bounds)
      nphases - phases of the synchronous phase expansion; 0 solves without expansion, N >= 1 requires a deterministic service time
      tol - uniformization truncation tolerance of the service law
      nmaxCap - cap on the uniformization order
      Returns:
      the result