排队论模型及其应用

排队系统的符号表述

描述符号：① / ② / ③ / ④ / ⑤ / ⑥

各符号的意义：

①——表示顾客相继到达间隔时间分布，常用下列符号：

M ——表示到达的过程为泊松过程或负指数分布；

D ——表示定长输入；

EK ——表示 K 阶爱尔朗分布；

G ——表示一般相互独立的随机分布。

②——表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。

③——表示服务台 ( 员 ) 个数：“ 1 ”表示单个服务台，“ s ” (s>1) 表示多个服务台。

④——表示系统中顾客容量限额，或称等待空间容量。如系统有 K 个等待位子，则， 0

⑤——表示顾客源限额，分有限与无限两种，∞表示顾客源无限，一般∞也可省略不写。

⑥——表示服务规则，常用下列符号

FCFS ：表示先到先服务的排队规则；

LCFS ：表示后到先服务的排队规则；

PR ：表示优先权服务的排队规则。

二、排队系统的主要数量指标

描述一个排队系统运行状况的主要数量指标有：

1．队长和排队长 (队列长)

队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)；排队长是指系统中正在排队等待服务的顾客数。队长和排队长一般都是随机变量。

2．等待时间和逗留时间

从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。等待时间是个随机变量。从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。

3. 忙期和闲期

忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，是服务员最为关心的指标，因为它关系到服务员的服务强度。与忙期相对的是闲期,即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。

4．数量指标的常用记号

(1)主要数量指标

L —— 平均队长，即稳态系统任一时刻的所有顾客数 的期望值；

L q —— 平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值；

W —— 平均逗留时间，即(在任意时刻)进入稳态系统的顾客逗留时间的期望值；

W q —— 平均等待时间，即(在任意时刻)进入稳态系统的顾客等待时间的期望值。

(2)其他常用数量指标

s —— 系统中并联服务台的数目；

λ —— 平均到达率；

1／λ —— 平均到达间隔；

μ —— 平均服务率；

1/μ —— 平均服务时间；

N――稳态系统任一时刻的状态（即系统中所有顾客数）；

U――任一顾客在稳态系统中的逗留时间；

Q――任一顾客在稳态系统中的等待时间；

ρ —— 服务强度，即每个服务台单位时间内的平均服务时间， — 般有ρ = λ／ (s μ ) ，这是衡量排队系统繁忙程度的重要尺度，当ρ趋近于 0 时，表明对期望服务的数量来说，服务能力相对地说是很大的。这时，等待时间一定很短，服务台有大量的空闲时间；如服务强度ρ趋近于 1 ，那么服务台空闲时间较少而顾客等待时间较多。我们一般都假定平均服务率μ大于平均到达率λ，即λ / μ <1, 否则排队的人数会越来越多，以后总是保持这个假设而不再声明。

李特尔公式

在系统达到稳态时，假定平均到达率为常数λ，平均服务时间为常数 1/ μ，则有下面的李特尔公式：

L=λ W

Lq=λ Wq

W= Wq +1/μ

L= Lq +λ/μ

排队系统运行情况的分析

排队系统运行情况的分析，就是在给定输入与服务条件下，通过求解系统状态为 n( 有 n 个顾客 ) 的概率 Pn ，再进行计算其主要的运行指标：

①系统中顾客数 ( 队长 ) 的期望值 L ；

②排队等待的顾客数 ( 排队长 ) 的期望值 Lq ；

③顾客在系统中全部时间 ( 逗留时间 ) 的期望值 W ；

④顾客排队等待时间的期望值 Wq 。

第三节 M ／ M ／ 1 模型

模型的条件是：

1 、输入过程――顾客源是无限的，顾客到达完全是随机的，单个到来，到达过程服从普阿松分布，且是平稳的；

2 、排队规则――单队，且队长没有限制，先到先服务；

3 、服务机构――单服务台，服务时间的长短是随机的，服从相同的指数分布。

第四节  M / M / S 模型

● 此模型与 M/M/1 模型不同之处在于有 S 个服务台，各服务台的工作相互独立，服务率相等，如果顾客到达时， S 个服务台都忙着，则排成一队等待，先到先服务的单队模型。

● 整个系统的平均服务率为 sμ ， ρ * ＝ λ/sμ ，（ ρ * <1 ）为该系统的服务强度。

几个连续型分布 — 定长

● 定长分布（记为 D ）

若顾客到达间隔时间（或服务时间）为一常量 a ，此时称输入（服务）分布为定长分布，用 T 表示此时间，则

P(T=a) = 1

用分布函数表示有

F(t) = P(T t) = 0 t

1 t a

● 概率特征：方差为 0

● 主要应用：

? 周期性到达事件

? 定长服务系统（例如 ATM 网络）

几个连续型分布 — 负指数

几个连续型分布 — 负指数

● 无记忆性

P(T>t+x| T>t) = P(T>x)

● 定理 1.1

负指数分布具有无记忆性 . 即设 T 是随机变量 , 服从负指数分布 , 参数为 >0, 设 t,x>0, 则

P(T>t +x| T>t) = P(T>x) = e - x

● 定理 1.2

设随机变量 T 是非负的连续型变量，它的分布具有无记忆性，则 T 服从负指数分布

● 连续型随机变量分布中，只有负指数分布具有无记忆特性

几个连续型分布 — 爱尔兰

● 定理 1.3

爱尔兰分布和负指数分布的关系

