Package jline.solvers.ba.analyzers

Class Solver_ba_bpt_analyzer

java.lang.Object
jline.solvers.ba.analyzers.Solver_ba_bpt_analyzer
public final class Solver_ba_bpt_analyzer extends Object
Achievable-region LOWER bound on the mean response times of a multiclass open Markovian network, valid for EVERY non-idling scheduling policy at every station.

Port of matlab/src/solvers/BA/solver_ba_bpt_analyzer.m. The polyhedron is the first-order linear-programming relaxation of the achievable region (Npfqn_bnd_bpt); this analyzer maps the LINE model onto it and reads the bound back per station and class.

CLASS SPACE. The reference's "class" is a buffer: one exponential service rate, one Markovian routing law. LINE's (station, job class) pair is exactly that, so a pair carrying traffic becomes one LP class, the Source is absorbed into the external arrival vector, and class switching needs no special treatment because sn.rt already carries it.

BOUND CONVENTION. R(i,r) is obtained by minimizing x over the polyhedron with the objective set to the unit vector of that pair, so each entry is a valid lower bound on its own. Q follows by Little's law from the bounded R and the EXACT throughput T (an open network's per-class rates are fixed by the traffic equations, not by the policy), and so does C. U is exact for the same reason.

TIGHTNESS. The relaxation is exact on M/M/1 and tight on the externally fed classes, but weak on a class whose arrivals are all internal: the only term coupling x_r to the second-moment block carries the factor lambda0_r, so an internally fed class can fall back to its own mean service time.

Reference: D. Bertsimas, I. Paschalidis, J. Tsitsiklis (1994). Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance. Annals of Applied Probability 4(1), 43-75.