排队论(讲义)ppt课件.ppt

《排队论(讲义)ppt课件.ppt》由会员分享，可在线阅读，更多相关《排队论(讲义)ppt课件.ppt（125页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排队论排队论Queueing TheoryQueueing Theory主讲：周在莹主讲：周在莹1排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能CONTENTSPREPARATION:概率论与随机过程概率论与随机过程UNIT1排队模型排队模型UNIT2排队网络模型排队网络模型UNIT3应用之：应用之：QUICKPASS系统系统结束语结束语2排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能PREPARATION概率论和随机过程概率论和随机过程Part1

2、概率论基础概率论基础1。概率的定义概率的定义概概率率关关系系着着对对时时间间的的数数量量分分配配。一一个个事事件件A的的概概率率P(A)是是对对应应事事件件A要要发发生生可可能能性性的的数数量量分分配配。概概率率有有很多不同的定义，常用的有三种：很多不同的定义，常用的有三种：(1)古古典典定定义义：P(A)=NA/N其其中中N是是可可能能结结果果的的总总个个数数，NA是事件是事件A在其中发生的结果的个数。在其中发生的结果的个数。例例1.求抛两个骰子并且决定和为求抛两个骰子并且决定和为7的概率的概率p。总共有总共有36种可能的结果，所以种可能的结果，所以N=36有有6种种结结果果(1,6),(2

3、,5),(3,4),(4,3),(5,2)和和(6,1)为为所所求。求。所以所以NA=6，从而从而p=6/36=1/6。3排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(2)相对频率定义相对频率定义：P(A)=limnA/nn其中其中n是实验的次数，是实验的次数，nA是是A发生的次数发生的次数例例2投硬币投硬币在在大大数数量量投投掷掷后后，硬硬币币的的正正面面在在上上的的可可能能性性在在0.5左左右右，上上下下两面在上面具有相同的概率。两面在上面具有相同的概率。(3)公公理理化化定定义义：从从一一定定数数量量的的定定义义

4、概概率率度度量量的的公公理理出出发发，经经过过推导规则达到概率的有效计算。这些公理包括：推导规则达到概率的有效计算。这些公理包括：（a）对于每一个事件对于每一个事件A，有，有0P（A）1（b）P（）=1（c）如果如果A和和B是互斥的，则是互斥的，则P（AUB）=P（A）+P（B）4排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2条件概率和独立性条件概率和独立性条件概率：条件概率：假假定定事事件件B已已经经发发生生时时，事事件件A发发生生的的条条件件概概率率P(A|B)可以定义如下：可以定义如下：P（A|B）=P（AB）/

5、P（B）独立性：独立性：如果如果P(AB)=P(A)P(B)，事件，事件A和和B叫做相互独立的事件叫做相互独立的事件独立性的概念可以推广到三个或多个事件。独立性的概念可以推广到三个或多个事件。5排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3全概率公式和贝叶斯定理全概率公式和贝叶斯定理全全概概率率公公式式：给给定定一一组组互互斥斥事事件件E1，E2，En，这这些些事事件件的的并并集集包包括括所所有有可可能能的的结结果果，同同时时给给任任一一个个任任意事件意事件A，那么全概率公式可以表示为：，那么全概率公式可以表示为：n

6、P(A)=P(A|Ei)P(Ei)i=1把计算把计算A的概率分解为一些容易计算的概率之和。的概率分解为一些容易计算的概率之和。贝叶斯定理：贝叶斯定理：P(Ei|A)=P(A|Ei)P(Ei)P(A|Ei)P(Ei)也称为后验概率公式，是在已知结果发生的情况下，求导也称为后验概率公式，是在已知结果发生的情况下，求导致结果的某种原因的可能性的大小。致结果的某种原因的可能性的大小。6排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Part2.随机变量的数字特征随机变量的数字特征随随机机变变量量X是是样样本本点点的的函函数数，它它

7、的的定定义义域域是是样样本本空空间间，值值域域是实数集是实数集R，即，即X：R随随机机变变量量的的数数字字特特征征对对研研究究随随机机变变量量是是很很重重要要的的，常常用用的的数数字字特征有：数学期望、方差、协方差和相关系数。特征有：数学期望、方差、协方差和相关系数。1数学期望数学期望：连续情况：连续情况：EX=x=xf(x)dx积分区间从积分区间从-，离散情况：离散情况：EX=x=kPx=k all k 它是一种统计平均值，简称它是一种统计平均值，简称均值均值2方差方差：DX=E(X-x)2=EX2-x2它是度量随机变量它是度量随机变量X与其均值与其均值EX的的偏离程度偏离程度。均方差均方差

