排队论讲义ppt课件.ppt

排队论,一.概率论及随机过程回顾二.排队论的基本知识三.单服务台负指数分布排队系统分析四.多服务台负指数分布排队系统分析五.一般服务时间M/G/1模型分析六.经济分析_排队系统的最优化,一、概率论及随机过程回顾,随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?,1.1、随机变量与概率分布,一、概率论及随机过程复习,随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?,随机变量连续型随机变量概率密度函数概率分布函数数学期望和方差常见连续型随机变量的概率分布均匀分布指数分布？正态分布？k阶爱尔朗分布？,一、随机变量与概率分布,?爱尔朗分布,为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分布,数理统计方法容易初步判断:期望=标准差,Poisson过程与负指数分布,负指数分布的性质:,马尔可夫性，或无后效性,Poisson过程与Poisson分布的关系：,对于Poisson流：单位时间平均到达的顾客数顾客相继到达的平均间隔时间,定义：设为一个随机过程，若N(t)的概率分布具有以下性质：(1)假设N(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为的负指数分布；(2)假设N(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为的负指数分布；(3)同一时刻是只有一个顾客到达或离去。则称为一个生灭过程。,生灭过程,平稳生灭过程系统状态n平衡方程：“流入=流出”,系统达到平稳状态时：,的分布,系统达到平稳状态时：,平衡方程：,当时才有意义,二、排队论的基本知识,2.1排队模型2.2排队系统的组成和特征,排队论研究的内容,性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.,2.1、排队模型,排队系统的的一般表示,服务机构,(a)一个队列、单服务台（阶段）,(b)一个队列、s个服务阶段,服务机构,服务机构,(c)一个队列、s个服务台一个服务阶段,服务机构,(d)s个队列、s个服务阶段,服务机构,(e)混合型,排队结构,(f)一个队列,(g)s个队列,输入过程顾客总体:有限,无限.顾客到达方式:单个,成批.顾客到达间隔时间:确定的、随机的.顾客到达的独立性:独立,不独立.输入过程的平稳性:与时间无关(平稳的),与时间有关(非平稳的).,2.2、排队系统的组成和特征,顾客到达时间间隔的分布:,：第n个顾客与第n-1个顾客到达的时间间隔；,顾客到达时间间隔的分布:,假定是独立同分布，分布函数为，排队论中常用的有两种：,（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相同!?,例：某医院手术室每小时就诊病人数和手术时间的记录如下：,解：,解：,解：,3.2系统容量有限制的情形(M/M/1/N/FCFS）,状态转移图状态转移方程,求排队系统顾客数的分布状况,其中,求排队系统顾客数的分布状况,队长队列长,计算有关指标,逗留时间等待时间,计算有关指标,系统已满顾客不能到达的概率-损失率,有6个椅子接待人们排队，超过6人顾客就离开，平均到达率3人/小时，理发需时平均15分钟。,7为系统中的最大顾客数。平均到达率:3人/小时平均服务率:4人/小时,举例：单人理发馆排队问题,顾客到达就能理发的概率-相当于理发店内没有顾客等待顾客数的期望值,求有效到达率顾客在理发馆内逗留的期望时间,人/小时,可能的顾客中有百分之几不等待就离开-求系统中有7个顾客的概率,设：m：为顾客总体数，：每个顾客的到达率，m-Ls：系统外顾客的平均数，e=（m-Ls）：为系统有效到达率。,3.3顾客源有限制的情形(M/M/1/m/FCFS）,含义与上节不同对顾客而言，而不是对系统,m,对系统而言,有一个顾客到达的概率,状态转移图,0,1,m,n-1,n,(m-n+1),(m-n),n+1,.,.,m-1,m,.,(m-1),2,状态转移方程,注意到，,求解状态转移方程得,有效到达率,求解顾客数概率分布,等待时间正常运转的平均设备台数,计算有关指标,队长队列长逗留时间,计算有关指标,例：P343#例7,4.1标准的M/M/c模型（M/M/c/）4.2标准的M/M/c/N/型4.3标准的M/M/c/m模型,四.多服务台负指数分布排队系统分析,规定：各服务台工作是相互独立的，且平均服务率相同，均为。整个服务机构的平均服务率为：c(当nc)，n(当nc);记=/,s=/c=/c为服务系统的平均利用率当/c1时，不会排成无限队列。,4.1标准的M/M/c模型（M/M/c/）,1,2,c,.,服务台C个,系统人数n人,1,2,c,.,服务台C个,系统人数n人,nc,状态转移图,0,1,n-1,n,n,(n+1),n+1,.,.,2,2,n-1,n,c,c,n+1,.,.,nc,状态转移方程,4.1标准的M/M/c模型（M/M/c/）,解差分方程，求得状态概率为,4.1标准的M/M/c模型（M/M/c/）,顾客等候的概率,计算有关指标,平均正接受服务的顾客数=正忙的服务台数,队长队列长逗留时间及等待时间,计算有关指标,某售票所有三个窗口，顾客到达服从Poisson过程，到达=0.9人/分钟，服务=0.4人/分钟。设顾客到达后依次排成一队向空闲的窗口购票，如图a.,图a,M/M/c型系统和c个M/M/1型系统的比较,图a,M/M/c型系统和c个M/M/1型系统的比较,属于M/M/c型系统c=3,=/=2.25,s=/c=2.25/31,符合要求.,整个售票所空闲概率,平均队长,平均等待时间和逗留时间,顾客到达后必须等待概率,以上例说明,设顾客到达后在每个窗口前各排一队(其它条件不变),共三队,每队平均到达率为:,M/M/c型系统和c个M/M/1型系统的比较,结果比较,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)=1/，D(V)=2服务强度：=/不论V服从什么分布，只要1,系统就会达到稳态，并有稳态概率为：P0=1-,5.1M/G/1模型,根据波拉切克（Pollacek）-欣钦（Khintchine）公式可导出：,其它相关结果,5.1M/G/1模型,系统对各顾客的服务时间相互独立且为同一个常数v，则有：E(v)=v=1/，D(v)=0波拉切克-欣钦公式可化简为：,5.1M/D/1模型,自学,5.1M/Ek/1模型,6.1排队系统最优化问题6.2M/M/1模型中最优服务率6.3M/M/c模型中最优服务台数c,6.经济分析_排队系统的最优化,系统设计最优化：(静态优化问题)设备达到最大效益系统控制最优化：(动态优化问题)如何运营使某个目标函数最优。,6.1排队系统最优化问题,6.2M/M/1模型中最优服务率,单位时间的费用,Cs：当时服务机构单位时间费用Cw：每个顾客在系统停留单位时间的费用,标准的/M/M/1模型,单位时间的纯利润,G：每服务1人可得的收入（已知）,标准的/M/M/1/N模型,6.2M/M/1模型中最优服务率,6.2M/M/1模型中最优服