《排队论讲义》PPT课件.ppt

《《排队论讲义》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《排队论讲义》PPT课件.ppt（125页珍藏版）》请在三一办公上搜索。

1、排队论Queueing Theory,主讲：周在莹,排队论课件,2,CONTENTS,PREPARATION:概率论与随机过程 UNIT 1 排队模型 UNIT 2 排队网络模型 UNIT 3 应用之：QUICK PASS系统结束语,排队论课件,3,PREPARATION 概率论和随机过程,Part 1概率论基础1。概率的定义 概率关系着对时间的数量分配。一个事件A的概率 P(A)是对应事件A要发生可能性的数量分配。概率有很多不同的定义，常用的有三种：(1)古典定义：P(A)=NA/N 其中N是可能结果的总个数，NA是事件A在其中发生的结果的个数。例1.求抛两个骰子并且决定和为7的概率p。总共

2、有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是互斥的，则P（A U B）=P（A）+P（B）,排队论课件

3、,5,2 条件概率和独立性 条件概率：假定事件B已经发生时，事件A发生的条件概率P(A|B)可以定义如下：P（A|B）=P（AB）/P（B）独立性：如果P(AB)=P(A)P(B)，事件A和B叫做相互独立的事件独立性的概念可以推广到三个或多个事件。,排队论课件,6,3 全概率公式和贝叶斯定理全概率公式：给定一组互斥事件E1，E2，En，这些事件的并集包括所有可能的结果，同时给任一个任意事件A，那么全概率公式可以表示为：n P(A)=P(A|Ei)P(Ei)i=1 把计算A的概率分解为一些容易计算的概率之和。贝叶斯定理：P(Ei|A)=P(A|Ei)P(Ei)P(A|Ei)P(Ei)也称为后验概

4、率公式，是在已知结果发生的情况下，求导致结果的某种原因的可能性的大小。,排队论课件,7,Part 2.随机变量的数字特征,随机变量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的偏离程度。均方差：方差的开方称为均方差，或标准方差，记为x 二阶矩：连续情况：EX2=x2f(

5、x)dx 积分区间从-，离散情况：EX2=k2Px=k all k,排队论课件,8,3 协方差：两个随机变量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-1 0 1/4 求 E(X),D(X),E(Y),D(Y),cov(X,Y),r(X,Y),排队论课件,9,Part 3 几种重要的概率分布,1 贝努里分布它的概率分布为：PX=1=p，PX=0=1-p它也称两点分布或（

