排队论讲义课件

排队论一.概率论及随机过程回顾二.排队论的基本知识三.单服务台负指数分布排队系统分析四.多服务台负指数分布排队系统分析五.一般服务时间M/G/1模型分析六.经济分析___排队系统的最优化

一、概率论及随机过程回顾随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?1.1、随机变量与概率分布一、概率论及随机过程复习随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?随机变量连续型随机变量概率密度函数概率分布函数数学期望和方差常见连续型随机变量的概率分布均匀分布指数分布？正态分布？k阶爱尔朗分布？一、随机变量与概率分布随机变量X为时间间隔，如顾客到达的时间间隔、电话呼叫的时间、产品的寿命等。密度函数?爱尔朗分布

为k个相互独立的随机变量；服从相同参数的负指数分布；设，则T的密度函数为

如k个服务台串联（k个服务阶段），一个顾客接受k个服务共需的服务时间T，T爱尔朗分布。1.2随机过程的有关概念随机过程(Randomprocess)的定义设，是一族随机变量，T是一个实数集，对是一个随机变量，则称为随机过程。

T：参数集合当T={0,1,…,n,…}时，称为随机序列

：随机过程的一个状态状态空间E={X(t)全体可能取值，}

随机过程的基本类型二阶矩过程平稳过程平稳独立增量过程常见随机过程马尔可夫过程？Poisson过程？生灭过程？1.2随机过程的有关概念定义：若满足如下性质：

对任意非负整数，只要

就有

则称具有马尔可夫性，或无后效性。马尔可夫过程马尔可夫链离散过去现在将来

“将来”的情况与“过去”无关，只是通过“现在”与“过去”发生联系，若“现在”已知，“将来”与“过去”无关。时齐的马氏链：马氏链

若满足：

