排队理论简介-Toy模板网

这篇具有很好参考价值的文章主要介绍了排队理论简介。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

1. 理论背景

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

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

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

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

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

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

2. 研究的数学方法

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

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

设排队系统中的申请流和服务流都是泊松过程，且为定常的，参数不随时间变化。而每2个事件之间的时间间隔 $T$ 是随机变量，其分布满足如下概率分布密度函数：
$\lambda {\rm e}^{-\lambda t} \quad (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 \rightarrow S_1$ ，此过程的强度（或密度）为 $\lambda$ ，可以理解为单位时间内新增了 $\lambda$ 个申请。以此类推，直到所有 $n$ 个通道均被占用。从低占用向高占用转化的过程中，每个状态转化的强度都是 $\lambda$ 。

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

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

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

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

另外，在实际运用中往往还感兴趣状态的边界概率，指系统的稳态模式下的概率。这里不加推导地给出公式：
$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!} }$ 记 $\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!} } \tag{2}$ 式(2)同样称为艾拉姆咖方程。

显然，所有通道都被占用的概率是 $p_n$ ，那么“新增申请能够被处理”的概率为
$q = 1 - p_n$ 进而绝对通过性为
$\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)$ 文章来源地址https://www.toymoban.com/news/detail-611144.html