queuing-theory

排队论

排队论的基本构成

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

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

  • 服务机构:服务台的数量;服务时间服从的分布。

排队系统的数量指标

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

排队论中的符号表示

A/B/C/nA/B/C/n

AA输入过程,BB服务时间,CC服务台数,nn系统容量。

例如:M/M/S/M/M/S/\infty

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

参数为λ\lambdaPoissonPoisson分布:

Pn(t)=(λt)nn!eλtP_n(t) = \frac{(\lambda t)^n}{n!}e^{-\lambda t}

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

参数为μ\mu的负指数分布:

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

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

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

重要统计量

  • 系统的服务强度:ρ=λμ\rho = \frac{\lambda}{\mu}
  • 无顾客的概率:p0=1ρ=1λμp_0 = 1 - \rho = 1 - \frac{\lambda}{\mu}
  • nn个顾客的概率:ρn=(1ρ)ρn\rho_n = (1 - \rho)\rho^n
  • 平均队长:

    Ls=n=0npn=(1ρ)n=0nρn=ρ1ρ=λμλ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}

  • 平均等待队长:

    Lq=n=1(n1)pn=(1ρ)n=1(n1)ρn=ρ21ρ=λ2μ(μλ)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)}

  • 平均逗留时间:

    Ws=1μλW_s=\frac{1}{\mu-\lambda}

  • 平均等待时间:

    Wq=1μλ1μ=λμ(μλ)W_q=\frac{1}{\mu-\lambda}-\frac{1}{\mu}=\frac{\lambda}{\mu(\mu-\lambda)}

  • LittleLittle公式:

    Ls=λWs,Lq=λWqL_s=\lambda W_s, L_q=\lambda W_q

等待制模型 M/M/S/M/M/S/\inftyS>1S>1

  • 服务能力和强度:

    Sμ,ρ=λsμS\mu,\rho = \frac{\lambda}{s\mu}

  • 服务台都空闲的概率:

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

  • 平均队长

    Ls=Sρ+(Sρ)SρS!(1ρ)2p0L_{s}=S \rho+\frac{(S \rho)^{S} \rho}{S !(1-\rho)^{2}} \cdot p_{0}

其他模型

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

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

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

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

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

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