M/G/1 under LRPT (longest remaining processing time). More...

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

Include dependency graph for qsys_mg1_lrpt.h:

Namespaces
namespace	line
namespace	line::qsys

Functions
template<class T>
Mg1DisciplineResult< T >	line::qsys::qsys_mg1_lrpt (const std::vector< T > &lambda, const std::vector< T > &mu, const std::vector< T > &cs)
	M/G/1 under LRPT (longest remaining processing time).

Detailed Description

M/G/1 under LRPT (longest remaining processing time).

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

LRPT gives the server to the job with the most work left, so the slowdown is the same for every job in the system (Wierman and Harchol-Balter, SIGMETRICS 2003, Sec. 3.2):

E[T(x)] = x/(1-rho) + lambda E[X^2] / (2 (1-rho)^2)

with rho the total load and E[X^2] the second moment of the mixture size. Only the first term depends on x, so under the exponential path the class mean is

E[T_k] = int_0^{20/mu_k} E[T(x)] mu_k e^{-mu_k x} dx

and this integral is elementary. MATLAB evaluates it by adaptive quadrature; the port uses the closed form of the same truncated integral,

int_0^X x mu e^{-mu x} dx = (1 - e^{-muX}(1 + muX))/mu, int_0^X mu e^{-mu x} dx = 1 - e^{-muX}, muX = 20,

which is the value MATLAB's quadrature converges to, so the two agree to MATLAB's RelTol of 1e-8 and in practice to round-off. The truncation at 20 mean service times is kept: dropping it would change the answer in the eighth digit and no longer reproduce the reference.

The general path (some cs != 1) is MATLAB's class-based preemptive-priority surrogate, with the classes sorted by decreasing mean size. Note that it ignores cs entirely – the residual term is sum_{i<=k} lambda_i/mu_i^2, i.e. the second moment of an exponential – so for a non-exponential input the reference answer does not depend on the variability it was given. That is a defect of the reference, reproduced here rather than silently fixed.

ARITHMETIC. exp appears in the exponential path, so the function is gated.

Definition in file qsys_mg1_lrpt.h.

Namespaces

Functions

Detailed Description