6、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次贝努里实验中首次出现成功的概率。,排队论课件,10,几何分布有一个重要的性质-后无效性：在前n次实验未出现成功的条件下，再经过m次实验（即在n+m次实验中）首次出现成功的概率，等于恰好需要进行m次实验出现首次成功的无条件概率。用式子表达：PX=n+m|Xn=PX=m(请同学们试证明之）这种与过去历史无关的性质称为马尔可夫性。几何分布在我们下面讲的排队论中是非常重要。它

7、可以描述某一任务（或顾客）的服务持续时间。4 泊松分布（Poisson）PX=k=k e-/k!k=0,1,2,泊松分布是最重要的离散型概率分布之一，它作为表述随机现象的一种形式，在计算机性能评价等实践中扮演了重要的角色。在实际系统模型中，一般都要假定任务（或顾客）的到来是服从泊松分布的。实践也证明：这种假设是有效的。,排队论课件,11,5（负）指数分布 它是一种连续型的概率分布，它的概率密度为 f（x）=e-x x0 0 x0,t0，有 Ps+t|s=Pt 在离散型随机变量中，只有几何分布具有无后效性。这两种分布可以分别用来描绘离散等待时间和连续等待时间。在排队理论中，指数分布是很重要的。,

8、排队论课件,12,6 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-爱尔朗分布在排队模型中，得到广泛应用。如：假定顾客在到达窗口排队必须通过一个关口，这个关口由k层构成，通过每层的时间服从参数为的指数分布，这样顾客通过整个关口到达窗口排队时，就实现了爱尔朗分布。如下图：k 2 1 0000 窗口,排队论课件,13,Pa

9、rt 4 随机过程,随机过程是定义在给定的概率空间上的一族随机变量 X(t)，t T。我们知道：一个随机变量是定义在样本空间S上的函数，则随机过程实际上就是一个函数族X（t，s）|s S，t T。若t固定，随机过程X（t，s）就是随机变量X（t）所取的值，称为在t时刻的状态。若s固定，它是t的函数，称为随机过程的样本函数或样本曲线。,排队论课件,14,随机过程的例子,为了更好的理解随机过程，我们从一个例子开始。例如，n个同样的电阻，同时记录它们热噪声的电压波形。电阻上的热噪声是由于电阻中的电子的热运动引起的，因此，在t1时刻电阻上的热噪声电压是一个随机变量，并记为 x(t1)，也就是说t1时刻

10、任一电阻r(i)上的噪声电压x(i,t1)是无法预先确切地知道的。这里n支电阻的热噪声电压的集合是这个随机实验的样本空间S。对于某一支电阻，其热噪声电压是一时间函数x(i，t)，是随机过程的样本函数。对所有电阻来说，其热噪声电压就是一族时间函数，记为 x(t)，这族时间函数就是“随机过程”，族中每一时间函数称为随机过程的样本函数。,排队论课件,15,Part 5 马尔可夫过程,马尔可夫过程(Markov Process)是具有无后效性的随机过程。无后效性是指：当过程在tn时刻所处的状态为已知时，过程在大于tn的时刻所处状态的概率特性只与过程在tn时刻所处的状态有关，而与过程在tn时刻以前的状态

11、无关。换言之，对于随机过程X（t），t T，如果对于任意参数 t0t1t2tn t,在X(t0),X(t1),X(tn)的值已知的情况下，X(t)的条件分布只与X(tn)的状态有关，即：P X(t)x|X(tn)=xn,X(tn-1)=xn-1,X(t0)=x0=P X(t)x|X(tn)=xn 此条件称为过程的无后效性或过程的马尔可夫性。t0 t1 tn-1 tn t,排队论课件,16,Part 6 生灭过程,生灭过程是一种特殊类型的马尔可夫过程，在系统性能评价等实际模型中是非常重要的。（1）离散时间生灭过程 对于离散时间生灭过程，所有的一步转移只发生在相邻的状态之间。转移概率矩阵P是一个夹

12、层的矩阵，其中，对于所有的|i-j|1有pij=0(2)连续时间生灭过程 一个连续时间，状态空间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只球中，中间号码X的分布规律。,排队论课件,18,习题解答,1把从10个电阻中取出3个的各种可能取法

13、作为样本点全体，这是古典概率，其总数为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个中取一个，于是：pk=PX=k=C(k-1,1)C(5-k,1)/C(5,3),k=2,3,4 所以，X的分布律为：X 2 3 4 Pk 0.3 0.4 0.3,排队论课件,19,UNIT1 排队模型,排队论（queueing theory），或称随机服务系统理论，作为运筹学研究的一种有力

14、手段，研究的内容有3个方面：系统的性态，即与排队有关的数量指标的概率规律性；系统的优化问题；统计推断，根据资料合理建立模型。目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论不仅在理论上达到了成熟阶段，而且其应用范围不断增加。概括起来，它已在电话交换网、公路、铁路、航空运输、工程管理、公共服务、货物存储和生产流水线过程等方面得到了广泛的应用。特别地，排队论是计算机通信网络和计算机系统中通信信息量研究的基础理论，信息系统通信问题的定量研究往往要求借助于排对论才能得到解决。,排队论课件,20,排队常常是件很令人恼火的事情尤其是在我们这样的人口大国,电话亭1978年在北京15%的电话要在

15、1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队 银行窗口，ATM游乐场的游乐项目医院、理发、火车售票,在现实生活中，为了接受某种服务，排队等待是常见的现象。从排队等待得到抽象的物理模型，进一步建立数学模型的一整套理论就是所谓的排队论。,排队论课件,21,什么是排队论？,排队论是专门研究带有随机因素，产生拥挤现象的优化理论。亦称为随机服务系统理论。因为被服务者到达系统的时间是不确定的。有关于由服务设施与被服务者构成的排队服务系统的理论。,排队论课件,22,本讲主要掌握：,基本模型M/M/1 模型M/M/c 模型其他模型应用：校园网的设计和调节收费,排队论课件,23,基本的排队模型,基本

16、组成概念与记号指数分布和生灭过程,排队论课件,24,典型排队系统模型,顾客到达:在队列中排队 服务台服务 顾客离开 输入源的 到达规律 队列大小？特性？到达方式？服务规律？服务协议？在本单元中，我们主要介绍排队系统的组成和特征，排队系统的到达和服务，经典排队模型等内容。顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。,输入源,。,排队论课件,25,基本组成,排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等),排队论课件,26,基本排队模型 输入过程,

