排队论简述及LINGO实现（3）——基于生灭过程的排队模型

基于生灭过程的排队模型

首先，我们假定模型都具有泊松输入和指数服务时间。给出三个模型作为排队系统的三个重要类型

$M/M/s$模型

$M/M/s$模型认为所有间隔到达时间按照指数分布且平均分布（即输入源为泊松分布），所有服务时间按照另一个独立的指数分布且均匀分布，且所有服务台数量为$s$，其平均到达率与平均服务率为$\lambda$和$\mu$。

当$s = 1$时，生灭过程参数为$\lambda_n$和$\mu_n$。

当$s > 1$时，系统到达率仍为$\lambda_n$，系统服务率为

• 当$n \leq s$时，$\mu_n = n\mu$，此时$\rho = 1$
• 当$n \geq s$时，$\mu_n = s\mu$，此时$\rho \leq 1$

$M/M/1$模型

当$s = 1$ 时，$\lambda_n = \lambda_1, \mu_n = \mu_1, \rho_n = \rho$， 则$C_n = \rho^n P_0$

则$P_n = \rho^n(1-\rho)，P_0 = 1- \rho, L = \frac{\lambda}{\mu - \lambda}, L_q = \frac{\lambda^2}{\mu(\mu - \lambda)}$

经简化计算得$W = \frac{1}{\mu - \lambda}, W_q = \frac{\lambda}{\mu(\mu - \lambda)}$

$P{W_q > t} = \rho e^{-\mu(1-\rho)t}$

$P{W_q > t | W_q > 0} = e^{-\mu(1-\rho)t}$

$M/M/s$模型

当$s>1$时， $C_n$ 变为

当$n<s$时， $C_n = \frac{(\lambda/\mu)^n}{n!}$

当$n\geq s$时， $C_n = \frac{(\lambda/\mu)^n}{s!s^{n-s}}$

经过中间计算，得出

$P_0=1/[\sum_{n=1}^{s-1}\frac{(\lambda/\mu)^n}{n!}+\frac{(\lambda/\mu)^s}{s!}\frac{1}{1-(\lambda/s\mu)}]$

$P_n$取值为

当$n<s$时，$P_n = \frac{(\lambda/\mu)^n}{n!}P_0$

当$n \geq s$时，$P_n = \frac{(\lambda/\mu)^n}{s!s^{n-s}}P_0$

$L_q = \frac{P_0(\lambda/\mu)^{s}\rho}{s!(1-\rho)^2}$

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

$W = W_q + \frac{1}{\mu}$

$L = L_q + \frac{\lambda}{\mu}$

$P{W>t} = e^{-\mu t}[1+\frac{P_0(\lambda/\mu)^s}{s!(1-\rho)}(\frac{1-e^{-\mu t(s-1-\lambda/\mu)}}{s-1-\lambda/\mu})]$

$P{W_q>t} = (1-P{W = 0})e^{-s\mu(1-\rho)t}$

其中$P{W = 0} = \sum^{s-1}_{n = 0} = P_n$

例题分析

医院急诊中，管理工程师得出结论：急诊的到达时间是随机的，所以间隔到达时间具有指数分布，每个医生的治疗时间也为指数分布，故在此选用$M/M/s$模型进行求解

每位病人的平均到达率为每半个小时一人，故有

$\lambda = 2$

每名医生治疗一位病人需要20min，故有

$\mu = 3$

考虑1位医生($s = 1$)和2位医生($s = 2$)的情况，在这两种情况下都有

$\rho = \frac{\lambda}{s\mu} < 1$，即都不会出现队列爆炸的情况， 系统都将趋于稳定

	$s = 1$	$s = 2$
$\rho$	2/3	1/3
$P_0$	1/3	1/2
$P_n$	2/9	1/3
$P{W_q > t}$	$\frac{2}{3}e^{-t}$	$\frac{1}{6}e^{-4t}$
$P{W > t}$	$e^{-t}$	$\frac{1}{2}e^{-3t}(3-e^{-t})$

$M/M/s/K$模型

$M/M/s/K$模型在$M/M/s$模型的基础上将队列假设为有限长的，系统中新来的顾客数量不允许超过某个指定的数量$K$。因此队列容量为$K - s$，在队列已满的情况下，新顾客会直接离开无法加入队列。即对于模型来说，当系统状态达到$K$值时，系统的平均输入率$\lambda = 0$，因此对$\lambda_n$ 进行修正，即有

$\lambda_n = \lambda$，当$n < K$时

$\lambda_n = 0$，当$n \geq K$时

$M/M/1/K$模型

当$s = 1$时

$P_0 = \frac{1}{\sum_{n = 0}^{K}(\lambda/\mu)} = \frac{1 - \rho}{1 - \rho^{K+1}}$

$P_n = \frac{1 - \rho}{1 - \rho^{K+1}}\rho^{n}$

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

$L_q = L - (1-P_0)$

$W = \frac{L}{\bar{\lambda}}, W_q = \frac{L_q}{\bar{\lambda}}$

$M/M/s/K$模型

当$s > 1$时

$P_n$取值为

当$n<s$时， $P_n = \frac{(\lambda - \mu)^n}{n!}P_0$

当$n\geq$且$n<K$时， $P_n = \frac{(\lambda - \mu)^n}{s!s^{n-s}}P_0$

当$n > K$时， $P_n = 0$

其中$P_0 = 1/[\sum_{n = 0}^{s}\frac{(\lambda/\mu)^n}{n!}+\frac{(\lambda/\mu)^s}{s!}\sum^{K}_{n = s+1}(\frac{\lambda}{s\mu})^{n-s}]$

$L_q = \frac{P_0(\lambda/\mu)^{s}\rho}{s!(1-\rho)^2}[1-\rho^{K-1}-(K-s)\rho^{K-1}(1-\rho)]$

$L = \sum_{n = 0}^{s-1}nP_n+L_q+s(1-\sum_{n=0}^{s-1}P_n)$

$M/M/s/s$模型

$M/M/s/s$模型是$M/M/s/K$模型的特殊形式，即当所有服务台都被占用时，顾客会直接离开。在此模型中队列数始终为空，即不存在等待状态。