Queue-Theory

13 排队论

1. 背景知识

1.1 Notation

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

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

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

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

• 泊松流

  $$P_n(t) = \frac{(\lambda t)^n}{n!}e^{-\lambda t}$$

• 负指数分布
  PDF:

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

  CDF:

  $$F_T(t) = \begin{cases} 1- e^{-\lambda t}, & t \ge 0 \\ 0, & t<0 \end{cases}$$
• 爱尔朗分布 $E_k$
  设 $v_1, \cdots, v_k$ 是 $k$ 个相互独立的随机变量，服从相同参数 $k\mu$ 的负指数分布，那么： $$T = v_1 + v_2 + \cdots +v)k$$ PDF: $$b_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) = \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*}$$

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

1.2 运行指标

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

• $\lambda$：单位时间内顾客的平均到达数，则 $1/\lambda$ 表示向量两个顾客到达的平均时间；
• $\mu$：单位时间内被服务完毕离去的 平均顾客数，$1/\mu$ 表示对每个顾客的 平均服务时间
• $S$：服务系统中并联的服务台数
• $P_n(t)$：时刻 $t$ 系统中恰有 $n$ 个顾客的概率。

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

$$\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/\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}$$

$W_s$ 的 PDF可以表示为:

$$f(W_s) = (\mu-\lambda) e^{-(\mu-\lambda)t}$$