17、顾客来源 有限/无限顾客数量有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间.服从某一概率分布.(指数分布)顾客的行为假定在未服务之前不会离开;当看到队列很长的时候离开；从一个队列移到另一个队列。,顾客到达的方式通常是一个一个到达的，也可能是成批的。顾客的到达总是有一定规律，即到达过程或到达时间间隔符合一定的分布，称到达分布。顾客的到达或到达时间通常假定为相互独立的且遵从同一分布的随机变量。,排队论课件,27,基本排队模型队列/排队规则,队列队列容量有限/无限排队方式单队列并联式多队列串联式多队列杂乱队列,对于一个有限大小的队列来说，顾客可能从队列中丢失。有什么样的服务协议就有

18、什么样的与之对应的排队方式。,排队论课件,28,基本排队模型服务规则,服务机构服务设施，服务渠道与服务台服务台数量单服务台系统多服务台系统无限服务台系统服务协议先来先服务（FCFS）后来先服务（LCFS）随机服务（RSS）有优先权的服务（PR）服务时间分布指数,常数,k阶Erlang,一般服务台对顾客是一个一个进行服务的，且对每一个顾客的服务时间长短不一。将服务时间看作随机变量，那么它们是相互独立的且遵循同一分布。因此描述服务规律时，采用服务时间的概率分布，即服务分布。服务分布同到达分布一样，到底属于哪一种概率分布，要根据具体排队问题进行分析。,排队论课件,29,服务协议,（a）先来先服务 顾

19、客到达的先后次序排队接受服务，用 FCFS（firstcomefirstserved）表示。（b）后来先服务（或称先来后服务）队列是一种堆栈形式（临时寄存货物的地方）。当某一顾客服务结束时，如果在队列中有两个以上等待的顾客，则把最后到达的顾客作为下一个服务的对象。用LCFS（lastcomefirstserved）表示。（c）随机选择服务 在服务时从等待顾客中随意抽取一个进行服务。（d）优先服务和动态优先服务 预先规定优先顺序位的类别、且给到达顾客规定优先顺序位作为标记的优先权。通常按FCFS进行服务。优先权分为三类：排队优先权、中断优先权、动态优先权。如计算机中断的优先级。（e）处理器共享（

20、processor sharing，PS）服务台的处理能力被平均分配给队列中的所有顾客，没有排队现象出现，当顾客的数量增加时，只是顾客的服务时间变长。如：网络服务系统。（f）无限服务台（infinite server，Is）在这种情况下，队列中的每个顾客接受完全相同的服务，而且就好像它是唯一的一个顾客一样。好像对于每个顾客都可以“克隆”出一个新的服务台，而且克隆的数目可以无限。,排队论课件,30,排队系统的到达和服务,1 到达规律的描述（1）主要描述参数（a）到达时点 将某一时刻设为t0，顾客依次到达的时刻用t-1t0t1t2表示，如果在时刻tk到达的顾客为Nk，则到达时点可用tk、Nk）表示

21、。（b）平均到达间隔一个顾客到达时刻之间的时宽为到达间隔。（c）到达速率单位时间到达顾客的平均数叫到达速率，也称到达密度或输入速率。（2）到达规律 顾客的到达规律可以用概率来描述，两个顾客到达的时间间隔是独立的随机变量，服从同一概率分布时。常用的分布规律有：（a）一般到达（b）泊松到达（c）爱尔朗到达（d）等间隔到达,排队论课件,31,泊松分布和负指数分布在排队论中的应用,泊松分布（Poisson）：PX=k=k e-/k!k=0,1,2,，x=x=泊松分布是最重要的离散型概率分布之一，也是表述随机现象的一种重要形式。在实际系统模型中，一般都要假定任务（或顾客）的到来是泊松分布的。实践也证明：

