qsys_gigk_rqt.h File Reference

Robust Queueing Theory (RQT) worst-case system time of a G/G/k FCFS queue. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/qsys/qsys_types.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for qsys_gigk_rqt.h:

Go to the source code of this file.

Classes
struct	line::qsys::GigkRqtResult< T >

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
GigkRqtResult< T >	line::qsys::qsys_gigk_rqt (const T &lambda, const T &mu, const T &Gamma_a, const T &Gamma_s, std::size_t k, const T &alpha_a, const T &alpha_s)
	Robust Queueing Theory (RQT) worst-case system time of a G/G/k FCFS queue.

Detailed Description

Robust Queueing Theory (RQT) worst-case system time of a G/G/k FCFS queue.

Templated port of matlab/src/api/qsys/qsys_gigk_rqt.m, cross-checked against jar/src/main/java/jline/api/qsys/Qsys_gigk_rqt.java.

The arrival and service processes are not described by distributions but by the polyhedral uncertainty sets

U^a = { T : (sum_{i=k+1}^n T_i - (n-k)/lambda)/(n-k)^(1/alpha_a) >= -Gamma_a } U^s = { X : (sum_{i=k}^n X_i - (n-k+1)/mu)/(n-k+1)^(1/alpha_s) <= Gamma_s }

whose shape follows the (generalized) central limit theorem: alpha = 2 is the finite-variance regime, alpha in (1,2) the heavy-tailed one. Performance analysis is then a worst-case optimization rather than an expectation.

W is the closed-form bound of Theorem 3 (Theorem 8 when the two tails differ, with ab = min(alpha_a,alpha_s)),

W <= (ab-1)/ab^(ab/(ab-1)) lambda^(1/(ab-1)) (Gamma_a + Gamma_s/k^(1/ab))^(ab/(ab-1)) / (1-rho)^(1/(ab-1)) + k/lambda,

which for k = 1 reduces to Theorem 2 and, at ab = 2, to the Kingman-like form (lambda/4)(Gamma_a+Gamma_s)^2/(1-rho) + 1/lambda. Sworst is the exact worst case over the uncertainty sets, eq. (45): the supremum over the integer x = nu-j+1 >= 1 of

x/mu + Gamma_s x^(1/alpha_s) - k(x-1)/lambda + Gamma_a (k(x-1))^(1/alpha_a).

The arrival deviation ADDS to the worst case, since the adversary shortens the interarrival times; the sign printed in eq. (12) is easily misread as a subtraction of the whole arrival bracket, and reading it that way puts Sworst an order of magnitude below W.

W is a SYSTEM time (waiting plus service), and its additive term is k/lambda rather than the mean service time 1/mu.

ARITHMETIC. Real exponents make this transcendental. At rho >= 1 MATLAB returns Inf; the port raises instead, as the rest of the qsys port does.

Reference: C. Bandi, D. Bertsimas, N. Youssef (2015). Robust Queueing Theory. Operations Research 63(3), 676-700.

Definition in file qsys_gigk_rqt.h.