Package jline.solvers.ba.analyzers

Class Solver_ba_bgt_analyzer

java.lang.Object
jline.solvers.ba.analyzers.Solver_ba_bgt_analyzer
public final class Solver_ba_bgt_analyzer extends Object
Piecewise-linear Lyapunov UPPER bound on the steady-state queue lengths of a multitype open Markovian network, valid for EVERY work-conserving Markovian policy.

Port of matlab/src/solvers/BA/solver_ba_bgt_analyzer.m. The polyhedron and the bound are Npfqn_bnd_bgt; this analyzer maps the LINE model onto them and reads the bound back per station and class.

CLASS SPACE. The reference's network is a MULTITYPE one: each type follows a FIXED sequence of stages, and stage k of type i is its own buffer. LINE's (station, job class) pair is that buffer, so the analyzer walks the routing matrix from the Source and turns each open class into one type whose stages are the pairs it visits. Two gates follow from the model and are enforced by name rather than approximated: routing must be DETERMINISTIC (a pair sends everything to one successor, or everything to the Sink), and routes must NOT MERGE (a pair belongs to exactly one type, else the reference's class index (i,k) is not defined). A re-entrant line is expressible by giving the revisits distinct LINE classes.

THE BOUND IS LOOSE, and knowingly so: the exception parameter of the smoothed Lyapunov function carries (Lmax+gamma)^3/gamma^2 and dominates as soon as there is more than one station. What is sharp is the STABILITY CERTIFICATE and the geometric tail RATE.

Reference: D. Bertsimas, D. Gamarnik, J. N. Tsitsiklis (2001). Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability 11(4), 1384-1428, Section 5.1.