22、这种假设有效。如果顾客到达的人数是符合泊松分布，即在时间T内到达有k个顾客到达的概率为：p=（T）k e-T/k!，在时间T内顾客到达的平均顾客数=T，平均到达速度（顾客数/秒）=服从泊松分布过程的到达被认为是随机到达，因为当顾客根据泊松过程到达时，顾客在各个时刻到达的可能性相同并与其它顾客的到达无关。,排队论课件,32,（负）指数分布：它是一种连续型的概率分布，它的概率密度：f（x）=e-x x0 它的分布函数：F（x）=1-e-x x0 指数分布的一个有用的性质是它的数学期望等于标准差：x=x=1/泊松分布和指数分布的关系：如果顾客以泊松到达,则顾客到达的时间间隔Ta服从指数分布，即：PT

23、at=1-e-t,ETa=1/因此，平均到达的时间间隔是到达速率的倒数。,排队论课件,33,负指数分布,密度函数,均值,方差,随机变量 T（两个顾客相继到达的时间间隔）,分布函数,排队论课件,34,负指数分布性质1,fT(t)是一个严格下降函数,排队论课件,35,负指数分布性质2,无后效性（无记忆性）,不管多长时间(t)已经过去，逗留时间的概率分布与下一个事件的相同.或者说，后一个顾客到来所需时间与前一个顾客到来所需时间无关。,排队论课件,36,负指数分布性质3,几个独立的指数分布的随机变量的最小也服从指数分布,几个独立的指数分布的随机变量的和还是一个服从指数分布的随机变量,排队论课件,37,

24、负指数分布性质4,负指数分布,Poisson分布,在t时间内已经服务n个顾客的概率,1/:平均服务时间,平均服务率=,相继顾客到达平均间隔时间,排队论课件,38,负指数分布性质5,排队论课件,39,排队论基本概念部分练习,练习1：1。指出下列排队系统中的顾客和服务台：（1）自行车修理店；（2）按客户订单进行加工的加工车间（3）机场起飞的客机（4）十字路口红灯前的车辆 2。判断正误（1）若到达排队系统的顾客人数服从泊松分布，则依次到达的两名顾客之间的间隔时间服从指数分布。（2）在一个排队系统中，不管顾客到达和服务时间的情况如何，只要运行时间足够长的时间后，系统将进入稳定状态。（3）在排队系统中，

25、顾客等待时间的分布不受排队规则的影响。,排队论课件,40,2 服务规律的描述,(1)主要描述参量（a）平均服务时间 设服务时间的分布函数为F（t），则服务时间的平均表示为:1/=t dF(t)其中称为平均服务速率，平均一个顾客的服务时间。（b）服务速率 一般指平均服务速率，单位时间内被服务完的顾客数，用来表示。(2)服务规律 服务规律通常是就服务时间的分布而言的。服务时间分布典型地有指数分布、爱尔朗分布、一般分布等。结论：顾客到达规律和服务规律都是通过概率来描述的，所以概率论是排队论的基础。,排队论课件,41,经典排队模型,它的格式为：ABnSZ 其中符号的含义如下：A：顾客到达的规律；B：服

26、务时间分布；n：服务台的数目；S：队列容量的大小；Z：服务规程。当队列的大小为无穷大、且服务规程为先来先服务时，经典排队模型可简化为 ABn 不同类型的排队，A、B可用如下约定的字母表示。M：如果用于描述到达，表示泊松到达过程，到达时间间隔符合指数分布；如 果用于描述服务，则指具有指数分布的时间。M表示Markov的第一个字母。G：一般分布。表示到达间隔时间或服务时间服从一般分布。G是General的第 一个字母。Ek：k-爱尔朗分布。表示到达间隔时间或服务时间服从k-爱尔朗分布。E是Erlang 的第一个字母。D:定长分布(常数时间)H：超几何分布。L：H项式分布。Z代表的服务规程典型的有：

