排队论（queuing theory）推论与举例

排队论 (queuing theory)，或称随机服务系统理论，是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科，也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络、生产、运输、库存等各项资源共享的随机服务系统。排队论研究的内容有 3 个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。

最初是用 3 个字母组成的符号 X/Y/Z 表示一个排队系统。其中 X 表示顾客到达时间分布，Y 表示服务时间的分布，Z 表示服务机构中的服务台的个数

1、排队模型的表示

X/Y/Z/A/B/C

X — 顾客相继到达的间隔时间的分布；

Y — 服务时间的分布(M — 负指数分布、D — 确定时间、Ek — k 阶埃尔朗分布、G — 一般随机分布、GI—一般相互独立分布)

Z — 服务台个数；

A — 系统容量限制（默认为 ∞）；

B — 顾客源数目（默认为 ∞）；

C — 服务规则（默认为先到先服务 FCFS）。

2、排队系统的衡量指标

服务队长 Ls — 正在接受服务的顾客数；期望值；

排队长 Lq — 在队列中等待的顾客数；期望值；

总队长 L = Ls + Lq — 系统中的顾客总数；期望值；

服务时间 E — 顾客在服务中消耗的时间；期望值；

等待时间 Wq — 顾客在队列中等待的时间；期望值；

总时间 Ws = E + Wq — 顾客在系统中的总逗留时间；期望值

忙期 — 服务机构两次空闲的时间间隔；

稳态 — 系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化。

服务强度： $\rho = \frac{\lambda}{s\cdot \mu }$ ；

3、排队系统的要素

（1）顾客输入过程；

（2）排队结构与排队规则；

（3）服务机构与服务规则。

顾客的输入过程

顾客源(总体)：有限/无限;
顾客到达方式：逐个/逐批;(仅研究逐个情形)
顾客到达间隔：随机型/确定型; <<<< X
顾客前后到达是否独立：相互独立/相互关联；
输入过程是否平稳：平稳/非平稳；(仅研究平稳性)

注：其中顾客到达间隔满足如下条件,则称为泊松流（满足泊松分布）：
(1) 在不相互重叠的时间区间内，到达顾客数相互独立(无后效性)；
(2) 对于充分小的时间间隔 $\left [ t,t+\Delta t \right ]$ 内，到达1个顾客的概率与t无关，仅与时间间隔成正比 (平稳性) ；
(3) 对于充分小的时间间隔 $\left [ t,t+\Delta t \right ]$ ，2个及以上顾客到达的概率可忽略不计 (普通性)。

排队结构与排队规则

顾客排队方式：等待制/即时制(损失制);
排队系统容量：有限制/无限制;
排队队列数目: 单列/多列;
是否中途退出: 允许/禁止;
是否列间转移: 允许/禁止; (仅研究禁止退出和转移的情形)

服务机构与服务规则

服务台(员)数目;单个/多个; <<<< Z
服务台(员)排列形式;并列/串列/混合;
服务台(员)服务方式;逐个/逐批;(研究逐个情形)
服务时间分布;随机型/确定型; <<<< Y
服务时间分布是否平稳:平稳/非平稳;(研究平稳情形)

其中，到达间隔和服务时间（X，Y）具有的典型分布有：

泊松分布	M
负指数分布	M
k阶爱尔朗分布	Ek
确定型分布	D
一般服务时间分布	G

归纳以上可得，经典排队系统模型（X，Y，Z，A，B，C）可表示成为：

M/M/1，M/D/1，M/ Ek /1
M/M/c， M/M/c/∞/m，
M/M/c/N/∞ ，。。。

注： $c\in (1,2\cdots ,n)$ ，M、D为上述几种分布。

4、模型的系统运行状态参数：

系统状态 N(t) —— 指排队系统在时刻t时的全部顾客数N(t)，包括“排队顾客数”（Lq）和“正被服务顾客数”（Ls）；

系统状态概率：

