单服务台系统理论推导¶
标准$M/M/1$模型( $M/M/1/\infty/\infty$ )是排队模型中最简单的一个模型，它是指顾客的到达符合参数为$\lambda$的泊松分布，服务时间服从参数为$\mu$的负指数分布，服务台的个数为1，顾客源的数量为无限，系统的容量无限，顾客到达间隔时间和服务时间之间相互独立，排队规则是先到先服务。
在负指数分布中可以假定
从 $[t, t+\Delta t]$ 内 $,$有一个顾客到达的概率为 $\lambda \Delta t+o(\Delta t),$有一个顾客离开的概率为 $\mu \Delta t+o(\Delta t)$，多于一个顾客达到或离开的概率为 $o(\Delta t)$ 。
在时刻 $[t, t+\Delta t]$时，$N(t+\Delta t)=n$的概率用状态转移来理解，可以表述为如下表达式：
$$ P_{n}(t+\Delta t)=P_{n-1}(t) *\left(\lambda \Delta t+o(\Delta t)\right)+P_{n+1}(t) *\left(\mu \Delta t+o(\Delta t)\right) \\ +P_{n}(t) *\left(\lambda \Delta t+o(\Delta t)\right) *\left(\mu \Delta t+o(\Delta t)\right) \\ +P_{n}(t) *(1- \left.\lambda \Delta t+o(\Delta t)\right) *\left(1-\mu \Delta t+o(\Delta t)\right) $$整理后得到
$$ P_{n}(t+\Delta t)-P_{n}(t)=\left[P_{n-1}(t) * \lambda +P_{n+1}(t) * \mu-P_{n}(t) * \lambda -\right. \\ \left.\left.P_{n}(t) * \mu \right] \Delta t+o(\Delta t)\right) $$对于整个系统，在系统稳定时，列状态平衡方程为
$$ \left\{\begin{array}{l} {\lambda P_{0}=\mu P_{1}} \\ {\lambda P_{n-1}+\mu P_{n+1}=\lambda P_{n}+\mu P_{n}(n \geq 1)} \end{array}\right. $$其中，
- $P_i$:系统中排队长度为$i$的概率
- $\lambda$:顾客到达速率
- $\mu$:服务速率
因为所有可能的状态概率求和为1
$$ \sum_{n=0}^{\infty} P_{n}=1 $$结合幂级数展开
$$ \frac{1}{1-\rho} = 1+\rho+\rho^2+\rho^3 + \cdots+\rho^n (\rho<1) $$可以得到
$$ \begin{aligned} &P_{0}=1-\rho\\ &\mathrm{P}_{\mathrm{n}}=(1-\rho) \rho^{n}, \quad n \geq 1 \end{aligned} $$其中
$$ \rho=\frac{\lambda}{\mu} $$为单位时间顾客平均到达率与平均服务率的比值，反映了服务机构的忙碌或利用的程度。
系统中顾客(包括排队等待和正在接受服务的)的数目定义为平均队长$L_s$
$$ \begin{aligned} L_{s} &=\sum_{n=0}^{\infty} n P_{n}=\sum_{n=1}^{\infty} n(1-\rho) \rho^{n} \\ &=\left(\rho+2 \rho^{2}+3 \rho^{3}+\cdots\right)-\left(\rho^{2}+2 \rho^{3}+3 \rho^{4}+\cdots\right) \\ &=\rho+\rho^{2}+\rho^{3}+\cdots \\ &=\frac{\rho}{1-\rho}=\frac{\lambda}{\mu-\lambda}, 0<\rho<1 \end{aligned} $$在队列中排队等待的顾客数定义为平均排队长
$$ \begin{aligned} L_{q} &=\sum_{n=1}^{\infty}(n-1) P_{n}=\sum_{n=1}^{\infty} n P_{n}-\sum_{n=1}^{\infty} P_{n}=L_{s}-\rho \\ &=\frac{\rho^{2}}{(1-\rho)}=\frac{\rho \lambda}{\mu-\lambda}=\frac{\lambda^{2}}{\mu(\mu-\lambda)} \end{aligned} $$正在预期接受服务的顾客数
$$ L=0 P_{0}+1\left(P_{1}+P_{2}+\ldots+P_{n}+\ldots\right)=1-P_{0}=1-(1-\rho)=\rho $$我们可以验证
$$ L_{s}=L_{q}+L $$其他指标的计算方法为 从顾客到达时刻算起到他接受服务完毕为止所需要的时间，即是顾客在系统中所花费的总时间定义为平均逗留时间
$$ W_s = \dfrac{L_s}{\lambda} $$从顾客到达时间算起到他开始接受服务时止的这段时间定义为平均等待时间
$$ W_q = \dfrac{L_q}{\lambda} $$每个顾客的平均服务时间为$d\dfrac{1}{\mu}$,因此
$$ W_s = W_q + \dfrac{1}{\mu} $$参考资料
- ThomsonRen github https://github.com/ThomsonRen/mathmodels