Package jline.solvers.mam.handlers

Class Solver_mam_bgchain

java.lang.Object
jline.solvers.mam.handlers.Solver_mam_bgchain
public final class Solver_mam_bgchain extends Object
Mixed-network solver that treats the CLOSED classes as a background modulating chain and the OPEN classes as matrix-analytic queues driven by it.

The closed population vector of a mixed network is a finite continuous-time Markov chain in its own right: it is the only part of the model whose state space is bounded. This method solves it exactly (given the capacity the open work leaves free) and hands the open classes a station-local Markovian environment read off that chain, so each open station becomes a level-dependent QBD whose phase carries the number of closed jobs competing for its server. The two halves meet at a fixed point on the closed capacity share.

  1. background chain: the closed population vector over the stations the closed classes visit (Mam_bgchain_ctmc)
  2. environment: that chain lumped onto the closed occupancy of one station (Mam_bgchain_env)
  3. open station: a MAP/PH/c queue modulated by that environment, solved as a level-dependent QBD (Mam_bgchain_station)
  4. fixed point: the capacity share feeds step 1 and closes

Tagged-class iteration. Step 1 is a population process of dimension (closed chains) x (stations), so its state space is exponential in the number of closed chains. With R > 1 closed chains the method keeps ONE chain free at a time: the tagged chain r is carried exactly, the other R-1 are replaced by flow-equivalent aggregate classes whose population is their total and whose service time and routing at each station are their throughput-weighted means (Chandy-Herzog-Woo aggregation). Every chain takes its turn as the tagged one and reads its own metrics off the chain it is exact in; the open-class results are averaged over the passes.

How much to aggregate is config.bgaggr, the number G of aggregate classes; the background chain then carries 1 + G. G = 1 is the classic tagged/aggregate pair and the default, so the chain stays two-class whatever R is; G >= R-1 aggregates nothing, carries every closed chain exactly, and answers in ONE pass instead of solving the same chain R times. Passing R reaches that, so asking for no aggregation needs no magic value. The cost is the state space, the product over the 1 + G classes of nchoosek(N_b + Mc - 1, Mc - 1), capped by bgstates_max.

Which chains share a group is decided by similarity of per-station SERVICE DEMAND, in Mam_bgchain_groups. An aggregate carries the flow-weighted mean of its members' service times and routing, so it is exact when they place the same demand at every station and distorts in proportion to how far apart they are; grouping the demand-similar chains together keeps the aggregation where it is harmless and away from the chains it would misrepresent.

Exactness, as measured against SolverCTMC and exact MVA on mixed models of two to four stations: PS or INF with ANY service law (exponential, Erlang, HyperExp, Coxian), any number of servers, Poisson or MAP arrivals and one to four closed chains agree to 4-5 significant digits, as does FCFS with class-independent rates. FCFS with class-DEPENDENT rates keeps the closed queue lengths within ~1% while the open queue length reads 14-20% low, because the server is held here in random order rather than head-of-line.

PS is INSENSITIVE to the service law beyond its mean, and the method honours that rather than approximating it: at a PS station the open service is replaced by the exponential of the same mean before the QBD is built. This QBD tracks ONE service phase for the whole station, so carrying the phase-type there makes the open queue length inherit the SCV-sensitivity of an M/PH/1 FCFS queue -- measured, a HyperExp of SCV 4 read 21% high where the exact answer is the exponential one to five digits. At an FCFS station the service law IS carried, and the background chain reads only the MEAN closed service time, exact under PS by the same insensitivity and a first-moment surrogate under FCFS.

  • Method Details

    • bgchainStates

      public static double bgchainStates(NetworkStruct sn, SolverOptions options)
      Number of states of the background-chain CTMC this solver would build on the model, WITHOUT building it. Mirrors mam_bgchain_states.m.

      The size is what decides whether bgchain is affordable and Mam_bgchain_ctmc only discovers it after the partition is fixed, so the default-method chooser needs it up front. The count follows the partition used below: a pass carries the tagged closed chain as background class 0 and the demand-similar groups of the other closed chains as classes 1..G, each enumerating the compositions of its population over the stations its members visit. Merging two chains onto the UNION of their supports can raise the count as easily as lower it, so the passes are enumerated rather than bounded and the largest returned: that is the one Mam_bgchain_ctmc would refuse.

      Returns:
      the state count, 0 when bgchain does not apply to the model at all, or Double.POSITIVE_INFINITY when it overflows

    • solver_mam_bgchain

      public static MAMResult solver_mam_bgchain(NetworkStruct sn, SolverOptions options)