27、FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；PR：优先权服务。Ba：集体（批量）服务。GD：一般规约服务，即通用规约服务。,排队论课件,42,3 基本排队关系,在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系统，若满足以下三个条件：（1）排队系统能够进入统计平衡状态；（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；（3）系统中任一顾客不会永远等待，系统也不会永无顾客到达。则下列 Little 公式成立（排队论中的通用公式）：（1）Lq=Wq 我们知道一个顾客的平均排队等待时间是Wq，且顾客是以平均速率到达，所以在时间Wq内有Wq个顾客到达，L

28、q表示排队等待服务的平均顾客数量，所以有：Lq=Wq（2）L=W 系统中的平均顾客数（包括等待的和正在被服务的顾客）等于顾客的平均到达速率乘以一个顾客在系统中花费的平均时间。（3）W=Wq+1/一个顾客在系统中花费的时间，就是它等待服务的时间加上被服务的时间。,排队论课件,43,4 队列分析的任务和假设条件,队列分析的基本任务是：给出如下输入信息（概率分布）：到达速率（）服务时间（1/)求出如下输出信息（均值、标准差）：等待顾客的数量（Lq,Lq）等待时间（Wq，wq）系统中顾客的数量（L，L）逗留时间（W，w）排队论中的假设：在排队分析中，最重要的一个假设是到达速率服从泊松分布，等效的说法是

29、到达间隔时间服从指数分布，这又等价于说到达是随机的并彼此独立。我们几乎一直要作这一假定。没有它，大部分的排队分析是不可能的。在这个假定的条件下，我们会发现仅仅知道到达速率和服务时间的均值和标准差就可以得到许多有用的结果。,排队论课件,44,模型之：M/M/c排队模型,1.M/M/1模型 顾客按照速率为的泊松过程到达，顾客的服务时间是独立同分布的随机变量，通常分布设为均值为1的指数分布。假设顾客按照到达的顺序接受服务，即FCFS服务。例如，如果“顾客”表示到达计算机系统的作业任务，那么“服务台”代表计算机系统。另外一种M/M/1 队列的解释为：顾客代表消息，而服务台代表通信信道。,排队论课件,4

30、5,随机过程和概率论在排队论中的应用,1.把排队过程看成生灭过程如果N（t）表示时刻 t 系统中的顾客数，则N（t），t 0就构成了一个随机过程。如果用“生”表示顾客的到达，“灭”表示顾客的离去，则对许多排队过程来说，N（t），t 0是一类特殊的随机过程-生灭过程。服务员忙的时间比率：=/=顾客到达速率/服务速率，也称为服务强度。2.由生灭过程得到几何分布 根据连续生灭过程稳定的条件，要求 1，根据连续时间生灭过程的计算公式，以得到系统在稳定状态下，有k个顾客的概率如下：Pk=(1-)k,P0=1-对于稳定的系统(1),稳定状态概率服从参数为1-的改进型几何分布。3.由几何分布可以得到系统中平

31、均顾客数量和等待时间 几何分布：PX=k=p(1-p)k-1,k=1,2,几何分布的数学期望为：1/p,方差为:q/p2 令 p=1-,计算出系统中顾客数量的均值和方差：L=EN=/(1-)VarN=/(1-)2令随机变量R代表稳定状态的响应时间，即一个顾客在系统中花费的时间，则W=ER，根据L=W，可以得到:W=1/(1-),排队论课件,46,随机过程和概率论在排队论中的应用,4.由系统中顾客平均数量和等待时间得队列中顾客数量w和等待时间Tw令随机变量Wt代表等待时间，St代表服务时间，则：R=Wt+St ER=EWt+ESt=EWt+1/所以顾客的平均等待时间Wq=EWt=ER-1/=/(

32、1-)即：Wq=/(1-)令随机变量Wi表示队列中正在等待的顾客数量，再根据little公式，Lq=EWi=*EWt=*/(1-)=2/(1-)即：Lq=2/(1-),排队论课件,47,M/M/1 系统运行指标,系统中平均顾客数：L=/(1-),顾客在系统中平均等待时间：W=1/(1-)顾客在队列中平均等待时间：Wq=/(1-)队列中平均顾客数：Lq=2/(1-)在单服务台系统中的little公式：=1/,L=Lq+通用的little公式：Lq=Wq L=W W=Wq+1/,排队论课件,48,M/M/1 模型练习,练习2：1 一个书店平均每分钟有3个顾客到达，正常情况有48个顾客在书店中，求每

