排队理论简介

本文参考文献为Вентцель Е. С.的《Исследование операций》。

1. 理论背景

排队理论又称大众服务理论，顾名思义指的是在有限的服务条件下服务大量人员的一种理论情景。日常生活中常见的场景如，排队的电话亭、等待理发的顾客、售票窗口、商店结账处等等。

显然，这些排队情景中都有一些共性。如：

1. 每个排队情景必然包括若干“服务人员”，称之为服务通道。一个排队情景中可以有一个或多个服务通道。
2. 每个排队情景中必然也包括若干申请流（或称请求流），这些请求在某个随机时刻进入该排队系统。
3. 当前正在处理的申请会占据一定的时间，在这段时间之后，处理该申请的通道会“放空”并等待处理下一个申请。
4. 当有多余的申请等待处理时，该申请有2种情况：要么等待被处理，形成“队列”（即排队），要么离开该服务通道。
5. 除4中的情况外，一个服务通道还可能处于非满载状态或停工状态。

一个服务通道能够成功处理的申请数，称为通过性。而排队理论研究的正是申请流、服务通道数量、服务通道的工作能力、排队系统的工作规则、工作效率等问题。

一般地，衡量一个排队系统的效率特征可以用以下的方式：

• 单位时间内可以处理的申请平均数量；
• 无法被满足、使排队系统无法服务的申请所占的百分比；
• 提交的申请能及时被处理的概率；
• 排队等候的平均用时；
• 等候用时的时长的分布律；
• 申请队列中的申请平均数量；
• 队列中申请数量的分布律；
• 单位时间内排队系统带来的平均收入。

2. 研究的数学方法

如果排队系统中的随机过程是马尔科夫过程，那么对排队系统的数学建模将会很简单。而如果排队系统中的过程确实是马尔科夫过程，那么逐个发生的事件流必须是泊松过程，即每个单独的事件都没有相应的后果或后续动作。对于排队过程来说，即需要申请流和服务流都满足泊松过程。然而业已证明，排队系统越复杂，服务通道越多，则越可以近似于马尔科夫过程。因此，采用马尔科夫过程研究排队理论并无大碍。

在研究排队过程之前，需要知道系统中的几个基本参数。
$n$ – 服务通道数量；
$\lambda$ – 申请流的强度；
$\mu$ – 每个服务通道的处理能力（工作产能），即每个服务通道单位时间内可处理的申请的平均数量；
形成排队的条件（若存在）。

设排队系统中的申请流和服务流都是泊松过程，且为定常的，参数不随时间变化。而每2个事件之间的时间间隔$T$是随机变量，其分布满足如下概率分布密度函数：
$$f(t)=\lambda {\mathrm{e}}^{-\lambda t}(t>0)$$

3. 拒绝型排队系统与等候型排队系统

排队系统分为2类：

• 拒绝型。当所有服务通道都被占用时，新的申请会被拒绝，离开排队系统并之后不再参与进来。
• 等候型。当所有服务通道都被占用时，新的申请加入等候队列。当某个通道处理完上一个申请变为空时，就从等候队列中转移一个申请至该通道并处理。

接下来将着重讲解拒绝型排队系统的数学模型。

4. 拒绝型排队系统

对于拒绝型排队系统来说，衡量其效率的指标称为绝对通过性，指的是单位时间内系统可以处理的申请的平均数量。与之对应的概念是相对通过性，指单位时间内被系统处理的申请的平均数，与该时间段内新增的申请数之比值。

设系统中有$n$个服务通道。根据被占用的通道的个数，将系统的状态分为如下几类：
$S_0$ – 所有服务通道都空；
$S_1$ – 只有一个服务通道被占用，其他通道都空；
$\cdots$
$S_k$ – 有$k$个通道被占用，其他通道都空；
$\cdots$
$S_n$ – 所有$n$个通道都被占用。

如下图所示是拒绝型排队系统的示意图。

一开始系统中没有申请，所有服务通道为空，系统状态为$S_0$。当有一个申请加入时，占用一个服务通道，系统状态从$S_0$变为$S_1$，即$S_0\to S_1$，此过程的强度（或密度）为$\lambda$，可以理解为单位时间内新增了$\lambda$个申请。以此类推，直到所有$n$个通道均被占用。从低占用向高占用转化的过程中，每个状态转化的强度都是$\lambda$。

当系统处于$S_1$状态，而该申请被完成时，系统将变成$S_0$状态，即$S_1\to S_0$。此过程的强度（或密度）为$\mu$，可以理解为一个被占用的服务通道单位时间内可以服务$\mu$个申请。值得注意的是，从高占用向低占用转化的过程的强度并非全是$\mu$，如图所示，$S_{k+1}\to S_k$过程的强度为$\left(k+1\right)\mu$。

