Package jline.api.npfqn

Class Npfqn_bnd_bpt

java.lang.Object
jline.api.npfqn.Npfqn_bnd_bpt
public final class Npfqn_bnd_bpt extends Object
First-order linear-programming relaxation of the achievable region of a multiclass open Markovian queueing network.

Port of matlab/src/api/npfqn/npfqn_bnd_bpt.m. Returns a LOWER bound on sum_r c_r x_r, where x_r is the mean sojourn time of class r, valid for EVERY non-idling scheduling policy.

A "class" here is a buffer with its own exponential service rate and its own Markovian routing, so a station serving several customer types owns one class per type. The network is open: class r receives external Poisson arrivals at rate lambda0[r] and, on completing service, becomes class r' with probability P(r,r') or leaves with the row deficit.

METHOD. Uniformize the chain and let R(t) = sum_r f(r) n_r(t) for an arbitrary vector f. The steady-state balance of E[R^2] is an identity quadratic in f; since it holds for every f, the coefficient matrices of the two sides agree entrywise. Diagonal entries give one equation per class, off-diagonal entries one per unordered pair, in the variables x_r, I(r,l) = E[1{sigma(r) busy with r} n_l] and N(i,l) = E[1{station i idle} n_l]. A third block states that the events "station i serves class r" and "station i idle" are mutually exclusive and exhaustive, so their terms sum to E[n_l] = lambda_l x_l. Minimizing over this polyhedron is a relaxation, hence a lower bound.

EXACT ON M/M/1: the LP reduces to mu*I11 - lambda^2*x = lambda and I11 + N11 = lambda*x with N11 >= 0, whence x >= 1/(mu-lambda) with equality.

NOT INCLUDED, DELIBERATELY: the valid inequality I(r,r) >= rho_r would tighten the relaxation but is not part of the reference's characterization, and reproducing the reference's published bounds is the acceptance test here.

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. See also D. Bertsimas (1995), Queueing Systems 21, 337-389, Theorem 9, which restates the same characterization.

  • Method Details

    • npfqn_bnd_bpt

      public static Npfqn_bnd_bpt.Result npfqn_bnd_bpt(double[] lambda0, double[] mu, Matrix P, int[] stationOf, double[] c)
      Parameters:
      lambda0 - external Poisson arrival rate into each class (0 if none)
      mu - exponential service rate of each class
      P - K x K routing, P(r,r') = P(class r becomes r' after service)
      stationOf - zero-based station index of each class
      c - objective weights; null means all ones