33、一个顾客在商店花费的平均时间？2 一条通信线路的带宽是2000位/秒，该线路用来传8位一个的字符，所以该线路的最大速率是250字符/秒,来自应用要求是12000字符/分。求：（1）等待被传输的平均字符数Lq,（2）每个字符平均传输时间W.3 假定一个电话通话的持续时间平均3分钟，一个人等待电话平均最大可以忍耐3分钟，求可以支持的最大呼叫量？,排队论课件,49,M/M/1模型练习,4。某修理店只有一个修理工，来修理的顾客到达过程为Poission流，平均4人/小时；修理时间服从负指数分布，平均需要6分钟。试求：（1）修理店空闲的概率；（2）店内恰有三个顾客的概率（3）店内至少有一个顾客的概率（4

34、）在店内的平均顾客数（5）每位顾客在店内的平均逗留时间（6）等待服务的平均顾客数（7）每位顾客平均等待服务时间（8）顾客在店内等待时间超过10分钟的概率 M/M/1模型中常用公式：系统中有k个顾客的概率，k=(1-)k,0=1-系统中顾客数量的均值和方差：EN=/(1-)VarN=/(1-)2M/M/1 队列中一般的公式：L=EN,W=1/(1-)，Wq=/(1-)，Lq=2/(1-)在单服务员系统中的little公式：=1/,L=Lq+通用的little公式：Lq=Wq L=W W=Wq+1/顾客在系统中的逗留时间T，服从参数为-的负指数分布，即：PTt=e(-)t,排队论课件,50,2.M

35、/M/c模型,M/M/c队列模型如下：该队列系统的顾客到达为泊松流，到达速率为，有并列的c个服务台，每个服务台的服务速率为，服务规则为FCFS。所有的服务台共享一个公用的队列。该队列是一个生灭过程模型，其生灭速率为：k=，k=0,1,2,k=c k c 根据的生灭过程特点，可以得到下面在M/M/c队列中的常用公式。,C个服务台,排队论课件,51,M/M/c模型系统运行指标,系统的服务强度，所有服务台是空的概率P0,所有服务台都在忙的概率 P,，平均等待顾客数量Lq,系统中平均顾客数量L，平均系统逗留时间W,平均排队等候时间Wq,分别为：,排队论课件,52,M/M/c模型系统运行指标,等价地：系

36、统中的平均顾客数量 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,基本排队模型记号方案,顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall 记号)M/M/1/FCFS M/M/1/M:负指数分布(Markovian)D:定长分布(常数时间)Ek

37、:k阶Erlang 分布G:普通的概率分布(任意概率分布),排队论课件,54,基本排队模型记号,系统状态:L=排队系统顾客的数量,队长。N(t)=在时间 t 排队系统中顾客的数量。Lq=等待服务的顾客的数量,队列长度。Pn(t)=在时间t,排队系统中恰好有n个顾客的概率。s=服务台的数目。,排队论课件,55,基本排队模型统计平稳条件下的记号,n=系统有n个顾客时的平均到达率（单位时间内平均到达的顾客人数即是平均到达率）n=系统有n个顾客时的平均服务率（单位时间内被服务完的顾客数即是平均服务率）=对任何n都是常数的平均到达率.=对任何n都是常数的平均服务率.1/=期望到达间隔时间1/=期望服务时

38、间=服务强度，或称使用因子，/,排队论课件,56,统计平稳条件下的系统运行指标,平均系统队长,平均等待队长,平均排队等待时间,平均系统逗留时间,排队论课件,57,L,W,Lq,Wq的关系,Littles formulae,排队论课件,58,M/M/1/或 M/M/1 模型,一个基本的排列模型.顾客到达时间间隔以及服务时间都服从负指数分布，一个服务台。称为服务强度，与到达率、服务率 满足：,排队论课件,59,M/M/1 举例,排队论课件,60,M/M/1/N/单一服务台，固定长度,固定长度排队意味着若到了最大系统容量顾客将不能进入系统.,排队论课件,61,M/M/1/N/举例,排队论课件,62,