利用柯尔莫哥洛夫方程，对图中每个状态的“入量”和“出量”进行描述，可以得到每个状态的柯尔莫哥洛夫方程。如，对于某个状态$S_k$来说，其“出量”（即图中从方块$S_k$发出的箭头）有两个，分别是方块$S_k$右上的$\lambda$和左下的$k\mu$；而“入量”（即图中进入方块$S_k$的箭头）也有2个，分别是方块$S_k$左上的$\lambda$和右下的$(k+1)\mu$。那么，状态$S_k$的概率可以描述为
$$\frac{\mathrm{d}{p}_k}{\mathrm{d}t}=-\left(\lambda +k\mu \right)p_k+\lambda p_{k-1}+(k+1)\mu p_{k+1}$$上式的含义是：

1. 所有方块$S_k$的出量均为负项，而入量为正项；
2. 出量有2个：1) 右上的$\lambda$从$S_k$出发，其概率为$p_k$，故该项是$-\lambda p_k$；2) 左下的$k\mu$也从$S_k$出发，其概率也是$p_k$，故该项是$-k\mu p_k$。
3. 入量有2个：1) 右下的$(k+1)\mu$从上一个状态$S_{k+1}$出发，其概率对应是$p_{k+1}$，故该项是$(k+1)\mu p_{k+1}$；2) 左上的$\lambda$从上一个状态$S_{k-1}$出发，其概率对应是$p_{k-1}$，故该项是$\lambda p_{k-1}$。
4. 注意：从哪个方块$S_i$出发，概率$p_i$的下标就要和方块的下标对应！概率$p_i$取决于箭头的出发地而不是指向地！

由此可以写出图中的微分方程关系：
$$\begin{array}{rl}\frac{\mathrm{d}{p}_0}{\mathrm{d}t}& =-\lambda p_0+\mu p_1\\ \frac{\mathrm{d}{p}_1}{\mathrm{d}t}& =-\left(\lambda +\mu \right)p_1+\lambda p_0+2\mu p_1\\ ⋮& \\ \frac{\mathrm{d}{p}_k}{\mathrm{d}t}& =-\left(\lambda +k\mu \right)p_k+\lambda p_{k-1}+(k+1)\mu p_{k+1}\\ ⋮& \\ \frac{\mathrm{d}{p}_n}{\mathrm{d}t}& =-n\mu p_n+\lambda p_{n-1}\end{array}\text{\hspace{1em}(1)}$$上述方程称为艾拉姆咖方程。初始条件为
$$p_0(0)=1,p_1(0)=p_2(0)=\cdots =p_n(0)=0$$艾拉姆咖方程往往无法手解，需要通过计算机辅助求解，得到结果$p_i(t)$为每种状态出现的概率。

另外，在实际运用中往往还感兴趣状态的边界概率，指系统的稳态模式下的概率。这里不加推导地给出公式：
$$\begin{gathered} p_k=\frac{{\lambda }^k}{\mu \cdot 2\mu \cdots k\mu }{p}_0=\frac{{\left(\lambda /\mu \right)}^k}{k!}{p}_0 \\ {p}_0=\frac{1}{1+\frac{\lambda /\mu }{1!}+\frac{{\left(\lambda /\mu \right)}^2}{2!}+\cdots +\frac{{\left(\lambda /\mu \right)}^n}{n!}} \end{gathered}$$记$$\lambda /\mu =\rho$$称为换算强度，其物理意义是：在处理一个请求的平均时长内，到来（新增）的请求的平均数量。

则上述边界概率公式可改写为
$$p_k=\frac{{\rho }^k}{k!}{p}_0$$$$p_0=\frac{1}{1+\frac{\rho }{1!}+\frac{{\rho }^2}{2!}+\cdots +\frac{{\rho }^n}{n!}}\text{\hspace{1em}(2)}$$式(2)同样称为艾拉姆咖方程。

显然，所有通道都被占用的概率是$p_n$，那么“新增申请能够被处理”的概率为
$$q=1-p_n$$进而绝对通过性为
$$A=\lambda q=\lambda \left(1-p_n\right)$$则繁忙通道的平均个数$\bar{k}$可以表示为加权和：
$$\bar{k}=0\cdot p_0+1\cdot p_1+\cdots +n\cdot p_n$$即为数学期望。
另一方面，由于绝对通过性表示单位时间内处理的申请的平均数量，而一个被占用的服务通道在单位时间内可以处理$\mu$个申请，故繁忙通道的平均个数亦可表示为
$$\bar{k}=\frac{A}{\mu }=\frac{\lambda \left(1-p_n\right)}{\mu }=\rho \left(1-p_n\right)$$