1.1 排队过程的一般表示

下图是排队论的一般模型。

图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。

凡要求服务的对象统称为顾客，为顾客服务的人或物称为 服务员 ，由顾客和服务员组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。因此，顾客总希望服务机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权衡决策，使其达到合理的平衡。

2 排队系统的组成和特征

一般的排队过程都由 输入过程、排队规则、服务过程 三部分组成，现分述如下：

2.1 输入过程

输入过程是指 顾客到来时间的规律性 ，可能有下列不同情况：

（i）顾客的组成可能是有限的，也可能是无限的。

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

（iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。

（iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。

2.2 排队规则

排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制三种。

（i） 损失制（消失制） 。当顾客到达时，所有的服务台均被占用，顾客随即离去。

（ii） 等待制 。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。

例如出故障的机器排队等待维修就是这种情况。

（iii） 混合制 。介于损失制和等待制之间的是混合制，即既有等待又有损失。有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。

排队方式还分为单列、多列和循环队列。

2.3 服务过程

（i）服务机构。

主要有以下几种类型：单服务台；多服务台并联（每个服务台同时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。

（ii）服务规则。

按为顾客服务的次序采用以下几种规则：

①先到先服务，这是通常的情形。

②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理。

③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。

④优先服务，如医疗系统对病情严重的病人给予优先治疗。

3 排队模型的符号表示

排队模型用六个符号表示，在符号之间用斜线隔开，即 X /Y / Z / A/ B /C 。

第一个符号 X 表示 顾客到达流或顾客到达间隔时间的分布 ；

第二个符号Y 表示 服务时间的分布 ；第三个符号 Z 表示 服务台数目 ；

第四个符号 A 是 系统容量限制 ；第五个符号 B 是 顾客源数目 ；第六个符号C 是 服务规则 ，

如 先到先服务 FCFS ，后到先服务 LCFS 等。并约定，如略去后三项，即指 X /Y / Z / ∞ / ∞ / FCFS的情形。

我们只讨论先到先服务 FCFS 的情形，所以略去第六项。

表示顾客到达间隔时间和服务时间的分布的约定符号为：

M — 指数分布 （ M 是 Markov 的字头，因为指数分布具有 无记忆性，即 Markov 性 ）；

D — 确定型（Deterministic） ；

$\large {E_{k}}$ — k 阶爱尔朗(Erlang)分布 ；

G — 一般（general）服务时间的分布 ；

GI — 一般相互独立（General Independent）的时间间隔的分布 。

例如， M / M /1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统。

D / M / c 表示确定的到达时间、服务时间为指数分布、 c 个平行服务台（但顾客是一队）的模型。

4 排队系统的运行指标

为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指标，这些数量指标通常是：

(i) 平均队长 ：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的数学期望，记作 Ls 。

(ii) 平均排队长 :指系统内等待服务的顾客数的数学期望，记作 Lq 。

(iii) 平均逗留时间 ：顾客在系统内逗留时间（包括排队等待的时间和接受服务的时间）的数学期望，记作Ws 。

（iv） 平均等待时间 ：指一个顾客在排队系统中排队等待时间的数学期望，记作 Wq 。

（v） 平均忙期 ：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机构再次空闲止的时间）长度的数学期望，记为Tb 。

还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等，这些都是很重要的指标。

计算这些指标的基础是表达系统状态的概率。所谓 系统的状态即指系统中顾客数 ，如果系统中有n 个顾客就说系统的状态是n ，它的可能值是

3 输入过程与服务时间的分布

排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服务时间不可能是负值，因此，它的分布是非负随机变量的分布。最常用的分布有 泊松分布、确定型分布，指数分布和爱尔朗分布。

3.1 泊松流与指数分布

在上述条件下，我们研究顾客到达数n 的概率分布。

对于泊松流, λ 表示单位时间平均到达的顾客数,所以 $\large \frac{1}{\lambda }$ 就表示相继顾客到达平均间隔时间，而这正和 ET 的意义相符。对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从指数分布。这时设它的分布函数和密度函数分别是

3.2 常用的几种概率分布及其产生

3.2.1 常用的连续型概率分布

我们只给出这些分布的参数、记号和通常的应用范围，更详细的内容参看专门的概率论书籍。

（i）均匀分布

区间 (a,b) 内的均匀分布记作U(a,b) 。服从U(0,1) 分布的随机变量又称为随机数，它是产生其它随机变量的基础。如若 X 为U(0,1) 分布，则Y = a + (b − a)X 服从 U(a,b) 。

（ii）正态分布

正态分布还可以作为 二项分布一定条件下的近似 。

（iii）指数分布

（iv）Gamma 分布、爱尔朗分布

Gamma 分布又称爱尔朗分布。

Gamma 分布是双参数α,β 的非对称分布，记作G(α,β ) ，期望是αβ 。α = 1时蜕化为指数分布。 n 个相互独立、同分布（参数 λ ）的指数分布之和是 Gamma 分布（α = n, β = λ) 。Gamma 分布可用于服务时间，零件寿命等。

（v）Weibull 分布

Weibull 分布是双参数α,β 的非对称分布，记作W(α, β ) 。α = 1时蜕化为指数分布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用。

（vi）Beta 分布

Beta 分布是区间(0,1) 内的双参数、非均匀分布，记作 B(α, β ) 。

2.2.2 常用的离散型概率分布

（i）离散均匀分布

（ii）Bernoulli 分布（两点分布）

Bernoulli 分布是 x = 1,0 处取值的概率分别是 p 和1− p 的两点分布，记作 Bern( p) 。用于基本的离散模型。

（iii）泊松（Poisson）分布