(1)瞬态概率Pn(t)
——表示时刻t系统状态 N(t)=n 的概率（也就是顾客到达数为n的概率分布）;
(2)稳态概率Pn
—— $P_{n}=\lim_{t\rightarrow \infty }P_{n}(t)$
——一般排队系统运行了一定长的时间后，系统状态的概率分布不再随时间 t变化，即初始时刻（t=0）系统状态的概率分布 (Pn(0) ，n>>0）的影响将消失。

公式推导过程：

总结上述

可知泊松流到达间隔服从负指数分布：

若顾客到达间隔T的概率密度为
$f_{T}(t)=\begin{cases} & \lambda e^{-\lambda t} ,t\geq 0\\ & \0\; \; \; \; \; ,t<0 \end{cases}$
则成T服从负指数分布，分布函数为：
$F_{T}(t)=\begin{cases} & 1-\lambda e^{-\lambda t} ,t\geq 0\\ & \0\; \; \; \; \; \; \; \; \; \; \; ,t<0 \end{cases}$
若顾客流是泊松流时，顾客到达的时间间隔服从上述负指数分布。
其中，E[T]=1/λ ; Var [T]=1/λ2 ; σ [T]=1/λ
λ 为单位时间顾客到达数的期望，称为平均到达率；1/λ 为平均间隔时间。

顾客服务时间分布（负指数分布）

对一个顾客的服务时间Ts，等价于相邻两个顾客离开排队系统的时间间隔。若Ts服从负指数分布，其概率密度函数为： $f_{T_{s}}(t)=\begin{cases} & \mu e^{-\mu t} ,t\geq 0\\ & \0\; \; \; \; \; ,t<0 \end{cases}$
分布函数为：
$f_{T_{s}}(t)=\begin{cases} & 1-\mu e^{-\mu t} ,t\geq 0\\ & \0\; \; \; \; \; \; \; \; \; \; \; \;,t<0 \end{cases}$
则 E[Ts]=1/µ ; Var [Ts]=1/ µ 2 ; σ [Ts]=1/ µ
E[Ts]=1/µ ：每个顾客的平均(期望)服务时间； µ:单位时间服务的顾客数，平均(期望)服务率；
其中μ 为平均服务率，1/μ 为平均服务时间。

5、M/M/1模型：

1、模型的条件是：

1、输入过程――顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从泊松分布，且是平稳的；
2、排队规则――单队，且队长没有限制，先到先服务；
3、服务机构――单服务台，服务时间的长短是随机的，服从相同的指数分布。

2、对于M／M／1模型有如下公式：

$P_{0}=1-\rho$	$P_{n}=\rho ^{n}(1-\rho)$
$L_{s}=\frac{\lambda }{\mu -\lambda}= \frac{\rho}{1-\rho}$	$L_{q}=\frac{\lambda ^{2}}{\mu (\mu-\lambda)}=\frac{\rho^{2}}{1-\rho}=L_{s}\rho$
$W_{s}=\frac{1}{\mu-\lambda}$	$W_{q}=\frac{\lambda}{\mu(\mu-\lambda)}=W_{s}\rho$

注：（橙色标注为可做评价类指标）

$P(N>k)=\rho^{k+1}$ ：N>k的概率为P；
N(t)：系统顾客数；
P0：系统处于没有顾客来到要求服务的概率
系统负荷水平 ρ ：它是衡量服务台在承担服务和满足需要方面能力的尺度；
总队长Ls：系统中排队等待服务和正在服务的顾客总数，其平均值；
队长Lg：系统中排队等待服务的顾客数，其平均值；
逗留时间Ws：一个顾客在系统中停留时间，包括等待时间和服务时间，其平均值；
等待时间Wg：一个顾客在系统中排队等待时间，其平均值。
λ为平均到达率，1/λ 为平均间隔时间；
μ为平均服务率，1/μ 为平均服务时间。

3、举例

某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。试对此排队队系统进行分析。

（1）先确定参数值：这是单服务台系统，有：
λ=3人/h µ =60/15=4人/h
故服务强度为：
$\rho =\frac{\lambda}{\mu}=\frac{3}{4}=0.75$

（2）计算稳态概率：P0=1-ρ，也就是急诊室空闲的概率；
繁忙的概率服从二项分布：ρ=1-P0=0.75
（3）急症室总病人数平均值： $L_{s}=\frac{\lambda}{\mu-\lambda}$
急症室排队等待人数： $L_{q}=L_{s}\rho$
病人在急症室逗留时间： $W_{s}=\frac{1}{\mu-\lambda}$
病人平均等候时间： $W_{q}=W_{s}\rho$

6、M/M/S模型

1、模型的条件是：

此模型与M/M/1模型不同之处在于有S个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时，S个服务台都忙着，则排成一队等待，先到先得（FCFS）服务的单队模型；
可以看做是s个M/M/1模型组合。
整个系统的平均服务率为sμ，ρ*＝λ/sμ，（ρ*<1）为该系统的服务强度。

2、对应M/M/S有如下公式：

（1）状态概率：
$\large P_{0}=\left [ \sum_{k=0}^{s-1}\frac{1}{k!} (\frac{\lambda}{\mu})^{k}+\frac{1}{s!}\frac{1}{1-\rho^{*}}(\frac{\lambda}{\mu})^{s}\right ]^{-1}$
$\large P_{n}=\begin{cases} & \frac{1}{n!}(\frac{\lambda}{\mu})^{n}P_{0}\; \; \; \; \;0<n\leq s\\ & \frac{1}{s!s^{n-s}}(\frac{\lambda}{\mu})^{n}P_{0}\;\;\;\;n\geq s \end{cases}$

（2）主要运行指标：

$\large L_{q}=\frac{(s\rho^{*})^{s}\rho^{*}}{s!(1-\rho^{*})^{2}}P_{0}$ $\large L_{s}=L_{q}+s\rho^{*}$
$\large W_{q}=\frac{L_{q}}{\lambda}$ $\large W_{s}=\frac{L}{\lambda}=W_{q}+\frac{1}{\mu}$

（3）系统状态 $N\geq S$ 的概率：
$\large P(N\geq k)=\sum_{n=k }^{\infty}P_{n}=\frac{\rho^{k}}{k!(1-\rho^{*})}P_{0}$

3、举例

某医院挂号室有三个窗口，就诊者的到达服从泊松分布，平均到达率为每分钟0.9人，挂号员服务时间服从指数分布，平均服务率每分钟0.4人，现假设就诊者到达后排成一队，依次向空闲的窗口挂号，显然系统的容量和顾客源是不限的，属于M/M/S型的排队服务模型。求：该系统的运行指标：Po、Lq、L、W、Wq、P(N≥3)。

由题可得：s=3；λ=0.9人/min；μ=0.4人/min；
ρ=0.9/0.4=2.25；ρ*＝λ/sμ=ρ/s=2.25/3=3/4

代入上列公式可得：Po、Lq、L、W、Wq、P。