Bettilarity
0%

排队论

Posted on Edited on

Queuing theory

基本概念

Poisson分布

$P_k(t)=\frac{(\lambda t)^k}{k!}\cdot e^{-\lambda t}$
若单位时间内到达的顾客的个数服从$\lambda$的Poisson分布，则顾客相继到达时间服从以$\lambda$为参数的负指数分布:
$f(t)=\lambda \cdot e^{-\lambda t}$

Kendall’s notation

[A/B/C/D/E/F]
  • A: 用户到达的模型
  • B: 用户离开的模型
  • C: 服务器的个数
  • D: 排队最大容量
  • E: 顾客源最大容量
  • F: 排队规则，如FCFS，LCFS

    Little Theorm

  • 系统总顾客数 $L=\sum_{k=0}^\infty k\cdot P_k$
  • 平均等待顾客个数 $L_q=\sum_{k=1}^\infty (k-1)\cdot P_k$
  • 包括服务的平均时间 $W=\frac{L}{\lambda}$
  • 平均顾客等待时间 $W_q=\frac{L_q}{\lambda}$

Little 使用条件

  • 系统没有阻塞
  • 系统的平均顾客数=平均到达率*平均到达时间

排队论模型

基本模型 M/M/1

状态转移方程
状态概率
指标

$L=\sum_{k=0}^\infty k\cdot P_k=\frac{\rho}{1-\rho}$

$L_q=\sum_{k=1}^\infty (k-1)\cdot P_k=\frac{\rho^2}{1-\rho}$

$W=\frac{L}{\lambda}=\frac{1}{\mu-\lambda}$

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

有限队列模型 M/M/1/N

状态转移方程
初始状态概率
指标

$L=\sum_{k=0}^\infty k\cdot P_k=\frac{\rho}{1-\rho}-\frac{(N+1)\rho^{N+1}}{1-\rho^{N+1}}$

$L_q=\sum_{k=1}^\infty (k-1)\cdot P_k=L-\frac{\lambda (1-P_N)}{\mu}$

$W=\frac{L}{\lambda}=\frac{L}{\lambda (1-P_n)}$

$W_q=\frac{L_q}{\lambda}=W-\frac{1}{\mu}$

有限用户模型 M/M/1/$\infty$/m

初始状态概率
指标

$W=\frac{m}{\mu(1-P_0)}-\frac{1}{\lambda}$

$L=m-\frac{\mu}{\lambda}\cdot(1-P_0)$

$L_q=m-(1+\rho)(1-\rho)=L-(1-P_0)$

$W_q=W-\frac{1}{m}$

Erlang-wait System M/M/C

当系统的顾客数$k<q$的时候，服务速率为$k\mu$

当系统的顾客数$k>q$的时候，服务速率为$c\mu$

指标

(use Erlang-C form)

M/G/1

G表示服务时间服从任意分布，服务强度$\rho=\lambda \cdot E(\mu)<1$

指标

$L=\rho+\frac{\rho^2}{2(1-\rho)}$

$L_q=L-\frac{\lambda}{\mu}=\frac{\lambda^2}{2\mu (\mu-\lambda)}$

$W_q=\frac{L_q}{\lambda}=\frac{\lambda}{2\cdot \mu(\mu-\lambda)}$

coefficient of variation: $C_x^2=\frac{V[x]}{E[x]^2}$

对于 $M/M/1$, $C_x^2=1, W=\frac{\rho \cdot E[x]}{1-\rho}$

对于 $M/D/1$, $C_x^2=0, W=\frac{\rho \cdot E[x]}{2(1-\rho)}$

对于 $M/E_4/1$, $C_x^2=\frac{1}{r}, W=\frac{\rho \cdot E[x]}{2(1-\rho)}\cdot (1+\frac{1}{r})$

K阶Erlang服务时间 M/$E_k$/1

$E[V]=\frac{1}{\mu}, \sigma(\mu^2)=\frac{1}{k\cdot \mu^2} $

指标

$C_x^2=\frac{1}{r}$

$L=\rho+\frac{(k+1)\cdot \rho^2}{2k(1-\rho)}$

$L_q=\frac{(k+1)\rho^2}{2k(1-\rho)}$

$W=\frac{L}{\lambda}$

$W_q=\frac{L_q}{\lambda}$

Erlang-loss System M/M/m/m/C

状态方程
指标

$P(Time\ blocking)=P_m$

$P(Call\ blocking)=a_m$

Effective traffic$:\ \lambda_{eff}=\sum _{i=0}^{m-1}\cdot \lambda P_i=\lambda(1-P_m)$

$L=\frac{\lambda_{eff}}{\mu}$

一般$C<10m$时，把C看作有限资源

M/G/1 with vacation

$R_s(t):\ Remaining\ service\ time$

$R_v(t):\ Remaining\ vacation\ time$

$W=\frac{R_s}{1-\rho}+\frac{R_v}{1-\rho}$

$W/G/1的 R_s = \frac{\lambda\cdot E[x^2]}{2}$

$可得 W=\frac{\lambda \cdot E[x^2]}{2(1-\rho)}+\frac{R_v}{1-\rho}=\frac{\lambda \cdot E[x^2]}{2(1-\rho)}+\frac{E[V^2]}{2E[V]}$

M/G/1 with priority

non-preemptive 非中断模式

$R_s=\frac{1}{2}\cdot \sum_{i=1}^k \lambda_i\cdot E[x]$

$W_i=\frac{R_s}{(1-\sum_{j=1}^{i-1}\rho_j)(1-\sum_{j=1}^{i}\rho_j)}$

$T_i=W_i+E[X_i]$

Average waiting time: $W=\sum\rho_i W_i=\sum \frac{\lambda_i}{\lambda}\cdot W_i$

preemptive 终端模式

$R_{s,i}=\frac{1}{2}\cdot \sum_{i=1}^{i} \lambda_jE[x_j^2]$

$W_i=\frac{R_{s,i}}{(1-\sum_{i=1}^{i-1}\rho_j)(1-\sum_{j=1}^i\rho_j)}$

总平均等待时间：
$W=\frac{\lambda_1}{\lambda_1+\lambda_n}W_1=\frac{\lambda_n}{\lambda_1+\lambda_n}W_n$

$T_i=W_i+E[X_i]$

Average waiting time: $W=\sum\rho_i W_i=\sum \frac{\lambda_i}{\lambda}\cdot W_i$

服务时间：
$E[X_i^{‘}]=E[X_i]+\sum_{j=1}^{i-1}E[X_j]\lambda_jE[X_1^{‘}]=\frac{E[x_i]}{1-\sum_{j=1}^{i-1}\rho_j}$

Appdendix

  • Burke Theorem : The departure process from an M/M/m queue is Poisson

  • Jackson Theorem : $p(n_1,n_2)=p(n_1)\cdotp(n_2)$

  • Erlang-Loss 算出来的是$P(block)$，而$P(wait)=\frac{m\cdot P(block)}{m-a(1-P(block))}$