The MMAP[K]/G[K]/1 LCFS-PR queue: K customer types with class-dependent GENERAL service under preemptive-resume last-come-first-served, fed by a marked Markovian arrival process. More...

#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <limits>
#include <string>
#include <vector>
#include "line/api/qsys/qsys_mmapgk1.h"

Include dependency graph for qsys_mmapgk1_lcfspr.h:

Classes
struct	line::qsys::MmapGk1LcfsprResult< T >
	Return value of qsys_mmapgk1_lcfspr, mirroring the MATLAB struct. More...
struct	line::qsys::MmapGk1LcfsprOptions< T >
	The MATLAB name-value options. More...

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::qsys
namespace	line::qsys::mmapgk1lcfsprdetail

Typedefs
typedef std::complex< double >	line::qsys::mmapgk1lcfsprdetail::cdbl
typedef std::vector< std::vector< cdbl > >	line::qsys::mmapgk1lcfsprdetail::CMat

Functions
CMat	line::qsys::mmapgk1lcfsprdetail::czeros (std::size_t n)
CMat	line::qsys::mmapgk1lcfsprdetail::ceye (std::size_t n)
CMat	line::qsys::mmapgk1lcfsprdetail::cmatmul (const CMat &A, const CMat &B)
template<class T>
CMat	line::qsys::mmapgk1lcfsprdetail::to_cmat (const Matrix< T > &A)
CMat	line::qsys::mmapgk1lcfsprdetail::csolve (const CMat &A, const CMat &B)
	X = A^-1 B over the complex field, column by column.
CMat	line::qsys::mmapgk1lcfsprdetail::cexpm (CMat A)
	Complex matrix exponential, scaling and squaring over a Taylor series.
void	line::qsys::mmapgk1lcfsprdetail::ceig_decomp (const CMat &U, std::vector< cdbl > &ev, CMat &V, CMat &Vinv, double &rcond)
	U = V diag(ev) V^-1 for a COMPLEX matrix, the reference's eig(U) at a complex argument.
CMat	line::qsys::mmapgk1lcfsprdetail::ceig_apply (const CMat &V, const CMat &Vinv, const std::vector< cdbl > &g)
	V diag(g) V^-1, kept complex.
template<class T>
CMat	line::qsys::mmapgk1lcfsprdetail::cmatrix_lst_map (const mam::Map< T > &rep, const CMat &U)
	int exp(Ut) dF(t) for a (D0, D1) phase-type law at a complex U, on the Kronecker sum.
template<class T>
CMat	line::qsys::mmapgk1lcfsprdetail::cmatrix_lst (const lang::Distrib< T > &law, const CMat &U, std::size_t quad_nodes)
	The matrix transform of a Distribution object at a complex U.
template<class T>
CMat	line::qsys::mmapgk1lcfsprdetail::cmatrix_lst (const MmapGk1Service< T > &svc, const CMat &U, std::size_t quad_nodes)
	The matrix transform of a service law in any of its three forms, at a complex U.
template<class T>
std::vector< cdbl >	line::qsys::mmapgk1lcfsprdetail::sojourn_lst (const Matrix< T > &D0, const std::vector< Matrix< T > > &Dk, const std::vector< MmapGk1Service< T > > &svc, const std::vector< T > &piArr, const std::vector< T > &lambdas, cdbl s, std::size_t quad_nodes, double tol)
	Per-type sojourn LST pi D_k F_k(Q(s)) e / lambda_k, Q(s) the minimal solution of Q* = C - sI + sum_j D_j F_j(Q*), iterated from C - sI.
double	line::qsys::mmapgk1lcfsprdetail::euler_invert (const std::function< cdbl(cdbl)> &lst, double t)
	Abate-Whitt Euler inversion of a CDF from its LST, qsys_mmapgk1_invert.m.
template<class T>
MmapGk1LcfsprResult< T >	line::qsys::qsys_mmapgk1_lcfspr (const std::vector< Matrix< T > > &MMAP, const std::vector< MmapGk1Service< T > > &svc, const MmapGk1LcfsprOptions< T > &opt)
	MMAP[K]/G[K]/1 LCFS-PR, per type, by Takine's matrix product form.
template<class T>
MmapGk1LcfsprResult< T >	line::qsys::qsys_mmapgk1_lcfspr (const std::vector< Matrix< T > > &MMAP, const std::vector< MmapGk1Service< T > > &svc)
	qsys_mmapgk1_lcfspr with the reference's defaults (no distributions, no CDF).
template<class T>
MmapGk1LcfsprResult< T >	line::qsys::qsys_mmapgk1_lcfspr (const std::vector< Matrix< T > > &MMAP, const std::vector< lang::Distrib< T > > &svc, const MmapGk1LcfsprOptions< T > &opt)
	qsys_mmapgk1_lcfspr on Distribution objects.
template<class T>
MmapGk1LcfsprResult< T >	line::qsys::qsys_mmapgk1_lcfspr (const std::vector< Matrix< T > > &MMAP, const std::vector< lang::Distrib< T > > &svc)
	qsys_mmapgk1_lcfspr on Distribution objects with the reference's defaults.

Detailed Description

The MMAP[K]/G[K]/1 LCFS-PR queue: K customer types with class-dependent GENERAL service under preemptive-resume last-come-first-served, fed by a marked Markovian arrival process.

Port of qsys_mmapgk1_lcfspr.m.

THE METHOD, Takine (2002). With C = D0, D_k = D^(k) and F_k the service law of type k, let Q be the minimal solution of

Q = C + sum_k D_k F_k(Q),      F_k(Q) = int_0^inf exp(Qx) dF_k(x),

the generator of the arrival phase with the busy periods excised (He's U in qsys_mmapgk1.h), and kappa its stationary vector. With beta_k = D_k e E[S_k], Takine's Theorem 1 gives the rate matrices

R_k = (beta_k kappa + D_k (I - F_k(Q))) (e kappa - Q)^-1,  R = sum_k R_k,

and the per-class numbers in system have the matrix product form y(n) = sum_k y(n - e_k) R_k, y(0) = (1 - rho) kappa. From it

P(N = n)   = (1 - rho) kappa R^n e,
P(Y_k = m) = (1 - rho) kappa (A_k R_k)^m A_k e,  A_k = (I - R + R_k)^-1,
E[Y_k]     = pi R_k (I - R)^-1 e,

with pi the stationary vector of C + D. A type-k sojourn under LCFS-PR is the sub-busy period its own service opens, so

E[exp(-s W_k)] = pi D_k F_k(Q*(s)) e / lambda_k,
Q*(s) = C - sI + sum_j D_j F_j(Q*(s)),

evaluated at COMPLEX s for the Euler inversion of the CDF. That is why this header carries a complex matrix transform: the real one in qsys_mmapgk1.h returns real(V diag(g) V^-1), which is right only for a real argument.

Reference: T. Takine, "Matrix product-form solution for an LCFS-PR single-server queue with multiple arrival streams governed by a Markov chain", Queueing Systems 42(2):131-151, 2002.

Definition in file qsys_mmapgk1_lcfspr.h.

Classes

Namespaces

Typedefs

Functions

Detailed Description