queuing-theory

排队论

排队论的基本构成

• 输入过程：描述顾客按照怎样的规律到达排队系统。顾客总体（有限/无限），到达的类型（单个/成批）、到达时间间隔等。

• 排队规则：指顾客按怎样的规定次序接受服务。常见的有等待制、损失制、混合制、闭合制等。

• 服务机构：服务台的数量；服务时间服从的分布。

排队系统的数量指标

• 队长：系统中的平均顾客数（包括正在接受服务的顾客）
• 等待队长：系统中处于等待的顾客的数量
• 等待时间：等待时间包括顾客的平均逗留时间
• 忙期：连续保持服务的时长

排队论中的符号表示

$A/B/C/n$

$A$输入过程，$B$服务时间，$C$服务台数，$n$系统容量。

例如：$M/M/S/\infty$

• 输入过程是$Poisson$流
• 服务时间服从负指数分布
• 系统有$S$个服务台平行服务
• 系统容量为无穷大的等待制排队系统

参数为$\lambda$的$Poisson$分布：

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

$[0,t]$时间内到达的顾客平均数为$\lambda t$。

参数为$\mu$的负指数分布：

$f(t) =\mu e^{-\mu t}(t>0)$

每个顾客接受服务的平均时间为$\frac{1}{\mu}$。

那么假设$\lambda \geq \mu$，那么显然服务队列中的人数将趋于无穷，队列是不稳定的。

重要统计量

• 系统的服务强度：$\rho = \frac{\lambda}{\mu}$
• 无顾客的概率：$p_0 = 1 - \rho = 1 - \frac{\lambda}{\mu}$
• 有$n$个顾客的概率：$\rho_n = (1 - \rho)\rho^n$
• 平均队长：

  $L_s = \sum_{n=0}^\infty np_n = (1 - \rho)\sum_{n=0}^\infty n\rho^n=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}$

• 平均等待队长：

  $L_q=\sum_{n=1}^\infty(n-1)p_n=(1-\rho)\sum_{n=1}^\infty(n-1)\rho^n=\frac{\rho^2}{1-\rho}=\frac{\lambda^2}{\mu(\mu-\lambda)}$

• 平均逗留时间：

  $W_s=\frac{1}{\mu-\lambda}$

• 平均等待时间：

  $W_q=\frac{1}{\mu-\lambda}-\frac{1}{\mu}=\frac{\lambda}{\mu(\mu-\lambda)}$

• $Little$公式：

  $L_s=\lambda W_s, L_q=\lambda W_q$

等待制模型 $M/M/S/\infty$：$S>1$

• 服务能力和强度：

  $S\mu,\rho = \frac{\lambda}{s\mu}$

• 服务台都空闲的概率：

  $p_{0}=\left[\sum_{k=0}^{S-1} \frac{(S \rho)^{k}}{k !}+\frac{(S \rho)^{S} \rho}{S !(1-\rho)}\right]^{-1}$

• 平均队长

  $L_{s}=S \rho+\frac{(S \rho)^{S} \rho}{S !(1-\rho)^{2}} \cdot p_{0}$

其他模型

损失制模型 $M/M/S/S$

• 顾客到达服从泊松分布，服务台服务时间服从指数分布
• 当$S$个服务台被占用后，顾客自动离开，不再等待

混合制模型 $M/M/S/K$

• 顾客到达服从泊松分布，服务台服务时间服从指数分布
• 系统容量为$K$，当K个位置被占用时，顾客自动离开

闭合制模型 $M/M/S/K/K$

• 顾客到达服从泊松分布，服务台服务时间服从指数分布
• 系统容量和潜在的顾客数都为$K$