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) = (-) e^{-(-)t} $$