Posts

排队论

MATH
Contents

基本概念

基本要素

graph LR A[顾客]-->B[排队结构] B-->C[服务机构] C-->D[离去]
  1. 到达时间的分布和服务时间的分布
  2. 服务机构的设置

排队现象的原因

要求服务的顾客数量超过了服务机构的数量。到达的顾客不能立刻得到服务。两个根本原因：

  1. 服务机构的限制
  2. 顾客到达和服务时间是不确定的

常见分布

时间间隔服从负指数分布，到达服从 Poisson 分布

Poisson 分布

Pn(t1,t2)=P(N(t2)−N(t1))=nP_n(t_1,t_2)=P(N(t_2)-N(t_1))=n P{N(t)=n}=(λt)nn!e−λt,n=1,2,…,NP\{ N(t)=n \}=\frac{(\lambda t)^n}{n!} e^{-\lambda t},n=1,2,\dots,N

  • 顾客到达数相互独立

  • 顾客到达是平稳的：P1(t,t+Δt)=λΔt+o(Δt)P_1(t,t+\Delta t)=\lambda \Delta t+ o(\Delta t)

  • 在 [t,t+Δt][t,t+\Delta t] 有 2 个或 2 个以上顾客到达的概率极小

负指数分布

P{T>t+s∣T>s}=P{T>t}P\{T\gt t+s\mid T\gt s\} = P\{ T\gt t\}

Probability density function

fλ(t)={λe−λt,t≥00,t<0f_{\lambda}(t)=\begin{cases} \lambda e^{-\lambda t}&,t\geq 0\\ 0&,t\lt 0 \end{cases}

Cumulative distribution function

Fλ(t)={1−e−λt,t≥00,t<0F_{\lambda}(t)=\begin{cases} 1-e^{-\lambda t}&,t\geq 0\\ 0&,t\lt 0 \end{cases}
  • 无记忆性

k 阶爱尔朗分布

Probability density function

fk(t)={kμ(kμt)k−1(k−1)!e−kμt,t≥00,t<0f_{k}(t)=\begin{cases} \frac{k\mu (k\mu t)^{k-1}}{(k-1)!}e^{-k\mu t}&,t\geq 0\\ 0&,t\lt 0 \end{cases}

  • 当 k≥30k\geq 30 时，趋近于正态分布

  • 当 k→∞k\to\infty 时，方差为 00

常见排队模型

M/M/1

  • λ\lambda

  • μ\mu

  • ρ=λμ\rho=\frac{\lambda}{\mu}

  • P0=1−ρP_0=1-\rho

  • Pn=ρnP0P_n=\rho^n P_0

Ls=ρ1−ρ=λμ−λL_s=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda} Lq=ρ21−ρ=λ2(μ−λ)μ L_q=\frac{\rho^2}{1-\rho}=\frac{\lambda^2}{(\mu-\lambda)\mu}
Ws=1μ−λW_s=\frac{1}{\mu-\lambda} Wq=λ(μ−λ)μW_q=\frac{\lambda}{(\mu-\lambda)\mu}

M/M/1/N

  • λ\lambda

  • μ\mu

  • nn

  • ρ=λμ\rho=\frac{\lambda}{\mu}

当 ρ=1\rho=1

  • Pn=1N+1,n=0,1,2,…,NP_n=\frac{1}{N+1},n=0,1,2,\dots,N

  • λe=μ(1−P0)\lambda_e=\mu(1-P_0)

Ls=N2L_s=\frac N2 Lq=Ls−λeμL_q=L_s- \frac{\lambda_e}{\mu}
Ws=LsλeW_s=\frac{L_s}{\lambda_e} Wq=Ws−1μW_q=W_s-\frac{1}{\mu}

当 ρ≠1\rho\neq 1

  • P0=1−ρ1−ρN+1P_0=\frac{1-\rho}{1-\rho^{N+1}}

  • Pn=ρnP0,n=1,2,…,NP_n=\rho^n P_0,n=1,2,\dots,N

  • λe=μ(1−P0)\lambda_e=\mu(1-P_0)

Ls=ρ1−ρ−(N+1)ρN+11−ρN+1L_s=\frac{\rho}{1-\rho} - \frac{(N+1)\rho^{N+1}}{1-\rho^{N+1}} Lq=Ls−λeμL_q=L_s-\frac{\lambda_e}{\mu}
Ws=LsλeW_s=\frac{L_s}{\lambda_e} Wq=Ws−1μW_q=W_s-\frac{1}{\mu}

M/M/c

和 1c\frac1c 个 M/M/1 不同

M/G/1

P-K 公式（派拉契克-辛钦公式）

Ls=ρ+ρ2+λ2Var(T)2(1−ρ)L_s=\rho+\frac{\rho^2+\lambda^2 \mathrm{Var}(T)}{2(1-\rho)} Lq=Ls−ρL_q=L_s-\rho
Ws=LsλW_s=\frac{L_s}{\lambda} Wq=LqλW_q=\frac{L_q}{\lambda}