39、增加更多服务台 M/M/c,所有服务台是空的概率P0,和所有服务台都在忙的概率 P,需要下面比较复杂的公式:,排队论课件,63,M/M/c 举例,排队论课件,64,其他模型，分类规则,M/M/c/K/K顾客来源是有限的服务系统.例如：一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及负指数分布服务时间.例如：医生赴约治病的时间表.M/Ek/1服务服从 Erlang 分布.例如：用相同平均时间去完成一些程序。,排队论课件,65,应用：校园网的设计和调节收费,问题的提出：根据用户数量研究通信端口的设计规模，以及通过适当收取线路调节

40、费来控制上网时间。1）m个用户，每个用户平均每天（16h计）上网1.5h，求n/m。(n为通信端口数)2）m=150,按设定的n讨论平均每个用户每天上网1h,1.5h,2h,3h,4h,5h的可能性，线路忙产生抱怨的可能性及通信端口的平均使用率3）给出一种合理的分段计时收取线路调节费的方案。,排队论课件,66,问题的分析：,排队系统：由信息网络和用户构成服务台：网络的通信端口，个数n顾客：用户，个数（顾客源数）m,顾客总体无限（因为上网次数不限）平均忙期：一天连续工作实际时间，16h系统服务：即时制（只要时间允许，不限制上网人数，但不允许用户在系统内排队等候）,排队论课件,67,问题的假设：,

41、1）每个用户上网随机独立，记 为单位时间平均到达（上网）率2）n个通信端口的使用随机独立，记 为单位时间平均服务率（上网人数）3）顾客接受一次服务后仍回顾客总体4）收费仅为了调节线路，控制上网时间，不追求经济利益。5）不考虑现实生活中要收取的线路基本费。,排队论课件,68,模型的建立与求解：,用户平均上网人数（顾客平均到达率）服从参数为 的泊松分布平均上网（服务）时间服从参数为 的负指数分布排队模型为:M/M/n/n/（容量有限系统）,顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则,排队论课件,69,模型求解：,问题1，m个用户，每个用户平均

42、每天（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时，即服务时间1/=1.5,排队论课件,71,系统满员率：,系统可上网率,单位时间端口的平均使用率：,排队论课件,72,=12.4263-16*0.3906*0.8837=6.9035,其它指标值：,排队论课件,73,排队论课件,74,UNIT2 排队网络模型,在工程实践中，

43、除遇到孤立的排队问题外，分析人员还经常遇到多个互连排队的问题，如顾客流的分开与合并，队列的串并连组合等。排队网络模型就是来解决这些问题。主要包括开环排队网络和闭环排队网络，具体应用请查阅相关资料。,QuickPass系统排队问题,UNIT3 应用之：,排队论课件,76,在游乐园中的频频排队会极为扫兴DisneyLand中的FastPass(QuickPass)系统就是想解决这个问题的,排队论课件,77,What is QuickPass?,工作原理：到达的顾客将自己的票插入FastPass的slot中FastPass计算出建议顾客返回的时间间隔(time interval)或时间点或时间窗(t

44、ime window)顾客无需排队，在指定的时间返回就可持票进入,排队论课件,78,怎样缩短排队的等待时间？,银行的排队叫号机 只是有序的组织了顾客，并没有减少等待时间如果能实现知道轮到自己需要等待多少时间，再选择合适的时间来，岂不很好？,排队论课件,79,FastPass存在的问题：,预知的返回时间间隔存在误差按时返回却仍需要排队建议的返回时间间隔太长如果告诉你4小时以后再回来呢？顾客可能不会完全按照安排的时间返回如果新来的顾客不想使用FastPass系统？,排队论课件,80,我们的目的就是对FastPass系统建立合理的离散统计模型（Distributed Statistical Mode