泊松分布与指数分布有密切的关系。当顾客平均到达率为常数 λ 的到达间隔服从指数分布时，单位时间内到达的顾客数 K 服从泊松分布，即单位时间内到达 k 位顾客的概率为

记作 Poisson(λ) 。泊松分布在排队服务、产品检验、生物与医学统计、天文、物理等领域都有广泛应用。

（iv）二项分布

在独立进行的每次试验中，某事件发生的概率为 p ，则 n 次试验中该事件发生的次数 K 服从二项分布，即发生k 次的概率为

记作 B(n, p) 。二项分布是n 个独立的 Bernoulli 分布之和。它在产品检验、保险、生物和医学统计等领域有着广泛的应用。

当n,k 很大时， B(n, p) 近似于正态分布 N(np,np(1− p)) ；

当n 很大、 p 很小，且np 约为常数λ 时， B(n, p) 近似于 Poisson(λ)。

排队论模型（一）：基本概念、输入过程与服务时间的常用概率分布

排队论模型（二）：生灭过程、 M / M /s 等待制排队模型、多服务台模型

排队论模型（三）：M / M / s/ s 损失制排队模型

排队论模型（四）：M / M / s 混合制排队模型

排队论模型（五）：有限源排队模型、服务率或到达率依赖状态的排队模型

排队论模型（六）：非生灭过程排队模型、爱尔朗（Erlang）排队模型

排队论模型（七）：排队系统的优化

排队论模型（八）：Matlab 生成随机数、排队模型的计算机模拟

M/M/1队列系统是最基本也是最重要的一种队列系统，该系统是一个单队列单服务器系统，其中M代表Markovian。M/M/1队列系统包含以下几个部分： 1. 请求到达时间满足满足Passion 分布（强度为）； 2. 服务时间呈指数分布（均值为，为服务率）； 3. 一个服务器； 4.一个无限长度的缓冲区。M/M/1队列系统的理论结果：文章目录一、算法介绍1.算法介绍2. 模型介绍二、适用问题三、算法总结1.M/M/1 排队系统2.M/M/S 排队系统四、应用场景举例1.M/M/1 排队系统2.M/M/S 排队系统12.M/M/S 排队系统2五、MATLAB代码1.M/M/12.M/M/S六、实际案例七、论文案例片段（待完善）排队论主要针对数学建模问题中的一些小的子问题进行求解，如果想直接使用请跳转至——四、五一、算法介绍 1.算法介绍排队论发源于上世纪初。当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。排队论起源于1909年丹麦电话工程师A.K.爱尔朗的工作，他对电话通过拥挤问题进行了研究。1917年，爱尔朗发表了他的著名文章——“自动电话交换中的概率论的几个问题的解决”。排队论已广泛应用于军事、运输、维修、生产、服务、库存、医疗卫生、教育、水利灌溉之类的问题，显示了强大的生命力。排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常需要排队。此时要求服务的数量超过服务机构（服务台，服务员等）的容量。也就是说，到达的顾客不能立即得到服务，因而出现了排队现象。... 一.随机过程（Stochastic Process）： 1.定义：设随机实验的样本空间S={s}，如果对于每个s，有对应属于参数集T的参数t的函数X(s,t)，那么对于所有的s，得到一组t的函数{X(s,t),t∈T}，这个t的函数族称为随机过程，简记为X(s,t)或X(t)。族中的每个函数称为该过程的一个样本，它是随机过程一次试验的物理实现，是一个确知的时间函数，称为样本函数或样本曲线。 01 排队论背景与发展介绍排队论最早起源于对电话通讯排队接线的研究，早在1909年，丹麦数学家A. K. Erlang 发表了The Theory of Probabilities and Telephone Conversations 初步产开了对由于随机需求的出现而产生非稳态队列的现象的研究。在他后期的工作中，他发现了几个重要结论: 自动电话通讯系统可以以两种基本概率模型模拟: 1. 泊松输入，指数分布服务时间，多服务流 2. 泊松输入 , 稳定常态服务时间，单服务流。Erlang亦提出队列稳态平衡的概这两个模型假设顾客抵达与服务时间为指数分布，时间流程为泊松过程， The Birth-and-Death Process. 为了得出M/M/1 及 M/M/S的一般公式，笔者认为有必要简单推导下…… 该模型为连续时间马尔可夫过程 (continuous time Markov chain)，要介绍全很困难，这里就给一个简易推导。在排队论中，“生” 指的是客抵达系统，“灭”指的是客离开系统，生灭过程的系统状态 N（t）此时顾客在t时候的顾客数量排队论解决的问题排队论也称随机服务系统理论，排队论又叫随机服务系统理论或公用事业管理中的数学方法。它是研究各种各样的排队现象的。它所要解决的主要问题是:在排队现象中设法寻求能够达到服务标准的最少设备,使得在满足服务对象条件下，服务机构的花费最为经济,使服务系统效率最高。排队现象作为一种随机现象，所采用的主要工具是研究随机现象规律的概率论。它把所需研究的问题形象地描述成顾客（如电话用户、发生故障的机床等）来到服务台前（如电话线路维修工人等)要求接待，如果“ 服务台”已被其他顾客占用，那么就得排队论模型（一）：基本概念、输入过程与服务时间的常用概率分布排队论模型（二）：生灭过程、 M / M /s 等待制排队模型、多服务台模型排队论模型（三）：M / M / s/ s 损失制排队模型排队论模型（四）：M / M / s 混合制排队模型排队论模型（五）：有限源排队模型、服务率或到达率依赖状态的排队模型排队论模型（六）：非生灭过程排队模型、爱尔朗（Erlang）排队 ...