8、：方差的开方称为均方差，或标准方差，记为：方差的开方称为均方差，或标准方差，记为x二阶矩二阶矩：连续情况：连续情况：EX2 =x2f(x)dx积分区间从积分区间从-，离散情况：离散情况：EX2 =k2Px=k all k7排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3协方差：协方差：两个随机变量两个随机变量X和和Y的协方差定义如下：的协方差定义如下：Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4相关系数相关系数:两个随机变量两个随机变量X和和Y的相关系数定义如下：的相关系数定义如下：r(X,Y)=Cov(

9、X,Y)/xy相关系数是两个随机变量线性相关程度的度量。相关系数是两个随机变量线性相关程度的度量。例例3：设随机变量（：设随机变量（X，Y）的分布律如下：）的分布律如下：YX121 -10 1/4 0 1/4 求求 E(X),D(X),E(E(X),D(X),E(Y Y),D(Y),cov(X,Y),r(X,Y),D(Y),cov(X,Y),r(X,Y)8排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Part3几种重要的概率分布几种重要的概率分布1贝努里分布贝努里分布它的概率分布为：它的概率分布为：PX=1=p，PX=0

10、=1-p它它也也称称两两点点分分布布或或（0-1）分分布布。它它描描述述一一次次贝贝努努里里实实验验中中，成成功或失败的概率。功或失败的概率。2二项分布二项分布PX=k=Cnkpk(1-p)n-k,k=0,1,n它描述它描述n次贝努里实验中事件次贝努里实验中事件A出现出现k次概率。次概率。3几何分布几何分布PX=k=p(1-p)k-1,k=1,2,它描述在它描述在k次贝努里实验中首次出现成功的概率。次贝努里实验中首次出现成功的概率。9排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n几何分布有一个重要的性质几何分布有一个重

11、要的性质-后无效性后无效性：在前：在前n次实验未出现次实验未出现成功的条件下，再经过成功的条件下，再经过m次实验（即在次实验（即在n+m次实验中）首次出现成次实验中）首次出现成功的概率，等于恰好需要进行功的概率，等于恰好需要进行m次实验出现首次成功的无条件概率。次实验出现首次成功的无条件概率。用式子表达：用式子表达：nPX=n+m|Xn=PX=m(请同学们试证明之）n这种与过去历史无关的性质称为这种与过去历史无关的性质称为马尔可夫性马尔可夫性。n几何分布在我们下面讲的排队论中是非常重要。它可以几何分布在我们下面讲的排队论中是非常重要。它可以描述某一描述某一任务（或顾客）的服务持续时间任务（或顾

12、客）的服务持续时间。n4泊松分布（泊松分布（Poisson）nPX=k=k e-/k!k=0,1,2,n泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，它它作作为为表表述述随随机机现现象象的一种形式，在计算机性能评价等实践中扮演了重要的角色。的一种形式，在计算机性能评价等实践中扮演了重要的角色。n在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或或顾顾客客）的的到到来来是是服服从从泊松分布的泊松分布的。实践也证明：这种假设是有效的。实践也证明：这种假设是有效的。10排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大

13、会精神,充分发挥中小学图书室育人功能5（负负）指数分布指数分布它是一种连续型的概率分布，它的概率密度为它是一种连续型的概率分布，它的概率密度为f（x）=e-x x0 0 x0,t0，有，有Ps+t|s=Pt在离散型随机变量中，只有几何分布具有无后效性。这两种在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中，指数分布是很重要的。在排队理论中，指数分布是很重要的。11排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6

14、k-爱尔朗分布爱尔朗分布概率密度概率密度:f(x)=(kx)n-1ke-kx/(n-1)!x0，0.0 x0数数字字特征：特征：EX=1/;VarX=1/（k2）如如果果k个个随随机机变变量量Xi，i=1，2，,k,分分别别服服从从指指数数分分布布，那那么么随随机机变变量量X=X1+X2+Xk服服从从爱爱尔尔朗朗分分布布。即即：具具有有k-爱爱尔尔朗朗分分布布的的随随机机变变量量可可以以看看作作具具有有同同一一指指数数分分布布的的独独立立的的k个个随随机机变量之和。变量之和。k-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必

15、须通过一个关口，这个关口由在到达窗口排队必须通过一个关口，这个关口由k层构成，通层构成，通过每层的时间服从参数为过每层的时间服从参数为的指数分布，这样顾客通过整个关的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。口到达窗口排队时，就实现了爱尔朗分布。如下图：如下图：k210000窗口窗口12排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Part4随机过程随机过程随随机机过过程程是是定定义义在在给给定定的的概概率率空空间间上上的的一一族族随机变量随机变量X(t)，tT。我我们们知知道道：一一个个随随机机

16、变变量量是是定定义义在在样样本本空空间间S上上的的函函数数，则则随随机机过过程程实实际际上上就就是是一一个个函函数数族族X（t，s）|sS，tT。若若t固定，随机过程固定，随机过程X（t，s）就是随机变量）就是随机变量X（t）所取的值）所取的值，称为在称为在t时刻的状态时刻的状态。若若s固定，它是固定，它是t的函数，的函数，称称为随机过程的样为随机过程的样本函数或样本曲线。本函数或样本曲线。13排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能随机过程的例子随机过程的例子为为了了更更好好的的理理解解随随机机过过程程，我我们们

17、从从一一个个例例子子开开始始。例例如如，n个同样的电阻，同时记录它们热噪声的电压波形。个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在在t1时刻电阻上的热噪声电压是一个时刻电阻上的热噪声电压是一个随机变量随机变量，并记为，并记为x(t1)，也就是说，也就是说t1时刻任一电阻时刻任一电阻r(i)上的噪声电压上的噪声电压x(i,t1)是无法预先是无法预先确切地知道的。确切地知道的。这里这里n支电阻的热噪声电压的集合是这个随机实验的样本空支电阻的热噪声电压的集合是这个随机实验的样本空间间S。对于

18、某一支电阻，其热噪声电压是一时间函数。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是，是随机过程的样本函数随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为对所有电阻来说，其热噪声电压就是一族时间函数，记为x(t)，这族时间函数就是，这族时间函数就是“随机过程随机过程”，族中每一时间函数称为，族中每一时间函数称为随机过程的样本函数随机过程的样本函数。14排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Part5马尔可夫过程马尔可夫过程马尔可夫过程马尔可夫过程(MarkovProcess)是具有

19、无后效性的随机过程。是具有无后效性的随机过程。无无后后效效性性是是指指：当当过过程程在在tn时时刻刻所所处处的的状状态态为为已已知知时时，过过程程在在大大于于tn的的时时刻刻所所处处状状态态的的概概率率特特性性只只与与过过程程在在tn时时刻刻所所处处的的状状态态有有关，而与过程在关，而与过程在tn时刻以前的状态无关。时刻以前的状态无关。换换言言之之，对对于于随随机机过过程程X（t），t T，如如果果对对于于任任意意参参数数t0t1t2tn1有有pij=0(2)连续时间生灭过程连续时间生灭过程一一个个连连续续时时间间，状状态态空空间间S=0，1，2为为可可数数集集的的齐齐次次马马尔可夫尔可夫过程

20、过程X(t)，t0，,称为生灭过程。称为生灭过程。时齐性时齐性转移概率转移概率Pij(t,)只与只与i,j,-t有关，即有关，即Pij()=Pij(t,t+)16排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能练习练习练习：练习：1。有有10个个电电阻阻，其其电电阻阻值值分分别别为为1，2，10，从从中中取取出出三三个个，要要求求取取出出的的三三个个电电阻阻，一一个个小小于于5，一一个个等等于于5，另另一一个个大大于于5，问问：取取一次就能达到要求的概率。一次就能达到要求的概率。2一一袋袋内内装装有有5只只球球，编编号号为

21、为1，2，3，4，5，从从中中任任取取3只只，求求被被抽抽取取3只只球球中中，中中间间号号码码X的的分分布布规律。规律。17排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能习题解答习题解答1把把从从10个个电电阻阻中中取取出出3个个的的各各种种可可能能取取法法作作为为样样本本点点全全体体，这这是是古古典典概概率率，其其总总数数为为C（10，3），有有利利场场合合为为C（4，1）C（1，1）C（5，1）故，所求概率为：）故，所求概率为：P=C（4，1）C（1，1）C（5，1）/C（10，3）=1/62依依题题意意，X的的可可

22、能能值值为为2，3，4，当当取取中中间间号号码码为为k时时，则则另另外外两两只只球球必必须须分分别别在在号号码码小小于于k的的k-1个个中中取取一一个个，和和在在号码大于号码大于k的的5-k个中取一个，于是：个中取一个，于是：pk=PX=k=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4所以，所以，X的分布律为：的分布律为：X234Pk0.30.40.318排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能UNIT1排队模型排队模型排排队队论论（queueingtheory），或或称称随随机机服服务务系系统统

23、理理论论，作作为为运运筹筹学学研研究究的的一一种种有有力力手手段段，研研究究的的内内容容有有3个个方方面面：系系统统的的性性态态，即即与与排排队队有有关关的的数数量量指指标标的的概概率率规规律律性性；系系统统的的优优化化问问题题；统统计计推推断断，根根据据资资料料合合理理建建立立模模型型。目目的的是是正正确确设设计计和和有有效效运运行行各各个个服服务务系系统统，使使之之发发挥挥最最佳佳效效益益。排排队队论论不不仅仅在在理理论论上上达达到到了了成成熟熟阶阶段段，而而且且其其应应用用范范围围不不断断增增加加。概概括括起起来来，它它已已在在电电话话交交换换网网、公公路路、铁铁路路、航航空空运运输输、

24、工工程程管管理理、公公共共服服务务、货货物物存存储储和和生生产产流流水水线线过过程程等等方方面面得得到到了了广广泛泛的的应应用用。特特别别地地，排排队队论论是是计计算算机机通通信信网网络络和和计计算算机机系系统统中中通通信信信信息息量量研研究究的的基基础础理理论论，信信息息系系统统通通信信问题的问题的定量定量研究往往要求借助于排对论才能得到解决。研究往往要求借助于排对论才能得到解决。19排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能排队排队常常是件很令人恼火的事情常常是件很令人恼火的事情尤其是在我们这样的人口大国尤其是在

25、我们这样的人口大国电话亭电话亭1978年在北京年在北京15%的电话要在的电话要在1小时后才能接通。小时后才能接通。在电报大楼打电话的人还要带着午饭去排队在电报大楼打电话的人还要带着午饭去排队银行窗口，银行窗口，ATM游乐场的游乐项目游乐场的游乐项目医院、理发、火车售票医院、理发、火车售票在现实生活中，为了接受某种服务，排队等待是常在现实生活中，为了接受某种服务，排队等待是常见的现象。见的现象。从排队等待得到抽象的物理模型，进一从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。步建立数学模型的一整套理论就是所谓的排队论。20排队论课件为深入学习习近平新时代中国特色社会

26、主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能什么是排队论？什么是排队论？排队论是专门研究带有随机因素，产生排队论是专门研究带有随机因素，产生拥挤现象的优化理论。拥挤现象的优化理论。亦称为亦称为随机服务系统理论随机服务系统理论。因为被服务。因为被服务者到达系统的时间是不确定的。者到达系统的时间是不确定的。有关于由有关于由服务设施服务设施与与被服务者被服务者构成的构成的排排队服务系统队服务系统的理论。的理论。21排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能本讲主要掌握：本讲主要掌握：基本模型

27、基本模型M/M/1模型模型M/M/c模型模型其他模型其他模型应用：校园网的设计和调节收费应用：校园网的设计和调节收费22排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本的排队模型基本的排队模型基本组成基本组成概念与记号概念与记号指数分布和生灭过程指数分布和生灭过程23排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能典型典型排队系统模型排队系统模型顾客到达顾客到达:在队列中排队在队列中排队服务台服务服务台服务顾客离开顾客离开输入源的输入源的到达规律到

28、达规律队列大小？队列大小？特性？特性？到达方式？到达方式？服务规律？服务规律？服务协议？服务协议？在在本本单单元元中中，我我们们主主要要介介绍绍排排队队系系统统的的组组成成和和特特征征，排排队队系系统统的的到到达达和和服服务务，经经典典排排队队模模型型等等内内容容。顾顾客客到到达达规规律律和和服服务务规规律律都是通过概率来描述的，所以概率论是排队论的基础。都是通过概率来描述的，所以概率论是排队论的基础。输入源。24排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本组成基本组成输入来源队 列服务机构排队系统排队系统顾客服务

29、完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)25排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本排队模型基本排队模型输入过程输入过程顾客来源顾客来源有限有限/无限无限顾客数量顾客数量有限有限无限无限经常性的顾客来源经常性的顾客来源顾客到达间隔时间顾客到达间隔时间:到下一个顾客到达的时间到下一个顾客到达的时间.服从某一概率分布服从某一概率分布.(指数分布指数分布)顾客的行为假定顾客的行为

30、假定在未服务之前不会离开在未服务之前不会离开;当看到队列很长的时候离开；当看到队列很长的时候离开；从一个队列移到另一个队列。从一个队列移到另一个队列。顾客到达的方式通常是一个一个到达顾客到达的方式通常是一个一个到达的，也可能是成批的。顾客的到达总是有的，也可能是成批的。顾客的到达总是有一定规律，即到达过程或到达时间间隔符一定规律，即到达过程或到达时间间隔符合一定的分布，称合一定的分布，称到达分布。到达分布。顾客的到达或到达时间通常假定为相顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的互独立的且遵从同一分布的随机变量。随机变量。26排队论课件为深入学习习近平新时代中国特色社会主义思想和

31、党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本排队模型队列基本排队模型队列/排队规则排队规则d队列队列队列容量队列容量有限有限/无限无限排队方式排队方式单队列单队列并联式多队列并联式多队列串联式多队列串联式多队列杂乱队列杂乱队列 对于一个有限大小的队列来对于一个有限大小的队列来说，顾客可能从队列中丢失。说，顾客可能从队列中丢失。有什么样的服务协议就有什么有什么样的服务协议就有什么样的与之对应的排队方式。样的与之对应的排队方式。27排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本排队模型服务规则基

32、本排队模型服务规则服务机构服务机构服务设施，服务设施，服务渠道与服务台服务渠道与服务台服务台数量服务台数量单服务台系统单服务台系统多服务台系统多服务台系统无限服务台系统无限服务台系统服务协议服务协议先来先服务（先来先服务（FCFS）后来先服务（后来先服务（LCFS）随机服务（随机服务（RSS）有优先权的服务（有优先权的服务（PR）服务时间分布服务时间分布指数指数,常数常数,k阶阶Erlang 一般服务台对顾客是一个一个一般服务台对顾客是一个一个进行服务的，且对每一个顾客的进行服务的，且对每一个顾客的服务时间服务时间长短不一。长短不一。将将服务时间服务时间看作看作随机变量随机变量，那么那么它们是

33、相互独立的且遵循同一分它们是相互独立的且遵循同一分布。因此描述服务规律时，采用布。因此描述服务规律时，采用服务时间的概率分布，即服务时间的概率分布，即服务分服务分布布。服务分布同到达分布一样，到服务分布同到达分布一样，到底属于哪一种概率分布，要根据底属于哪一种概率分布，要根据具体排队问题进行分析。具体排队问题进行分析。28排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能服务协议服务协议（a）先来先服务先来先服务顾顾客客到到达达的的先先后后次次序序排排队队接接受受服服务务，用用FCFS（firstcomefirstserve

34、d）表示。）表示。（b）后来先服务（或称先来后服务）后来先服务（或称先来后服务）队队列列是是一一种种堆堆栈栈形形式式（临临时时寄寄存存货货物物的的地地方方）。当当某某一一顾顾客客服服务务结结束束时时，如如果果在在队队列列中中有有两两个个以以上上等等待待的的顾顾客客，则则把把最最后后到到达达的的顾顾客客作作为为下下一一个个服服务的对象。用务的对象。用LCFS（lastcomefirstserved）表示。）表示。（c）随机选择服务随机选择服务在服务时从等待顾客中随意抽取一个进行服务。在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务优先服务和动态优先服务预预先先规规定定优优先

35、先顺顺序序位位的的类类别别、且且给给到到达达顾顾客客规规定定优优先先顺顺序序位位作作为为标标记记的的优优先先权权。通通常常按按FCFS进进行行服服务务。优优先先权权分分为为三三类类：排排队队优优先先权权、中中断断优优先权、动态优先权先权、动态优先权。如计算机中断的优先级。如计算机中断的优先级。（e）处理器共享（处理器共享（processorsharing，PS）服服务务台台的的处处理理能能力力被被平平均均分分配配给给队队列列中中的的所所有有顾顾客客，没没有有排排队队现现象象出出现现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。当顾客的数量增加时，只是顾客的服务时间变长。如：网

36、络服务系统。（f）无限服务台（无限服务台（infiniteserver，Is）在在这这种种情情况况下下，队队列列中中的的每每个个顾顾客客接接受受完完全全相相同同的的服服务务，而而且且就就好好像像它它是是唯唯一一的的一一个个顾顾客客一一样样。好好像像对对于于每每个个顾顾客客都都可可以以“克克隆隆”出出一一个个新新的的服服务务台，而且克隆的数目可以无限。台，而且克隆的数目可以无限。29排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能排队系统的到达和服务排队系统的到达和服务1到达规律的描述到达规律的描述（1）主要描述参数）主要描

37、述参数（a）到达时点）到达时点将将某某一一时时刻刻设设为为t0，顾顾客客依依次次到到达达的的时时刻刻用用t-1t0t1t2表表示示，如如果果在在时刻时刻tk到达的顾客为到达的顾客为Nk，则到达时点可用，则到达时点可用tk、Nk）表示。）表示。（b）平均到达间隔）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律）到达规律顾顾客客的的到到达达规规律律可可以以用用概概率率来来描描述述，两两个个顾顾客客到到

38、达达的的时时间间间间隔隔是是独独立立的的随随机变量，服从同一概率分布时。常用的分布规律有：机变量，服从同一概率分布时。常用的分布规律有：（a）一般到达）一般到达（b）泊松到达）泊松到达（c）爱尔朗到达）爱尔朗到达（d）等间隔到达）等间隔到达30排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能泊松分布和负指数分布在排队论中的应用泊松分布和负指数分布在排队论中的应用泊松分布（泊松分布（Poisson）：）：PX=k=ke-/k!k=0,1,2,，x=x=泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，

39、也也是是表表述述随随机机现现象象的的一一种种重重要要形形式式。在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。如如果果顾顾客客到到达达的的人人数数是是符符合合泊泊松松分分布布，即即在在时时间间T内内到到达达有有k个顾客到达的概率为：个顾客到达的概率为：p=（T）ke-T/k!，在时间在时间T内顾客到达的平均顾客数内顾客到达的平均顾客数=T，平均到达速度（顾客数平均到达速度（顾客数/秒）秒）=服服从从泊泊松松分分布布过过程程的的到到达达被被认认为为是是随随机机到到达达

40、，因因为为当当顾顾客客根根据据泊泊松松过过程程到到达达时时，顾顾客客在在各各个个时时刻刻到到达达的的可可能能性性相相同同并并与与其它顾客的到达无关。其它顾客的到达无关。31排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（负）指数分布：（负）指数分布：它是一种连续型的概率分布，它的概率密度：它是一种连续型的概率分布，它的概率密度：f（x）=e-xx0它的分布函数：它的分布函数：F（x）=1-e-xx0指指数数分分布布的的一一个个有有用用的的性性质质是是它它的的数数学学期期望望等等于于标标准准差差：x=x=1/泊松分布和指数

41、分布的关系：泊松分布和指数分布的关系：如如果果顾顾客客以以泊泊松松到到达达,则则顾顾客客到到达达的的时时间间间间隔隔Ta服服从从指指数数分分布布，即：即：PTat=1-e-t,ETa=1/因此，平均到达的时间间隔是到达速率的倒数。因此，平均到达的时间间隔是到达速率的倒数。32排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布负指数分布密度函数密度函数均值均值方差方差随机变量随机变量 T（两个顾客相继到达的时间间隔）（两个顾客相继到达的时间间隔）分布函数分布函数 fT(t)t33排队论课件为深入学习习近平新时代中国特

42、色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布性质负指数分布性质1fT(t)tttfT(t)是一个严格下降函数34排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布性质负指数分布性质2无后效性（无记忆性）无后效性（无记忆性）不管多长时间不管多长时间(t)已经过去，已经过去，逗留时间的概率分布与下逗留时间的概率分布与下一个事件的相同一个事件的相同.或者说，后一个顾客到来所需时间与或者说，后一个顾客到来所需时间与前一个顾客到来所需时间无关。前一个顾客到来所需时间无关。35排

43、队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布性质负指数分布性质3几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机几个独立的指数分布的随机变量的和还是一个服从指数变量的和还是一个服从指数分布的随机变量分布的随机变量T1(1)T1(2)T1(3)T(1+2+3)36排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布性质负指数分布性质4负指数分布Poisson分布 在

44、t时间内已经服务n个顾客的概率1/:平均服务时间平均服务率=相继顾客到达平均间隔时间37排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能负指数分布性质负指数分布性质538排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能排队论基本概念部分练习排队论基本概念部分练习练习练习1：1。指出下列排队系统中的顾客和服务台：。指出下列排队系统中的顾客和服务台：（1）自行车修理店；（）自行车修理店；（2）按客户订单进行加工的加工车间）按客户订单进行加工的加工车间（3）

45、机场起飞的客机）机场起飞的客机（4）十字路口红灯前的车辆）十字路口红灯前的车辆2。判断正误。判断正误（1）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间隔时间服从指数分布。隔时间服从指数分布。（2）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间足够长的时间后，系统将进入稳定状态。足够长的时间后，系统将进入稳定状态。（3）在排队系统中，顾客等待时间的分布不受排队规则的影响。）在排队系统中，顾客等待时间的分布不受排队规则的影响。

46、39排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2服务规律的描述服务规律的描述(1)主要描述参量主要描述参量（a）平均服务时间）平均服务时间设设服服务务时时间间的的分分布布函函数数为为F（t），则则服服务务时时间间的的平平均均表表示示为为:1/=tdF(t)其中其中称为平均服务速率，平均一个顾客的服务时间。称为平均服务速率，平均一个顾客的服务时间。（b）服务速率）服务速率一一般般指指平平均均服服务务速速率率，单单位位时时间间内内被被服服务务完完的的顾顾客客数数，用用来表示。来表示。(2)服务规律服务规律服服务务规规律律

47、通通常常是是就就服服务务时时间间的的分分布布而而言言的的。服服务务时时间间分分布布典典型地有指数分布、爱尔朗分布、一般分布等。型地有指数分布、爱尔朗分布、一般分布等。结结论论：顾顾客客到到达达规规律律和和服服务务规规律律都都是是通通过过概概率率来来描描述述的的，所所以以概概率论是排队论的基础。率论是排队论的基础。40排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能经典排队模型经典排队模型它的格式为：它的格式为：ABnSZ其中符号的含义如下：其中符号的含义如下：A：顾客到达的规律；顾客到达的规律；B：服务时间分布；服务时间分

48、布；n：服务台的数目；服务台的数目；S：队列容量的大小；队列容量的大小；Z：服务规程。服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为ABn不同类型的排队，不同类型的排队，A、B可用如下约定的字母表示可用如下约定的字母表示。M：如如果果用用于于描描述述到到达达，表表示示泊泊松松到到达达过过程程，到到达达时时间间间间隔隔符符合合指指数数分分布布；如如 果用于描述果用于描述服务，则指具有指数分布的时间。服务，则指具有指数分布的时间。M表示表示Markov的第一个字母。的第一个字母。G：一一般般分分布布

49、。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从一一般般分分布布。G是是General的的第第一个字母。一个字母。Ek：k-爱爱尔尔朗朗分分布布。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从k-爱爱尔尔朗朗分分布布。E是是Erlang的第一个字母。的第一个字母。D:定长分布定长分布(常数时间常数时间)H：超几何分布。：超几何分布。L：H项式分布。项式分布。Z代表的服务规程典型的有：代表的服务规程典型的有：FCFS：先来先服务；先来先服务；LCFS：后来先服务；后来先服务；RSS：随机选择服务；随机选择服务；PR：优先权服务。优先权服务。Ba：集体（批量）服务。集体

50、（批量）服务。GD：一般规约服务，即通用规约服务。一般规约服务，即通用规约服务。41排队论课件为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3基本排队关系基本排队关系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：统，若满足以下三个条件：（1）排队系统能够进入统计平衡状态；）排队系统能够进入统计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）