设 T 1 ,T 2 ,…,T k , 是独立同负指数分布的随机变量，参数为 ，则 T =T 1 +T 2 +…+T k , 服从 k 阶爱尔兰分布

● 主要应用

? 描述多级服务系统

? 描述平滑（规则）随机事件流

几个离散型分布

● 离散时间的排队理论在计算机通讯中有着广泛的应用。因为机械动作是间断的，用离散理论可以得到更精确的结果。

● 排队论中常用的最重要的离散分布是几何分布和负二项分布，实际上可以把它们看作是负指数分布、爱尔兰分布离散化而得到的分布，因此它们也应具有负指数分布、爱尔兰分布的类似性质。

几个离散型分布 — 几何

● 几何分布可以用来描述某一顾客的到达间隔或服务持续时间

? 每单位时间执行一次贝努力试验，“失败”则继续，成功则完成

? 首次“成功”之前需要持续的 时间就可以看成是相应的到达间隔或服务持续时间

几个离散型分布 — 几何

● 定理 1.4

几何分布具有无记忆性，即

P(T>n+m | T>n)=P(T>m)

或 P( T=n+m | T>n )=P( T=m )

● 定理 1.5

在离散型分布中，几何分布是唯一具有无记忆性的分布

几个离散型分布 — 负二项

● 定理 1.5

负二项分布与几何分布的关系

设 T1 ， T2 ， … ， Tk 是独立同几何分布的离散型随机变量，则 T=T1+T2…+…Tk 服从负二项分布（参数为 k ）

二项分布

二项分布即重复 n 次独立的 伯努利试验 。在每次试验中只有两种可能的结果，而且两种结果发生与否互相对立，并且相互 独立 ，与其它各次试验结果无关，事件发生与否的概率在每一次 独立试验 中都保持不变，则这一系列试验总称为 n 重伯努利实验，当试验次数为 1 时，二项分布就是 伯努利分布 。

2 概念

二项分布（Binomial Distribution），即重复n次的 伯努利试验 （Bernoulli Experiment），用ξ表示 随机试验 的结果。

二项分布公式

如果事件发生的 概率 是P,则不发生的概率q=1-p，N次 独立重复试验 中发生K次的概率是

应用条件

1．各观察单位只能具有相互对立的一种结果，如阳性或阴性，生存或死亡等，属于两分类资料。

2．已知发生某一结果（阳性）的概率为π，其对立结果的概率为1-π，实际工作中要求π是从大量观察中获得比较稳定的数值。

二项分布公式

3．n次试验在相同条件下进行，且各个观察单位的观察结果相互独立，即每个观察单位的观察结果不会影响到其他观察单位的结果。如要求疾病无传染性、无家族性等。

泊松分布

1 命名原因

泊松分布实例

泊松分布（Poisson distribution），台译卜瓦松分布，是一种统计与概率学里常见到的离散机率分布（discrete probability distribution）。泊松分布是以18～19 世纪的法国数学家 西莫恩·德尼·泊松 （Siméon-Denis Poisson）命名的，他在1838年时发表。但是这个分布却在更早些时候由贝努里家族的一个人描述过。就像当代科学史专家斯蒂芬·施蒂格勒（Stephen Stigler）所说的误称定律（the Law of Misonomy），数学中根本没有以其发明者命名的东西。

2分布特点

泊松分布的概率函数为：

泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生率。 泊松分布适合于描述单位时间内随机事件发生的次数。

泊松分布的期望和方差均为特征函数为

3关系

泊松分布与二项分布

泊松分布

当二项分布的n很大而p很小时，泊松分布可作为二项分布的近似，其中λ为np。通常当n≧10,p≦0.1时，就可以用泊松公式近似得计算。

事实上，泊松分布正是由二项分布推导而来的，具体推导过程参见本词条相关部分。

4应用场景

在实际事例中，当一个随机事件，例如某电话交换台收到的呼叫、来到某公共汽车站的乘客、某放射性物质发射出的粒子、显微镜下某区域中的白血球等等，以固定的平均 瞬时速率 λ （或称密度）随机且独立地出现时，那么这个事件在单位时间（面积或体积）内出现的次数或个数就近似地服从泊松分布 P ( λ )。因此,泊松分布在管理科学、运筹学以及自然科学的某些问题中都占有重要的地位。

5 应用示例

泊松分布适合于描述单位时间（或空间）内随机事件发生的次数。如某一服务设施在一定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，机器出现的故障数，自然灾害发生的次数，一块产品上的缺陷数，显微镜下单位分区内的细菌分布数等等。 [1]

观察事物平均发生m次的条件下，实际发生x次的概率P（x）可用下式表示：

称为泊松分布。例如采用0.05J/㎡紫外线照射大肠杆菌时，每个基因组（～4×10 6 核苷酸对 ）平均产生3个嘧啶二体。实际上每个基因组二体的分布是服从泊松分布的，将取如下形式：

是未产生二体的菌的存在概率，实际上其值的5%与采用0.05J/㎡照射时的大肠杆菌uvrA-株，recA-株（除去既不能修复又不能重组修复的二重突变）的生存率是一致的。由于该菌株每个基因组有一个二体就是致死量，因此

就意味着全部死亡的概率。 [2]

指数分布 的 分布函数 为：

数学期望 E(X)=1/λ ，方差为 D(X)=1/λ 2 。指数分布的分布函数图象如下图所示：