pfqn_sjn.h File Reference

Closed networks with non-preemptive shortest-job-next (SJN/SJF) stations. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
#include <vector>
#include "line/api/pfqn/pfqn_bs.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for pfqn_sjn.h:

Go to the source code of this file.

Classes
struct	line::pfqn::SjnOptions
	Options of the SJN solvers, the fields sjn_args fills in. More...
struct	line::pfqn::SjnProfile
	The conditional waiting time profile at one SJN station, the reference's WX. More...
struct	line::pfqn::SjnResult
	Return block of pfqn_mvasjn and pfqn_amvasjn. More...
class	line::pfqn::SjnStarvationError
	The conditional waiting time equation has no solution at some population. More...

Namespaces
namespace	line
namespace	line::pfqn

Functions
SjnResult	line::pfqn::pfqn_mvasjn (const Matrix< double > &L, const std::vector< double > &N, const std::vector< double > &Z, const Matrix< double > &scv, const std::vector< std::size_t > &sjnset, const Matrix< double > &V, const SjnOptions &options)
	Exact-lattice MVA for closed networks with SJN stations, the unidirectional scheme of Kant 1992.
SjnResult	line::pfqn::pfqn_amvasjn (const Matrix< double > &L, const std::vector< double > &N, const std::vector< double > &Z, const Matrix< double > &scv, const std::vector< std::size_t > &sjnset, const Matrix< double > &V, const SjnOptions &options)
	Schweitzer fixed point counterpart of pfqn_mvasjn.

Detailed Description

Closed networks with non-preemptive shortest-job-next (SJN/SJF) stations.

Port of matlab/src/api/pfqn/pfqn_mvasjn.m and pfqn_amvasjn.m together with the six private helpers they share (sjn_args, sjn_fit, sjn_setup, sjn_quad, sjn_station, sjn_cap), cross-checked against jar/src/main/java/jline/api/pfqn/mva/{Pfqn_mvasjn,Pfqn_amvasjn,SjnSupport}.java.

THE EQUATION. A tagged customer whose service requirement is x waits, by the arrival theorem, for the residual life of the job in service, for the work of the queued jobs that will be served before it, and for the work of the jobs that overtake it while it waits (Kant 1992, eqs. 1-7):

W(x,n) = [ (1+CV^2) s U(n-1)/2 + X(n-1) phi(x,n-1) ] / [ 1 - X(n-1) theta(x) ] theta(x) = int_0^x t f(t) dt, phi(x,n) = int_0^x W(t,n) t f(t) dt R(n) = s + int_0^inf W(x,n) f(x) dx

W(.,n) needs only phi(.,n-1), so the profile is carried alongside the population recursion. pfqn_mvasjn does exactly that over the whole lattice; pfqn_amvasjn replaces the lattice by a Schweitzer closure applied to the SIZE-RESOLVED queue length lam_k W_k(x) f_k(x) rather than to its integral, which is why the two share sjn_station unchanged and differ only in the deflation vector beta handed to it.

THE SIZE DENSITY IS NOT AN INPUT. Only its mean and SCV are, and the density is reconstructed by the two-moment branching-Erlang fit the reference prescribes. That is what makes theta and the tail integrals closed form and lets the x-integrals run on a FIXED grid: W(.,n) is needed again at the next population step, so a rule that samples at arbitrary abscissae cannot be used. Beyond the grid edge Lx the profile is closed by the analytic tail W(x,n) = a - b exp(-c (x - Lx)) of eqs. (11)-(14).

ARITHMETIC: DOUBLE, NOT TEMPLATED. Unlike its pfqn neighbours this header is not generic in the number type. The recursion evaluates the REGULARIZED INCOMPLETE GAMMA in both its branches, for which the port has no T-generic implementation, and its accuracy is set by a 33-point Simpson grid rather than by the arithmetic, so a wider T would buy nothing. Callers gate on num_traits<T>::has_transcendental and convert at the boundary; the exact (Rational) path refuses SJN by name in solver_mva_sjn.h.

WHY NOT REUSE mam::gammainc_lower. It returns only P(a,x). The tail correction needs Q(a,x) at magnitudes around 1e-300, where 1 - P is exactly zero, so an upper branch that is computed rather than subtracted is mandatory. detail::gammainc below returns both from the one continued fraction, which is also what MATLAB's gammainc(...,'upper') does.

WARNINGS BECOME FLAGS. The reference calls line_warning when the utilization cap binds and when the fixed point runs out of iterations. This port has no warning channel, so SjnResult::capped and SjnResult::converged carry the same information to the caller. The hard line_error cases stay exceptions.

Reference: K. Kant, "MVA approximations for SJN scheduling", Performance Evaluation 15(1):41-61, 1992.

Definition in file pfqn_sjn.h.