45、l），求出最优的顾客返回时间。,建模的一般步骤以及：*模型的改进*启发与待解决的问题,排队论课件,81,1 模型的假设,游乐园开放时间为8:00-18:00,一天中不同时间的顾客流量不同，比如上午10:00和下午3:00的顾客流量是最大的。顾客的到达时间符合非时间齐次泊松过程(Nonhomogeneous Possion Process)，到达速率是(t)。,排队论课件,82,Poisson Process,排队论课件,83,Poisson Process,排队论课件,84,分析1：能否得到准确的返回时间？,2 在我们开始动手建模之前，先要问几个问题：,排队论课件,85,分析2：使用FastP

46、ass后排队是不是可以避免的？FastPass给出的返回时间只是期望值，而非确定值假设所有的顾客都使用FastPass,但需考虑有的顾客可能会不遵守FastPass给出的返回时间,2 在我们开始动手建模之前，先要问几个问题：,排队论课件,86,分析3：我们优化的目标函数（或cost function）是什么？是排队时间吗？,2 在我们开始动手建模之前，先要问几个问题：,排队论课件,87,优化问题的目标函数为：,3 模型的建立（1）目标函数,排队论课件,88,根据排队论（queueing theory）的分类规则,（X/Y/Z/A）代表一类排队的规则，其中 X:顾客流到达所符合的分布 Y:顾客接

47、受服务的时间所服从的分布 Z:服务台的个数 A:服务台一次可服务的顾客数量（系统的容量）针对各个游乐项目的特点，我们主要讨论两种排队系统:,模型的建立（2）排队模型的分类,排队论课件,89,特点：系统容量为1，顾客的到达是Poisson流，服务时间服从指数分布，只有一条队列,模型的建立（3）电话亭模型,排队论课件,90,求出这类系统的代价函数表达式,模型的建立（3）电话亭模型,排队论课件,91,近似将总的优化目标函数等效为对顾客i的目标函数：,模型的建立（3）电话亭模型,排队论课件,92,模型的建立（3）电话亭模型,排队论课件,93,如果简化c1,c2为常数，并计算第二个人的无需等待返回时间的

48、期望值，得用MatLab能够作出 的函数，并从图中得出结果,模型的求解（4）电话亭模型,排队论课件,94,模型的求解（4）电话亭模型,排队论课件,95,第三个人的无需等待返回时间的期望值，同理可以算出，并用图解法求出,模型的求解（4）电话亭模型,排队论课件,96,但是第4个人，第5个人呢？这种方法太繁琐似乎不好用可否有近似的算法？,排队论课件,97,与前一个模型的区别在于：系统容量是c1,服务时间固定，顾客的到达仍然是Poisson流。,模型的建立（5）过山车模型,排队论课件,98,还要考虑：实际的FastPass系统 有两条队列：FastPass和Standby队列 不考虑standby队列

49、，将得到Greedy algorithm模型 考虑standby队列，将得到效用函数模型,模型的建立（5）过山车,排队论课件,99,排队论课件,100,最简单的情况：只有一条队列，即所有的人都只用FastPass系统为了防止前面的人等的时间太长，过山车只要载满一定数量的人后就开车，假设为80c。用贪心算法（greedy algorithm),将每个顾客尽量安排在离顾客到达时间最近的，且还没有安排满人的一班车上。假设被安排的顾客按照Beta分布到达所被安排的时间段内,模型的建立（5）过山车模型,排队论课件,101,贪心算法,模型的建立（5）过山车模型,排队论课件,102,很容易想到，全局优化的目

50、标变量1.如果开车的时间不固定，则a%是多少最优？就是说顾客坐满多少就开车？2.如果开车的时间间隔是固定的，则多长时间开一次是最优的？衡量的标准：目标函数,模型的建立（5）过山车模型,排队论课件,103,一个区间内的顾客返回示意图,排队论课件,104,目标函数：,模型的建立（5）过山车模型,排队论课件,105,模型的建立（5）过山车模型,怎样求解最优的a%c和最优的开车间隔？对于这类复杂的问题，离散仿真是最好的方法了,排队论课件,106,仿真：用计算机生成一些符合某种分布的随机数据点，模拟离散时间的发生这里的仿真用MatLab完成：步骤：1.生成Poisson顾客流（模拟到达时间）2.给定不同