【管理运筹学】第 10 章 | 排队论（1，排队论的基本概念）

---

引言

开一点排队论的内容吧，方便做题。

排队论（Queuing Theory）也称随机服务系统理论，是为解决一系列排队问题（如日常购物结算排队、电话占线问题、车站堵塞和疏导问题等）而发展的一门学科。

---

一、基本概念

1.1 排队过程

下图是排队过程的一般模型。来自顾客源（总体）的顾客到达服务机构（服务台）前排队等候服务，接受服务后离开。排队结构指队列的数目和排队方式，排队规则和服务规则说明顾客在排队系统中按怎样的规则、次序接受服务。排队系统包括下图中虚线所包括的部分。

1.2 排队系统的组成和特征

一般的排队系统都由输入过程、排队规则、服务机构 3 个基本部分组成。

1. 输入过程

输入过程是描述顾客来源以及顾客按什么规律到达排队系统的，它包括以下三个方面：

（1）顾客来源。顾客总体的组成可能是有限的，也可能是无限的。

（2）顾客到达方式。顾客到来可能是一个个的，也可能是成批的。

（3）顾客流的概率分布。顾客一个（批）一个（批）来到排队系统，相继到达的顾客之间的间隔时间分布是确定的还是随机的，分布参数是什么，到达的间隔时间是否相互独立，分布是随时间变化还是平稳的。

2. 排队规则

排队规则是描述顾客来到服务系统时，服务机构是否允许排队，顾客是否愿意排队，在排队等待情况下服务的顺序是什么？一般可分为损失制、等待制和混合制三大类。

损失制：顾客到达时，如果所有的服务台均被占用，且服务机构由不允许顾客等待，顾客只能离去。

等待制：顾客达到时，如果所有服务台均被占用，这是顾客自动加入队列等待服务，服务完才离开。有先到先服务、后到先服务、随机服务和优先服务等情形。

3. 服务机构

服务机构主要描述服务台的数目即服务规律。服务机构由多个时，服务方式有并列的、串列的、还有混合的；接受服务的顾客可以是单个的也可以是成批的；服务时间可以是固定的，也可以是随机的；顾客接受服务的时间是否独立等。

1.3 排队模型的分类

为描述排队系统，1953 年 D.G.Kendall 提出了一个分类办法，考虑了排队系统中最主要的、影响最大的三个因素：顾客相继到达的间隔时间分布、服务时间的分布、服务台个数。

按照这三个特征用一定符号表示随机服务系统的种类，称为 Kendall 符号，符号形式为：$$X/Y/Z$$ 其中，$X$ 处填写顾客相继到达间隔时间的分布；$Y$ 处填写服务时间的分布；$Z$ 处填写并列的服务台个数。

一般表示相继到达间隔时间和服务时间分布的随机分布符号是：

$M$ —— 负指数分布（Markov）；
$D$ —— 确定性（Deterministic）；
$E_k$ —— $k$ 阶爱尔朗（Erlang）分布；
$GI$ —— 一般相互独立（General Independent）；
$G$ —— 一般服务时间的分布。

例如，$M/M/1$ 表示到达间隔时间服从负指数分布、服务时间服从负指数分布、单服务台的模型；$D/M/c$ 表示到达间隔时间确定、服务时间服从负指数分布、$c$ 个平行服务台（顾客是一队）的模型。

1971 年关于排队论符号标准化会议上决定，将 Kendall 符号进行扩充，表示成 $X/Y/Z/A/B/C$ 。其中前三项意义不变，而 $A$ 表示系统容量限制 $N$ ；$B$ 表示顾客源数目 $m$ ；$C$ 处填写服务规则，如先到先服务（FCFS,first come first serve）。

并约定，如果省略后三项，指的是 $X/Y/Z/\infty /\infty /FCFS$ 的情形。考试范围，只讨论 FCFS 的情形，故第六项也可省略。

1.4 系统指标

研究排队系统的目的，是把握排队系统运行的效率，估计服务质量，确定系统参数的最优值，最终目的是确定排队系统的结构是否合理以及设计改进措施等，所以必须确定用以判断系统运行优劣的基本数量指标，有如下这些。

1. 队长，指在系统中的顾客数（包括在队列中等待服务的顾客和正在接受服务的顾客），它的期望值记作 $L_s$ ；
2. 排队长，指在系统中排队等候服务的顾客数，它的期望值记作 $L_q$ ；
3. 逗留时间，指一个顾客在排队系统的停留时间，它的期望值记作 $W_s$ ；
4. 等待时间，指一个顾客在系统中排队等候的时间，它的期望值记作 $W_q$ 。

在机器故障问题中，无论是等待修理或正在修理，都会使工厂受到损失，因此逗留时间（停工时间）是最被关心的；而一般购物、诊断等排队问题中，顾客常关心的是等待时间。

忙期（Busy Period）是指从顾客到达空闲的服务机构起到服务机构再次变为空闲为止的这段时间的长度，即服务机构连续繁忙的时间长度，它关系到服务员的工作强度。忙期和一个忙期中平均完成服务的顾客数都是衡量服务机构效率的指标。

在即时制或排队有限制的情形，由于顾客被拒绝而使企业受到损失的损失率及以后经常遇到的服务强度等，都是很重要的指标。

1.5 系统状态

系统状态指的是系统中的顾客数，如系统中有 $n$ 个顾客，就说系统的状态是 $n$ ，它的可能值是：

1. 队长无限制时，$n=0,1,2,\cdots ;$
2. 队长有限制且最大数为 $N$ 时，$n=0,1,2,\cdots ,N;$
3. 即时制，服务台个数是 $c$ 时，$n=0,1,2,\cdots ,c$ 。

系统状态的概率一般是随时刻 $t$ 变化的，时刻 $t$ 、状态为 $n$ 的概率用 $P_n(t)$ 表示。

计算状态概率 $P_n(t)$ ，首先要建立起含 $P_n(t)$ 的关系式，因 $t$ 是连续变量，而 $n$ 只能取非负整数，所以一般 $P_n(t)$ 的关系式为差分微分方程（关于 $t$ 的微分方程，关于 $n$ 的差分方程）。方程的解称为瞬态（或过渡状态，Transient State）解。求瞬态解比较困难，即使求出也很难利用，因此常用它的极限（如果存在）$$\underset{t\to \infty }{\lim }{p}_n(t)=p_n.$$ 称其为稳态（Steady State），或称为平衡状态（Statistical Equilibrium State）的解。

稳态的物理含义是，当系统运行了无限长时间后，初始（$t=0$）状态的概率分布（$P_n(0),n\ge 0$）的影响将消失，而且系统的状态概率分布不再随时间变化。在实际应用中，大多数系统会很快趋于稳态（如下图所示），而无须等到 $t\to \infty$ 。但永远达不到稳态的情形也是存在的。

求稳态概率 $P_n(t)$ 时，不一定求 $t\to \infty$ 时 $P_n(t)$ 的极限，而只需对时间的一阶导 $P_n^{\prime }(t)=0$ 即可。