《排队论(讲义)2013年建模A题专用.ppt》由会员分享，可在线阅读，更多相关《排队论(讲义)2013年建模A题专用.ppt（125页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、排队论*（2013建模A题专用）Queueing Theory主讲：周在莹主讲：周在莹排队论课件2CONTENTSPREPARATION:概率论与随机过程概率论与随机过程UNIT1排队模型排队模型UNIT2排队网络模型排队网络模型UNIT3应用之：应用之：QUICKPASS系统系统结束语结束语排队论课件3PREPARATION概率论和随机过程概率论和随机过程Part1概率论基础1。概率的定义概率关系着对时间的数量分配。一个事件A的概率 P(A)是对应事件A要发生可能性的数量分配。概率有很多不同的定义，常用的有三种：(1)古典定义：P(A)=NA/N其中N是可能结果的总个数，NA是事件A在其中发
2、生的结果的个数。例1.求抛两个骰子并且决定和为7的概率p。总共有36种可能的结果，所以N=36 有6种结果(1,6),(2,5),(3,4),(4,3),(5,2)和(6,1)为所求。所以NA=6，从而 p=6/36=1/6。排队论课件4(2)相对频率定义：P(A)=lim nA/n n其中n是实验的次数，nA是A发生的次数 例2 投硬币 在大数量投掷后，硬币的正面在上的可能性在0.5左右，上下两面在上面具有相同的概率。(3)公理化定义：从一定数量的定义概率度量的公理出发，经过推导规则达到概率的有效计算。这些公理包括：（a）对于每一个事件A，有0P（A）1（b）P（）=1（c）如果A和B是互斥
3、的，则P（AUB）=P（A）+P（B）排队论课件52 条件概率和独立性 条件概率：假定事件B已经发生时，事件A发生的条件概率P(A|B)可以定义如下：P（A|B）=P（AB）/P（B）独立性：如果P(AB)=P(A)P(B)，事件A和B叫做相互独立的事件独立性的概念可以推广到三个或多个事件。排队论课件63 全概率公式和贝叶斯定理全概率公式：给定一组互斥事件E1，E2，En，这些事件的并集包括所有可能的结果，同时给任一个任意事件A，那么全概率公式可以表示为：n P(A)=P(A|Ei)P(Ei)i=1把计算A的概率分解为一些容易计算的概率之和。贝叶斯定理：P(Ei|A)=P(A|Ei)P(Ei)
4、P(A|Ei)P(Ei)也称为后验概率公式，是在已知结果发生的情况下，求导致结果的某种原因的可能性的大小。排队论课件7Part2.随机变量的数字特征随机变量的数字特征随机变量X是样本点的函数，它的定义域是样本空间，值域是实数集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的偏离程度。均方差：方差的开方称为均方差，或标准方差，
5、记为x二阶矩：连续情况：EX2 =x2f(x)dx 积分区间从-，离散情况：EX2 =k2Px=k all k排队论课件83 协方差：两个随机变量X和Y的协方差定义如下：Cov(X,Y)=E(X-x)(Y-y)=EXY-EXEY4 相关系数:两个随机变量X和Y的相关系数定义如下：r(X,Y)=Cov(X,Y)/xy相关系数是两个随机变量线性相关程度的度量。例3：设随机变量（X，Y）的分布律如下：Y X 1 2 1 -10 1/4 求 E(X),D(X),E(Y),D(Y),cov(X,Y),r(X,Y)排队论课件9Part3几种重要的概率分布1 贝努里分布它的概率分布为：PX=1=p，PX=0
6、=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次贝努里实验中首次出现成功的概率。排队论课件10n几何分布有一个重要的性质几何分布有一个重要的性质-后无效性后无效性：在前：在前n次实验未出现次实验未出现成功的条件下，再经过成功的条件下，再经过m次实验（即在次实验（即在n+m次实验中）首次出现成次实验中）首次出现成功的概率，等于恰好需要进行功的概率，等于恰好需要进行m次实验出现首次成功的无条件概
7、率。次实验出现首次成功的无条件概率。用式子表达：用式子表达：nPX=n+m|Xn=PX=m (请同学们试证明之）n这种与过去历史无关的性质称为这种与过去历史无关的性质称为马尔可夫性马尔可夫性。n几何分布在我们下面讲的排队论中是非常重要。它可以几何分布在我们下面讲的排队论中是非常重要。它可以描述某一描述某一任务（或顾客）的服务持续时间任务（或顾客）的服务持续时间。n4 泊松分布（泊松分布（Poisson）nPX=k=k e-/k!k=0,1,2,n泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，它它作作为为表表述述随随机机现现象象的一种形式，在计算机性能评价等实践中扮演
8、了重要的角色。的一种形式，在计算机性能评价等实践中扮演了重要的角色。n在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或或顾顾客客）的的到到来来是是服服从从泊松分布的泊松分布的。实践也证明：这种假设是有效的。实践也证明：这种假设是有效的。排队论课件115 （负）指数分布它是一种连续型的概率分布，它的概率密度为f（x）=e-x x0 0 x0,t0，有 Ps+t|s=Pt 在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中，指数分布是很重要的。排队论课件12 6 k-爱尔朗分布概率密度:f(x)=(kx)n-1ke
9、-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-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必须通过一个关口，这个关口由k层构成，通过每层的时间服从参数为的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。如下图：k210000窗口排队论课件13Part4随机过程 随机过程是定义在给定的概率空间上的一族随机变量X(t)，t T。我们知道
10、：一个随机变量是定义在样本空间S上的函数，则随机过程实际上就是一个函数族X（t，s）|s S，t T。若t固定，随机过程X（t，s）就是随机变量X（t）所取的值，称为在t时刻的状态。若s固定，它是t的函数，称为随机过程的样本函数或样本曲线。排队论课件14随机过程的例子随机过程的例子为了更好的理解随机过程，我们从一个例子开始。例如，n个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在t1时刻电阻上的热噪声电压是一个随机变量，并记为x(t1)，也就是说t1时刻任一电阻r(i)上的噪声电压x(i,t1)是无法预先确切地知道的。这里n支电阻的热噪声电压
11、的集合是这个随机实验的样本空间S。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为x(t)，这族时间函数就是“随机过程”，族中每一时间函数称为随机过程的样本函数。排队论课件15Part5马尔可夫过程马尔可夫过程(MarkovProcess)是具有无后效性的随机过程。无后效性是指：当过程在tn时刻所处的状态为已知时，过程在大于tn的时刻所处状态的概率特性只与过程在tn时刻所处的状态有关，而与过程在tn时刻以前的状态无关。换言之，对于随机过程X（t），tT，如果对于任意参数 t0t1t2tn1有pij=0(2)连续时间生
12、灭过程一个连续时间，状态空间S=0，1，2为可数集的齐次马尔可夫过程X(t)，t0，,称为生灭过程。时齐性转移概率Pij(t,)只与i,j,-t有关，即Pij()=Pij(t,t+)排队论课件17练习练习练习：练习：1。有有10个个电电阻阻，其其电电阻阻值值分分别别为为1，2，10，从从中中取取出出三三个个，要要求求取取出出的的三三个个电电阻阻，一一个个小小于于5，一一个个等等于于5，另另一一个个大大于于5，问问：取取一次就能达到要求的概率。一次就能达到要求的概率。2一一袋袋内内装装有有5只只球球，编编号号为为1，2，3，4，5，从从中中任任取取3只只，求求被被抽抽取取3只只球球中中，中中间间
13、号号码码X的的分分布布规律。规律。排队论课件18习题解答习题解答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的的可可能能值值为为2，3，4，当当取取中中间间号号码码为为k时时，则则另另外外两两只只球球必必须须分分别别在在号号码码小小于于k的的k-1个个中中取取一一个个，和和在在号码大于号码大于k的的5-k个中取
14、一个，于是：个中取一个，于是：pk=PX=k=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4所以，所以，X的分布律为：的分布律为：X234Pk0.30.40.3排队论课件19UNIT1排队模型 排队论（queueing theory），或称随机服务系统理论，作为运筹学研究的一种有力手段，研究的内容有3个方面：系统的性态，即与排队有关的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型。目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论不仅在理论上达到了成熟阶段，而且其应用范围不断增加。概括起来，它已在电话交换网、公路、铁路、航空运输、工程管理、公共
15、服务、货物存储和生产流水线过程等方面得到了广泛的应用。特别地，排队论是计算机通信网络和计算机系统中通信信息量研究的基础理论，信息系统通信问题的定量研究往往要求借助于排对论才能得到解决。排队论课件20排队常常是件很令人恼火的事情常常是件很令人恼火的事情尤其是在我们这样的人口大国尤其是在我们这样的人口大国电话亭电话亭1978年在北京年在北京15%的电话要在的电话要在1小时后才能接通。小时后才能接通。在电报大楼打电话的人还要带着午饭去排队在电报大楼打电话的人还要带着午饭去排队银行窗口，银行窗口，ATM游乐场的游乐项目游乐场的游乐项目医院、理发、火车售票医院、理发、火车售票在现实生活中，为了接受某种服
16、务，排队等待是常在现实生活中，为了接受某种服务，排队等待是常见的现象。见的现象。从排队等待得到抽象的物理模型，进一从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。步建立数学模型的一整套理论就是所谓的排队论。排队论课件21什么是排队论？什么是排队论？排队论是专门研究带有随机因素，产生排队论是专门研究带有随机因素，产生拥挤现象的优化理论。拥挤现象的优化理论。亦称为亦称为随机服务系统理论。因为被服务。因为被服务者到达系统的时间是不确定的。者到达系统的时间是不确定的。有关于由有关于由服务设施与与被服务者构成的构成的排队服务系统的理论。的理论。排队论课件22本讲主要掌握：本
17、讲主要掌握：基本模型基本模型M/M/1模型模型M/M/c模型模型其他模型其他模型应用：校园网的设计和调节收费应用：校园网的设计和调节收费排队论课件23基本的排队模型基本的排队模型基本组成基本组成概念与记号概念与记号指数分布和生灭过程指数分布和生灭过程排队论课件24典型排队系统模型 顾客到达:在队列中排队服务台服务顾客离开输入源的到达规律队列大小？特性？到达方式？服务规律？服务协议？在本单元中，我们主要介绍排队系统的组成和特征，排队系统的到达和服务，经典排队模型等内容。顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。输入源。排队论课件25基本组成基本组成输入来源队列服务机构
18、排队系统排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)排队论课件26基本排队模型基本排队模型输入过程输入过程顾客来源有限/无限顾客数量有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间.服从某一概率分布.(指数分布)顾客的行为假定在未服务之前不会离开;当看到队列很长的时候离开；从一个队列移到另一个队列。顾客到达的方式通常是一个一个到达顾客到达的方式通常是一个一个到达的，也可能是成批的。顾客的到达总是有的，也可能是成批的。顾客的到达总
19、是有一定规律，即到达过程或到达时间间隔符一定规律，即到达过程或到达时间间隔符合一定的分布，称合一定的分布，称到达分布。到达分布。顾客的到达或到达时间通常假定为相顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的互独立的且遵从同一分布的随机变量。随机变量。排队论课件27基本排队模型队列基本排队模型队列/排队规则排队规则d队列队列队列容量队列容量有限/无限排队方式排队方式单队列并联式多队列串联式多队列杂乱队列对于一个有限大小的队列来对于一个有限大小的队列来说，顾客可能从队列中丢失。说，顾客可能从队列中丢失。有什么样的服务协议就有什么有什么样的服务协议就有什么样的与之对应的排队方式。样的与之对
20、应的排队方式。排队论课件28基本排队模型服务规则基本排队模型服务规则服务机构服务机构服务设施，服务设施，服务渠道与服务台服务渠道与服务台服务台数量服务台数量单服务台系统多服务台系统无限服务台系统服务协议先来先服务（FCFS）后来先服务（LCFS）随机服务（RSS）有优先权的服务（PR）服务时间分布指数,常数,k阶Erlang一般服务台对顾客是一个一个一般服务台对顾客是一个一个进行服务的，且对每一个顾客的进行服务的，且对每一个顾客的服务时间服务时间长短不一。长短不一。将将服务时间服务时间看作看作随机变量随机变量，那么那么它们是相互独立的且遵循同一分它们是相互独立的且遵循同一分布。因此描述服务规律
21、时，采用布。因此描述服务规律时，采用服务时间的概率分布，即服务时间的概率分布，即服务分服务分布布。服务分布同到达分布一样，到服务分布同到达分布一样，到底属于哪一种概率分布，要根据底属于哪一种概率分布，要根据具体排队问题进行分析。具体排队问题进行分析。排队论课件29服务协议（a）先来先服务先来先服务 顾顾客客到到达达的的先先后后次次序序排排队队接接受受服服务务，用用 FCFS（firstcomefirstserved）表示。）表示。（b）后来先服务（或称先来后服务）后来先服务（或称先来后服务）队队列列是是一一种种堆堆栈栈形形式式（临临时时寄寄存存货货物物的的地地方方）。当当某某一一顾顾客客服服务
22、务结结束束时时，如如果果在在队队列列中中有有两两个个以以上上等等待待的的顾顾客客，则则把把最最后后到到达达的的顾顾客客作作为为下下一一个个服服务的对象。用务的对象。用LCFS（lastcomefirstserved）表示。）表示。（c）随机选择服务随机选择服务 在服务时从等待顾客中随意抽取一个进行服务。在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务优先服务和动态优先服务 预预先先规规定定优优先先顺顺序序位位的的类类别别、且且给给到到达达顾顾客客规规定定优优先先顺顺序序位位作作为为标标记记的的优优先先权权。通通常常按按FCFS进进行行服服务务。优优先先权权分分为为三三类类
23、：排排队队优优先先权权、中中断断优优先权、动态优先权先权、动态优先权。如计算机中断的优先级。如计算机中断的优先级。（e）处理器共享（处理器共享（processor sharing，PS）服服务务台台的的处处理理能能力力被被平平均均分分配配给给队队列列中中的的所所有有顾顾客客，没没有有排排队队现现象象出出现现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。（f）无限服务台（无限服务台（infinite server，Is）在在这这种种情情况况下下，队队列列中中的的每每个个顾顾客客接接受受完完全全相相同同的的服服务务，而
24、而且且就就好好像像它它是是唯唯一一的的一一个个顾顾客客一一样样。好好像像对对于于每每个个顾顾客客都都可可以以“克克隆隆”出出一一个个新新的的服服务务台，而且克隆的数目可以无限。台，而且克隆的数目可以无限。排队论课件30排队系统的到达和服务1 到达规律的描述（1）主要描述参数（a）到达时点 将某一时刻设为t0，顾客依次到达的时刻用t-1t0t1t2表示，如果在时刻tk到达的顾客为Nk，则到达时点可用tk、Nk）表示。（b）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律 顾客的到达规律可以用概率来描述，两个
25、顾客到达的时间间隔是独立的随机变量，服从同一概率分布时。常用的分布规律有：（a）一般到达（b）泊松到达（c）爱尔朗到达（d）等间隔到达排队论课件31泊松分布和负指数分布在排队论中的应用 泊松分布（Poisson）：PX=k=ke-/k!k=0,1,2,，x=x=泊泊松松分分布布是是最最重重要要的的离离散散型型概概率率分分布布之之一一，也也是是表表述述随随机机现现象象的的一一种种重重要要形形式式。在在实实际际系系统统模模型型中中，一一般般都都要要假假定定任任务务（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。（或顾客）的到来是泊松分布的。实践也证明：这种假设有效。如果顾客到达的人数是符合
26、泊松分布，即在时间T内到达有k个顾客到达的概率为：p=（T）ke-T/k!，在时间T内顾客到达的平均顾客数=T，平均到达速度（顾客数/秒）=服服从从泊泊松松分分布布过过程程的的到到达达被被认认为为是是随随机机到到达达，因因为为当当顾顾客客根根据据泊泊松松过过程程到到达达时时，顾顾客客在在各各个个时时刻刻到到达达的的可可能能性性相相同同并并与与其它顾客的到达无关。其它顾客的到达无关。排队论课件32（负）指数分布：它是一种连续型的概率分布，它的概率密度：它是一种连续型的概率分布，它的概率密度：f（x）=e-xx0 它的分布函数：它的分布函数：F（x）=1-e-xx0指指数数分分布布的的一一个个有有
27、用用的的性性质质是是它它的的数数学学期期望望等等于于标标准准差差：x=x=1/泊松分布和指数分布的关系：如果顾客以泊松到达,则顾客到达的时间间隔Ta服从指数分布，即：PTat=1-e-t,ETa=1/因此，平均到达的时间间隔是到达速率的倒数。排队论课件33负指数分布负指数分布密度函数密度函数均值均值方差方差随机变量随机变量 T（两个顾客相继到达的时间间隔）（两个顾客相继到达的时间间隔）分布函数分布函数 fT(t)t排队论课件34负指数分布性质负指数分布性质1fT(t)tttfT(t)是一个严格下降函数排队论课件35负指数分布性质负指数分布性质2无后效性（无记忆性）无后效性（无记忆性）不管多长时
28、间不管多长时间(t)已经过去，已经过去，逗留时间的概率分布与下逗留时间的概率分布与下一个事件的相同一个事件的相同.或者说，后一个顾客到来所需时间与或者说，后一个顾客到来所需时间与前一个顾客到来所需时间无关。前一个顾客到来所需时间无关。排队论课件36负指数分布性质负指数分布性质3几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机变量的最小也服从指数分布几个独立的指数分布的随机几个独立的指数分布的随机变量的和还是一个服从指数变量的和还是一个服从指数分布的随机变量分布的随机变量T1(1)T1(2)T1(3)T(1+2+3)排队论课件37负指数分布性质负指数分布性质4负指数分布P
29、oisson分布在t时间内已经服务n个顾客的概率1/:平均服务时间平均服务率=相继顾客到达平均间隔时间排队论课件38负指数分布性质负指数分布性质5排队论课件39排队论基本概念部分练习排队论基本概念部分练习练习练习1：1。指出下列排队系统中的顾客和服务台：。指出下列排队系统中的顾客和服务台：（1）自行车修理店；（）自行车修理店；（2）按客户订单进行加工的加工车间）按客户订单进行加工的加工车间（3）机场起飞的客机）机场起飞的客机（4）十字路口红灯前的车辆）十字路口红灯前的车辆2。判断正误。判断正误（1）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间）若到达排队系统的顾客人数服从
30、泊松分布，则依次到达的两名顾客之间的间隔时间服从指数分布。隔时间服从指数分布。（2）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间足够长的时间后，系统将进入稳定状态。足够长的时间后，系统将进入稳定状态。（3）在排队系统中，顾客等待时间的分布不受排队规则的影响。）在排队系统中，顾客等待时间的分布不受排队规则的影响。排队论课件402服务规律的描述(1)主要描述参量 （a）平均服务时间）平均服务时间 设设服服务务时时间间的的分分布布函函数数为为F（t），则则服服务务时时间间的的平平均均表表示示为为:1/=t dF(t
31、)其中其中称为平均服务速率，平均一个顾客的服务时间。称为平均服务速率，平均一个顾客的服务时间。（b）服务速率）服务速率 一一般般指指平平均均服服务务速速率率，单单位位时时间间内内被被服服务务完完的的顾顾客客数数，用用来表示。来表示。(2)服务规律 服服务务规规律律通通常常是是就就服服务务时时间间的的分分布布而而言言的的。服服务务时时间间分分布布典典型地有指数分布、爱尔朗分布、一般分布等。型地有指数分布、爱尔朗分布、一般分布等。结论：顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。排队论课件41经典排队模型经典排队模型它的格式为：它的格式为：ABnSZ 其中符号的含义如下：
32、其中符号的含义如下：A：顾客到达的规律；顾客到达的规律；B：服务时间分布；服务时间分布；n：服务台的数目；服务台的数目；S：队列容量的大小；队列容量的大小；Z：服务规程。服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为ABn 不同类型的排队，不同类型的排队，A、B可用如下约定的字母表示可用如下约定的字母表示。M：如如果果用用于于描描述述到到达达，表表示示泊泊松松到到达达过过程程，到到达达时时间间间间隔隔符符合合指指数数分分布布；如如 果用于描述果用于描述服务，则指具有指数分布的时间。服务，则指具有
33、指数分布的时间。M表示表示Markov的第一个字母。的第一个字母。G：一一般般分分布布。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从一一般般分分布布。G是是General的的第第 一个字母。一个字母。Ek：k-爱爱尔尔朗朗分分布布。表表示示到到达达间间隔隔时时间间或或服服务务时时间间服服从从k-爱爱尔尔朗朗分分布布。E是是Erlang的第一个字母。的第一个字母。D:定长分布定长分布(常数时间常数时间)H：超几何分布。：超几何分布。L：H项式分布。项式分布。Z代表的服务规程典型的有：代表的服务规程典型的有：FCFS：先来先服务；先来先服务；LCFS：后来先服务；后来先服务；RSS
34、：随机选择服务；随机选择服务；PR：优先权服务。优先权服务。Ba：集体（批量）服务。集体（批量）服务。GD：一般规约服务，即通用规约服务。一般规约服务，即通用规约服务。排队论课件423基本排队关系在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：（1）排队系统能够进入统计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）系统中任一顾客不会永远等待，系统也不会永无顾客到达。则下列Little公式成立（排队论中的通用公式）：（1）Lq=Wq我们知道一个顾客的平均排队等待时间是Wq，且顾客是以平均速率到达，所以在时间Wq内有Wq个顾客
35、到达，Lq表示排队等待服务的平均顾客数量，所以有：Lq=Wq（2）L=W系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平均到达速率乘以一个顾客在系统中花费的平均时间。（3）W=Wq+1/一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。排队论课件434队列分析的任务和假设条件队列分析的基本任务是：给出如下输入信息（概率分布）：到达速率（到达速率（）服务时间（服务时间（1/)求出如下输出信息（均值、标准差）：等待顾客的数量（等待顾客的数量（Lq,Lq）等待时间（等待时间（Wq，wq）系统中顾客的数量（系统中顾客的数量（L，L）逗留时间（逗留时间（W，w）排队论中的假
36、设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是到达间隔时间服从指数分布，这又等价于说到达等效的说法是到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。许多有用的结果。排队论课件44模型之：模
37、型之：M/M/c排队模型排队模型1.M/M/1模型顾客按照速率为的泊松过程到达，顾客的服务时间是独立同分布的随机变量，通常分布设为均值为1的指数分布。假设顾客按照到达的顺序接受服务，即FCFS服务。例如，如果“顾客”表示到达计算机系统的作业任务，那么“服务台”代表计算机系统。另外一种M/M/1队列的解释为：顾客代表消息，而服务台代表通信信道。排队论课件45随机过程和概率论在排队论中的应用1.把排队过程看成生灭过程如果如果N（t）表示时刻）表示时刻t系统中的顾客数，则系统中的顾客数，则N（t），），t0就构成了一个随机过程。如就构成了一个随机过程。如果用果用“生生”表示顾客的到达，表示顾客的到达
38、，“灭灭”表示顾客的离去，则对许多排队过程来说，表示顾客的离去，则对许多排队过程来说，N（t），），t0是一类特殊的随机过程是一类特殊的随机过程-生灭过程。服务员忙的时间比率：服务员忙的时间比率：=/=顾客到达速率顾客到达速率/服务速率，服务速率，也称为服务强度。2.由生灭过程得到几何分布根据连续生灭过程稳定的条件，要求根据连续生灭过程稳定的条件，要求1，根据连续时间生灭过程的计算公式，以，根据连续时间生灭过程的计算公式，以得到系统在稳定状态下，有得到系统在稳定状态下，有k个顾客的概率如下：个顾客的概率如下：Pk=(1-)k,P0=1-对于稳定的系统对于稳定的系统(t=e(-)t排队论课件50
39、2.M/M/c模型模型M/M/c队列模型如下队列模型如下：该队列系统的顾客到达为泊松流，到达速率为，有并列的c个服务台，每个服务台的服务速率为，服务规则为FCFS。所有的服务台共享一个公用的队列。该队列是一个生灭过程模型，其生灭速率为：k=，k=0,1,2,k=ckc根据的生灭过程特点，可以得到下面在M/M/c队列中的常用公式。C个服务台排队论课件51M/M/c模型系统运行指标模型系统运行指标系统的服务强度系统的服务强度，所有服务台是空的概率，所有服务台是空的概率P0,所有服务所有服务台都在忙的概率台都在忙的概率P,，平均等待顾客数量平均等待顾客数量Lq,系统中平均系统中平均顾客数量顾客数量L
40、，平均系统逗留时间，平均系统逗留时间W,平均排队等候时间平均排队等候时间Wq,分别为：分别为：排队论课件52M/M/c模型系统运行指标模型系统运行指标等价地：系统中的平均顾客数量等价地：系统中的平均顾客数量L=c+P0(c)c/c!(1-)2其中，平均等待顾客数量Lq=P0(c)c/c!(1-)2令随机变量令随机变量M表示表示“忙忙”服务台的数量，服务台的数量，EM=c=/所以，任意一个服务台的利用率=/（c）在多服务台系统中的Little公式：=/（c），L=Lq+c。请同学们思考：一个M/M/c系统与c个M/M/1系统比较，那一种效率高？排队论课件53基本排队模型记号方案基本排队模型记号方
41、案ServerQueueArrival顾客到达时间间隔分布顾客到达时间间隔分布/服务时间分布服务时间分布/服务台数目服务台数目/排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数量顾客总体数量/排排队规则队规则(Kendall记号记号)M/M/1/FCFS M/M/1/M:负指数分布负指数分布(Markovian)D:定长分布定长分布(常数时间常数时间)Ek:k阶阶Erlang分布分布G:普通的概率分布普通的概率分布(任意概率分布任意概率分布)排队论课件54基本排队模型记号基本排队模型记号系统状态系统状态:L=排队系统顾客的数量排队系统顾客的数量,队长。队长。N(t)=在时间在时
42、间 t 排队系统中顾客的数量。排队系统中顾客的数量。Lq =等待服务的顾客的数量等待服务的顾客的数量,队列长度。队列长度。Pn(t)=在时间在时间t,排队系统中恰好有排队系统中恰好有n个顾客的概个顾客的概率。率。s=服务台的数目。服务台的数目。排队论课件55基本排队模型基本排队模型统计平稳条件下的记号统计平稳条件下的记号 n =系统有系统有n个顾客时的平均到达率（单位时间内平均到个顾客时的平均到达率（单位时间内平均到达的顾客人数即是平均到达率）达的顾客人数即是平均到达率）n =系统有系统有n个顾客时的平均服务率（单位时间内被服务个顾客时的平均服务率（单位时间内被服务完的顾客数即是平均服务率）完
43、的顾客数即是平均服务率）=对任何对任何n都是常数的平均到达率都是常数的平均到达率.=对任何对任何n都是常数的平均服务率都是常数的平均服务率.1/=期望到达间隔时间期望到达间隔时间1/=期望服务时间期望服务时间 =服务强度，服务强度，或称使用因子，或称使用因子，/排队论课件56统计平稳条件下的系统运行指标统计平稳条件下的系统运行指标平均系统队长平均系统队长平均等待队长平均等待队长平均排队等待时间平均排队等待时间平均系统逗留时间平均系统逗留时间排队论课件57L,W,Lq,Wq的关系的关系Littlesformulae排队论课件58M/M/1/或或M/M/1模型模型一个基本的排列模型.顾客到达时间间
44、隔以及服务时间都服从负指数分布，一个服务台。称为服务强度，与到达率、服务率满足：排队论课件59M/M/1举例举例排队论课件60M/M/1/N/单一服务台，固定长度单一服务台，固定长度固定长度排队意味着若到了最大系统容量顾客将不能进固定长度排队意味着若到了最大系统容量顾客将不能进入系统入系统.排队论课件61M/M/1/N/举例举例排队论课件62增加更多服务台增加更多服务台M/M/c所有服务台是空的概率所有服务台是空的概率P0,和所有服务台都和所有服务台都在忙的概率在忙的概率P,需要下面比较复杂的公式需要下面比较复杂的公式:排队论课件63M/M/c举例举例排队论课件64其他模型，分类规则其他模型，
45、分类规则M/M/c/K/K顾客来源是有限的服务系统顾客来源是有限的服务系统.例如：例如：一个饭店一个饭店有有X张桌子和张桌子和Y个服务生服务来源有限的顾客个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统服务时间不变的服务系统.D/M/1确定性到达模式确定性到达模式,及负指数分布服务时间及负指数分布服务时间.例如：例如：医生赴约治病的时间表医生赴约治病的时间表.M/Ek/1服务服从服务服从Erlang分布分布.例如：用相同平均时间例如：用相同平均时间去完成一些程序。去完成一些程序。排队论课件65应用：应用：校园网的设计和调节收费校园网的设计和调节收费问题的提出：问题的提出：根据用户数
46、量研究通信端口的设计规模，以及根据用户数量研究通信端口的设计规模，以及通过适当收取线路调节费来控制上网时间。通过适当收取线路调节费来控制上网时间。1）m个用户，每个用户平均每天（个用户，每个用户平均每天（16h计）上计）上网网1.5h，求，求n/m。(n为通信端口数为通信端口数)2）m=150,按设定的按设定的n讨论平均每个用户每天讨论平均每个用户每天上网上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率产生抱怨的可能性及通信端口的平均使用率3）给出一种合理的分段计时收取线路调节费）给出一种合理的分段计时收取线路调节费的方案。的方案
47、。排队论课件66问题的分析：问题的分析：排队系统：由信息网络和用户构成排队系统：由信息网络和用户构成服务台服务台：网络的通信端口，个数：网络的通信端口，个数n顾客：用户，个数（顾客源数）顾客：用户，个数（顾客源数）m,顾客顾客总体无限（因为上网次数不限）总体无限（因为上网次数不限）平均忙期：一天连续工作实际时间，平均忙期：一天连续工作实际时间，16h系统服务：即时制（只要时间允许，不系统服务：即时制（只要时间允许，不限制上网人数，但不允许用户在系统内限制上网人数，但不允许用户在系统内排队等候排队等候）排队论课件67问题的假设：问题的假设：1）每个用户上网随机独立，记为单位时间平均到达（上网）率
48、2）n个通信端口的使用随机独立，记为单位时间平均服务率（上网人数）3）顾客接受一次服务后仍回顾客总体4）收费仅为了调节线路，控制上网时间，不追求经济利益。5）不考虑现实生活中要收取的线路基本费。排队论课件68模型的建立与求解：模型的建立与求解：用户平均上网人数（顾客平均到达率）服从参用户平均上网人数（顾客平均到达率）服从参数为数为 的泊松分布的泊松分布平均上网（服务）时间服从参数为平均上网（服务）时间服从参数为 的负指数的负指数分布分布排队模型为排队模型为:M/M/n/n/（容量有限系统）（容量有限系统）顾客到达时间间隔分布顾客到达时间间隔分布/服务时间分布服务时间分布/服务台数目服务台数目/
49、排队系统允许的最大顾客容量排队系统允许的最大顾客容量/顾客总体数量顾客总体数量/排队规则排队规则排队论课件69模型求解：模型求解：问题问题1，m个用户，每个用户平均每天（个用户，每个用户平均每天（16h计）上网计）上网1.5h，求，求n/m。(n为通信端口数为通信端口数)T:每天总上网时间每天总上网时间排队论课件70问题2，m=150,按设定的n讨论平均每个用户每天上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率通常通信端口为通常通信端口为16口、口、32口、口、64口、口、128口等口等每个用户每天上网时间为每个用户每天上网时间为1.5h时，时
50、，即服务时间即服务时间1/=1.5排队论课件71系统满员率：系统满员率：系统可上网率系统可上网率单位时间端口的平均使用率单位时间端口的平均使用率：排队论课件72=12.4263-16*0.3906*0.8837=6.9035其它指标值：排队论课件73排队论课件74UNIT2排队网络模型 在工程实践中，除遇到孤立的排队问题外，分析人员还经常遇到多个互连排队的问题，如顾客流的分开与合并，队列的串并连组合等。排队网络模型就是来解决这些问题。主要包括开环排队网络和闭环排队网络，具体应用请查阅相关资料。QuickPass系统排队问题UNIT3应用之：排队论课件76在游乐园中的频频排队在游乐园中的频频排队