0%

Queue-Theory

13 排队论

1. 背景知识

1.1 Notation

  • 肯德尔记号 (Kendall):输入分布/输出分布/并联服务台数(X/Y/ZX/Y/Z

1971 年,国际排队符号标准会上扩展至六项,记为 (X/Y/Z/A/B/CX/Y/Z/A/B/C):

1
输入分布/输出分布/并联服务台数/系统容量(队长)/系统状态(顾客源数)/服务规则

e.g. M/M/1///FCFSM/M/1/\infty/\infty/FCFS

  • 泊松流

Pn(t)=(λt)nn!eλtP_n(t) = \frac{(\lambda t)^n}{n!}e^{-\lambda t}

  • 负指数分布
    PDF:

fT(t)={λeλt,t00,t<0f_T(t) = \begin{cases} \lambda e^{-\lambda t}, & t \ge 0 \\ 0, & t<0 \end{cases}

CDF:

FT(t)={1eλt,t00,t<0F_T(t) = \begin{cases} 1- e^{-\lambda t}, & t \ge 0 \\ 0, & t<0 \end{cases}

  • 爱尔朗分布 EkE_k
    v1,,vkv_1, \cdots, v_kkk 个相互独立的随机变量,服从相同参数 kμk\mu 的负指数分布,那么:

T=v1+v2++v)kT = v_1 + v_2 + \cdots +v)k

PDF:

bk(t)=μk(μkt)k1(k1)!eμktt>0b_k(t) = \frac{\mu k (\mu kt)^{k-1}}{(k-1)!} e^{-\mu k t} \quad t >0

1.2 级数展开

基本幂级数

\begin{align*} e^x &= \sum\limits_{n=0}^{\infty} \frac{1}{n!}x^n, &-\infty < x < +\infty \\ \sin x &= \sum\limits_{n=0}^{\infty} \frac{(-1)^n}{(2n + 1)!}x^{2n + 1}, &-\infty < x < +\infty \\ \frac{1}{1 + x} &= \sum\limits_{n=0}^{\infty} (-1)^n x^n, &-1 < x < +1 \\ \end{align*}

  • 推广

\begin{align*} \cos x &= \sum\limits_{n=0}^{\infty} \frac{(-1)^n}{(2n)!}x^{2n }, &-\infty < x < +\infty \\ \frac{1}{1 + x^2} &= \sum\limits_{n=0}^{\infty} (-1)^n x^{2n}, &-1 < x < +1 \\ \ln(1+x) &= \sum\limits_{n=0}^{\infty} \frac{(-1)^n}{n+1} x^{n+1} , &-1 < x < +1 \\ a^x = e^{x ln a} &= \sum\limits_{n= 0}^{\infty} \frac{(\ln a)^n}{n!} x^n, &-\infty < x< +\infty \\ \arctan x&= \sum\limits_{n= 0}^{\infty} \frac{(-1)^n}{2n+1} x^{2n+1} , &-1 \leq x \leq +1 \\ \end{align*}

泰勒展开

f(x)=f(x0)0!+f(x0)1!(xx0)+f(x0)n!(xx0)2++f(n)(x0)n!(xx0)n+Rn(x)f(x) = \frac{f(x_0)}{0!} + \frac{f^\prime(x_0)}{1!} (x - x_0) + \frac{f^{\prime\prime}(x_0)}{n!} (x - x_0)^2 + \cdots + \frac{f^{(n)}(x_0)}{n!} (x - x_0)^n + R_n(x)

拓展:麦克劳林公式

\begin{align*} e^x &= 1 + x + \frac{1}{2!} x^2 + \cdots + \frac{1}{n!} x^n + o(x^n) \\ \sin x &= x - \frac{1}{3!} x^3 + \cdots + \frac{(-1)^{m-1}}{(2m-1)!} x^{2m-1} + o(x^{2m-1}) \\ \cos x &= 1 - \frac{1}{2!} x^2 + \cdots + \frac{(-1)^{m}}{(2m)!} x^{2m} + o(x^{2m}) \\ \ln (1+x) &= x - \frac{1}{2} x^2 + \cdots + \frac{(-1)^{n-1}}{n} x^{n} + o(x^{n}) \\ \end{align*}

佩亚诺余项为 (xx0)n(x-x_0)^n 的高阶无穷小:Rn(x)=o[(xx0)n]R_n(x) = o\big[(x-x_0)^n\big]

1.2 运行指标

排队系统运行指标间的关系:

  • λ\lambda:单位时间内顾客的平均到达数,则 1/λ1/\lambda 表示向量两个顾客到达的平均时间;
  • μ\mu:单位时间内被服务完毕离去的 平均顾客数1/μ1/\mu 表示对每个顾客的 平均服务时间
  • SS:服务系统中并联的服务台数
  • Pn(t)P_n(t):时刻 tt 系统中恰有 nn 个顾客的概率。

排队系统中运行指标之间的关系

\begin{align} L_s & = \lambda W_s &\quad W_s & =\frac{L_s}{\lambda} \\ L_q & = \lambda W_q &\quad W_q & =\frac{L_q}{\lambda} \\ L_s & = L_q + \frac{\lambda}{\mu} &\quad W_s & =W_q + \frac{1}{\mu} \\ L_s & = \sum\limits_{n=0}^\infty n P_n &\quad W_q & =W_s -\frac{1}{\mu}=\frac{\rho}{\mu-\lambda} \\ L_q & = \sum\limits_{n=0}^\infty (n-s)P_n =\frac{\rho \lambda }{\mu-\lambda} \end{align}

  • M/M/1//M/M/1/\infty/\infty

\begin{align} P_0 &= 1-\rho \\ P_n &=\rho^n P_0 \\ L_s & =\sum\limits_{n=0}^\infty n P_n = \rho(1-\rho)\left( \frac{1}{1-\rho}\right)^\prime = \frac{\rho}{1-\rho} = \frac{\lambda}{\mu-\lambda} \\ W_s & =\frac{L_s}{\lambda} \\ L_q & = L_s -\frac{1}{\mu} \\ W_q & = \frac{L_1}{\lambda} \\ \end{align}

WsW_s 的 PDF可以表示为:

f(Ws)=(μλ)e(μλ)tf(W_s) = (\mu-\lambda) e^{-(\mu-\lambda)t}

-------------This blog is over! Thanks for your reading-------------