则称为时齐马尔可夫链—系统由状态i经过m个时间间隔（或m步）转移到状态j的转移概率Poisson过程定义：设为时间内到达系统的顾客数，若满足下面三个条件：独立性：在任意两个不相交的区间内顾客到达的情况相互独立；平稳性：在内有一个顾客到达的概率为普通性：在内多于一个顾客到达的率为。则称为Poisson过程。（1）只与区间长度与起点无关。（2）单位时间内一个顾客到达的概率为。Poisson过程与Poisson分布定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是数理统计方法容易初步判断:期望=标准差Poisson过程与负指数分布定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。负指数分布的性质:马尔可夫性，或无后效性Poisson过程与Poisson分布的关系：定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。对于Poisson流：——单位时间平均到达的顾客数——顾客相继到达的平均间隔时间定义：设为一个随机过程，若N(t)的概率分布具有以下性质：(1)假设N(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为的负指数分布；(2)假设N(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为的负指数分布；(3)同一时刻是只有一个顾客到达或离去。则称为一个生灭过程。

生灭过程10nn-1n+1平稳生灭过程系统状态n平衡方程：“流入=流出”系统达到平稳状态时：的分布系统达到平稳状态时：其中平衡方程：当时才有意义二、排队论的基本知识2.1

排队模型2.2排队系统的组成和特征排队论研究的内容性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.顾客源2.1、排队模型排队系统排队结构服务机构排队规则服务规则接受服务后离去——排队系统的的一般表示服务机构服务台(a)一个队列、单服务台（阶段）服务台1服务台2(b)一个队列、s个服务阶段服务机构服务台1服务台2服务机构(c)一个队列、s个服务台一个服务阶段服务台3服务台4服务台1服务台2服务机构(d)s个队列、s个服务阶段服务台3服务台4服务台1服务台2:1–2–4:2–4–3:3–2–1–4服务机构(e)混合型排队结构服务台(f)一个队列服务台(g)s个队列

输入过程顾客总体:有限,无限.顾客到达方式:单个,成批.顾客到达间隔时间:确定的、随机的.顾客到达的独立性:独立,不独立.输入过程的平稳性:与时间无关(平稳的),与时间有关(非平稳的).2.2、排队系统的组成和特征顾客到达时间间隔的分布:：第n个顾客与第n-1个顾客到达的时间间隔；：第n个顾客到达的时刻；设令顾客到达时间间隔的分布:假定是独立同分布，分布函数为，排队论中常用的有两种：（2）最简流（即Poisson流）（M）：

顾客到达时间间隔为独立的，服从负指数分布，其密度函数为（1）定长分布（D）：顾客到达时间间隔为确定的。因为负指数分布具有无后效性（即Markov性）

排队及排队规则即时制(损失制)等待制先到先服务:FCFS后到先服务:LCFS随机服务优先权服务：PS队容量:有限,无限;有形,无形.队列数目:单列,多列.

服务机构服务员数量:无,单个,多个.队列与服务台的组合服务方式:单个顾客,成批顾客.服务时间:确定的,随机的.服务时间和到达间隔时间至少一个是随机的.服务时间分布是平稳的.服务时间分布:

设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：（1）定长分布（D）：每个顾客接受服务的时间是一个确定的常数。（2）负指数分布（M）：每个顾客接受服务时间相互独立，具有相互的负指数分布：

其中，为一常数。μ--单位时间平均服务完成的顾客数1/μ--每个顾客的平均服务时间服务时间分布:（3）k阶爱尔朗（Erlang）分布：每个顾客接受服务时间服从k阶爱尔朗分布，其密度函数为：

符号表示:X/Y/ZX--客到达间隔时间分布Y--服务时间分布Z--服务台个数X,Y可以是:M--负指数分布D--确定性的Ek--k阶Erlang分布GI--一般相互独立的到达时间间隔分布G--一般(General)时间分布排队系统的分类

扩展符号表示:X/Y/Z/A/B/CA--系统容量B--顾客源中顾客的数量C--服务规则:FCFS,LCFS,等等.若省略后三项，即是指下面的情形：

X/Y/Z///FCFS例：M/M/s/K表示？

已知:顾客到达间隔时间分布,服务时间分布.求:队长:Ls--系统中的顾客数.排队长(队列长):Lq--队列中的顾客数.

Ls=

Lq+正在接受服务的顾客数逗留时间:WS--顾客在系统中的停留时间等待时间:Wq--顾客在队列中的等待时间.

WS=Wq+服务时间忙期,损失率,服务强度.排队问题的求解三.单服务台负指数分布

排队系统分析

3.1M/M/1模型3.2M/M/1/N/模型(即系统的容量有限)3.3M/M/1//m模型（即顾客源为有限）顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去3.1M/M/1模型无限输入过程服从参数为的Poisson过程单队队长无限先到先服务服务时间服从参数为的负指数分布生灭过程

求解：:系统达到平稳后，系统有n个顾客的概率。平衡方程：，且当时其中关于的几点说明：顾客平均到达率顾客平均服务率一个顾客服务时间一个顾客到达时间——服务强度即顾客的顾客平均到达率小于顾客平均服务率时，系统才能达到统计平稳。系统中至少有一个顾客的概率；服务台处于忙的状态的概率；反映系统繁忙程度

计算有关指标队长队列长

计算有关指标

逗留时间:可以证明,Ws服从参数为μ-λ的负指数分布.则:等待时间计算有关指标计算有关指标Little公式（相互关系）小结平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:

(1-)平均闲期I=1/闲期的分布与顾客到达时间间隔的相同----服从参数为的负指数分布计算有关指标忙期与闲期WHY?1-P0=平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:

(1-)平均闲期I=1/平均忙期B=(/(1-))/=1/(-)计算有关指标忙期与闲期与逗留时间Ws相同!!!?例：某医院手术室每小时就诊病人数和手术时间的记录如下：到达的病人数出现次数

nun010128229316410566以上1合计100完成手术时间出现次数

rvr0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合计100解：到达的病人数出现次数

nun010128229316410566以上1合计100每小时病人平均到达率（人/小时）每次手术平均时间（小时/人）每小时完成手术人数（平均服务率）（人/小时）解：到达的病人数出现次数

nun010128229316410566以上1合计100每小时病人平均到达率（人/小时）每次手术平均时间（小时/人）每小时完成手术人数（平均服务率）（人/小时）完成手术时间出现次数

rvr0.0~0.2380.2~0.4250.4~0.6170.6~0.890.8~1.061.0~1.251.2以上0合计100解：3.2系统容量有限制的情形

(M/M/1/N/∞/FCFS）状态转移图状态转移方程N-1N求排队系统顾客数的分布状况其中

求排队系统顾客数的分布状况

队长队列长计算有关指标

逗留时间等待时间计算有关指标系统已满顾客不能到达的概率---损失率

有6个椅子接待人们排队，超过6人顾客就离开，平均到达率3人/小时，理发需时平均15分钟。Ｎ＝7为系统中的最大顾客数。平均到达率:＝3人/小时平均服务率:＝4人/小时举例：单人理发馆排队问题

顾客到达就能理发的概率

-------相当于理发店内没有顾客等待顾客数的期望值

求有效到达率

顾客在理发馆内逗留的期望时间小时分钟人/小时

可能的顾客中有百分之几不等待就离开-----求系统中有7个顾客的概率设：m：为顾客总体数，

λ：每个顾客的到达率，

m-Ls：系统外顾客的平均数，

λe=λ（m-Ls）：为系统有效到达率。3.3顾客源有限制的情形

(M/M/1/∞/m/FCFS）含义与上节不同—对顾客而言，而不是对系统m对系统而言,有一个顾客到达的概率状

态

转

移

图01mn-1n(m-n+1)

(m-n)n+1......m-1m...(m-1)2状态转移方程注意到，

求解状态转移方程得有效到达率求解顾客数概率分布

等待时间正常运转的平均设备台数计算有关指标

队长队列长逗留时间计算有关指标例：P343#例74.1标准的M/M/c模型（M/M/c//）4.2标准的M/M/c/N/型4.3标准的M/M/c//m模型四.多服务台负指数分布排队系统分析规定：各服务台工作是相互独立的，且平均服务率相同，均为。整个服务机构的平均服务率为：

c(当nc)，n(当n<c);记=/,s=/c=/c为服务系统的平均利用率当/c<1时，不会排成无限队列。4.1标准的M/M/c模型（M/M/c//）12c….服务台C个系统人数n人12c….服务台C个系统人数n人n<=c12c….服务台C个系统人数n人

n>c状

态

转

移

图01n-1nn(n+1)n+1......22n-1nccn+1......n<=c

n>c状态转移方程4.1标准的M/M/c模型（M/M/c//）解差分方程，求得状态概率为4.1标准的M/M/c模型（M/M/c//）

顾客等候的概率

计算有关指标平均正接受服务的顾客数=正忙的服务台数解释?

队长队列长逗留时间及等待时间计算有关指标唯一

某售票所有三个窗口，顾客到达服从Poisson过程，到达

=0.9人/分钟，服务=0.4人/分钟。设顾客到达后依次排成一队向空闲的窗口购票，如图a.

图a

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.9M/M/c型系统和c个M/M/1型系统的比较图aM/M/c型系统和c个M/M/1型系统的比较

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.3

=0.3

=0.3

=0.9图b

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.9属于M/M/c型系统c=3,=/=2.25,

s=/c=2.25/3<1,符合要求.整个售票所空闲概率平均队长平均等待时间和逗留时间顾客到达后必须等待概率

以上例说明,设顾客到达后在每个窗口前各排一队(其它条件不变),共三队,每队平均到达率为:

窗口1=0.4

窗口2=0.4

窗口3=0.4

=0.3

=0.3

=0.3

=0.9图bM/M/c型系统和c个M/M/1型系统的比较模型指标M/M/33个(M/M/1)P0LqLsWsWq必须等待概率0.07481.703.954.39(分钟)1.89(分钟)0.570.25(子系统)2.25(子)9.00(整)10(分钟)7.5(分钟)0.75结果比较M/M/c型系统和c个M/M/1型系统的比较4.2标准的M/M/c/N/模型状态图是多服务台和容量有限的综合平衡方程你会吗?4.2标准的M/M/c/N/模型求系统有n位顾客的概率分布4.2标准的M/M/c/N/模型求系统的指标有效到达率平均被占用的服务台4.2标准的M/M/c/N/模型求系统的指标4.3标准的M/M/c//m模型自学5.1M/G/1模型5.2M/Ｄ/1模型5.3M/Ek/1模型5.一般服务时间

M/G/1模型设系统的平均到达率为

，任一顾客的服务时间为V,且有：

E(V)