排队理论及应用课件.pptx

1、排队理论及应用排队理论及应用目录目录一、排队论的基本知识排队论研究的内容排队论研究的内容n性态问题:排队系统的概率规律,如队长分布,等待时间分布等.n最优化问题:排队系统的最优设计.n统计推断:判定排队系统的类型.顾客源顾客源1、排队排队模型模型排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去服务服务机构机构服务服务台台(a)a)一个一个队列、单服务队列、单服务台台（阶段阶段）服务台服务台1服务台服务台2(b)b)一个一个队列、队列、s s个服务阶段个服务阶段服务服务机构机构服务台服务台1服务台服务台2服务服务机构机构(c c)一个一个队列、

2、队列、s s个服务台个服务台 一个服务阶段一个服务阶段服务台服务台3服务台服务台4服务台服务台1服务台服务台2服务服务机构机构(d d)s s个个队列、队列、s s个服务阶段个服务阶段服务台服务台3服务台服务台4服务台服务台1服务台服务台2:124:243:3214服务服务机构机构(e e)混合混合型型排队排队结构结构服务服务台台(f f)一个一个队列队列服务服务台台(g g)s s个个队列队列 n输入过程输入过程n顾客总体顾客总体:有限有限,无限无限.n顾客到达方式顾客到达方式:单个单个,成批成批.n顾客到达间隔时间顾客到达间隔时间:确定的、确定的、随机的随机的.n顾客到达的独立性顾客到达的

3、独立性:独立独立,不独立不独立.n输入过程的平稳性输入过程的平稳性:与时间无关与时间无关(平稳的平稳的),与时间有与时间有关关(非平稳的非平稳的).2 2、排队系统的组成和特征排队系统的组成和特征n顾客到达时间间隔的分布顾客到达时间间隔的分布:：第：第n n个顾客与第个顾客与第n-1n-1个顾客到达的时间间隔；个顾客到达的时间间隔；nXnT：第：第n n个顾客到达的时刻；个顾客到达的时刻；设设nTTT100,2,1,1nTTXnnn令令1T2TnT1nT1nT0TnXn顾客到达时间间隔的分布顾客到达时间间隔的分布:假定假定 是独立同分布，分布函数为是独立同分布，分布函数为 ，排队论中常用的有两

4、种：排队论中常用的有两种：nX)(tAnX（2 2）最简流（即）最简流（即PoissonPoisson流）（流）（M M）：）：顾客到达时间间隔顾客到达时间间隔 为独立的，为独立的，服从负指数分布，其密度函数为服从负指数分布，其密度函数为（1 1）定长分布（）定长分布（D D）：）：顾客到达时间间隔为确定的。顾客到达时间间隔为确定的。000)(ttetat因为负指数分布因为负指数分布具有无后效性具有无后效性（即（即Markov性）性）n排队及排队规则排队及排队规则n即时制即时制(损失制损失制)n等待制等待制n先到先服务先到先服务:FCFSn后到先服务后到先服务:LCFSn随机服务随机服务n优先

5、权服务：优先权服务：PSn队容量队容量:有限有限,无限无限;有形有形,无形无形.n队列数目队列数目:单列单列,多列多列.n 服务机构服务机构n服务员数量服务员数量:无无,单个单个,多个多个.n队列与服务台的组合队列与服务台的组合n服务方式服务方式:单个顾客单个顾客,成批顾客成批顾客.n服务时间服务时间:确定的确定的,随机的随机的.服务时间和到达服务时间和到达间隔时间至少一个是随机的间隔时间至少一个是随机的.n服务时间分布是平稳的服务时间分布是平稳的.n服务时间分布服务时间分布:设某服务台的服务时间为设某服务台的服务时间为V V，其密度函数其密度函数为为b b（t t），），常见的分布有：常见的

6、分布有：（1 1）定长分布（）定长分布（D D）：）：每个顾客接受服务的时间每个顾客接受服务的时间 是一个确定的常数。是一个确定的常数。（2 2）负指数分布（）负指数分布（M M）：）：每个顾客接受服务时间每个顾客接受服务时间 相互独立，具有相互的负指数分布：相互独立，具有相互的负指数分布：其中其中 ，为一常数。，为一常数。000)(ttetbt0-单位时间平均服务完成的顾客数单位时间平均服务完成的顾客数1/1/-每个顾客的平均服务时间每个顾客的平均服务时间n服务时间分布服务时间分布:（3 3）k k阶爱尔朗（阶爱尔朗（ErlangErlang）分布：每个顾客接受服务分布：每个顾客接受服务 时

7、间服从时间服从k k阶爱尔朗分布，其密度函数为：阶爱尔朗分布，其密度函数为：tkkektkktb)!1()()(1 n符号表示符号表示:X/Y/ZnX 顾客到达时间间隔分布顾客到达时间间隔分布nY-服务时间分布服务时间分布nZ-服务台个数服务台个数nX,Y 可以是可以是:nM-M-负指数分布负指数分布nD-D-确定性的确定性的nE Ek k-k-k阶阶ErlangErlang分布分布nGI-GI-一般相互独立的到达时间间隔分布一般相互独立的到达时间间隔分布nG-G-一般一般(General)General)时间分布时间分布排队系统的分类排队系统的分类 n扩展符号表示扩展符号表示:X/Y/Z/A

8、/B/CnA-系统容量系统容量nB-顾客源中顾客的数量顾客源中顾客的数量nC-服务规则服务规则:FCFS,LCFS,等等等等.n若省略后三项，即是指下面的情形：若省略后三项，即是指下面的情形：X/Y/Z/FCFS例：M/M/s/K表示？已知:顾客到达间隔时间分布,服务时间分布.求:n队长队长:Ls-系统中的顾客数系统中的顾客数.排队长排队长(队列长队列长):Lq-队列中的顾客数队列中的顾客数.Ls=Lq +正在接受服务的顾客数正在接受服务的顾客数n逗留时间逗留时间:W S-顾客在系统中的停留时间顾客在系统中的停留时间 等待时间等待时间:Wq-顾客在队列中的等待时间顾客在队列中的等待时间.WS=

9、Wq+服务时间服务时间n忙期忙期,损失率损失率,服务强度服务强度.排队问题的求解排队问题的求解二二.单服务台负指数分布单服务台负指数分布排队系统分析排队系统分析 1 1、M/M/1M/M/1模型模型2 2、M/M/1/N/M/M/1/N/模型模型(即系统的容量有限即系统的容量有限)3 3、M/M/1/m M/M/1/m 模型（即顾客源为有限）模型（即顾客源为有限）顾客源顾客源排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去1 1、M/M/1M/M/1模型模型无限无限输入过程服从输入过程服从参数为参数为 的的PoissonPoisson过程过程

10、单队单队队长无限队长无限先到先服务先到先服务服务时间服从服务时间服从参数为参数为 的的负指数分布负指数分布 M/M/1M/M/1排队模型排队模型是是指指1 1个个服务员的排队系统，服务员的排队系统，顾客到来间隔时间是独立同分布的；顾客到来间隔时间是独立同分布的；服务时间也是独立同分布的；服务时间也是独立同分布的；并且独立于输入过程；并且独立于输入过程；排队规则是等待制；排队规则是等待制；含假定：含假定：顾客到来间隔时间服从参数为顾客到来间隔时间服从参数为 的指数分布，的指数分布，服务时间服从参数为服务时间服从参数为 的负指数分布，且有隐的负指数分布，且有隐 按排队论的基本构成特征，来求解该排队

11、模型按排队论的基本构成特征，来求解该排队模型(1).基本构成基本构成(i)顾客到达规律顾客到达规律()(),0,1,2!kttP X tkekk 的主要数量指标：的主要数量指标：平均到达率平均到达率.表示在表示在 时间到达的时间到达的顾客数顾客数，称为排队系统的输入过程，称为排队系统的输入过程.()Xt(,)t tt 其平均值为其平均值为 ，即单位时间内到达的顾客数为，即单位时间内到达的顾客数为 ，并称为，并称为t它服从参数为它服从参数为 的泊松分布，即的泊松分布，即：t(ii)服务时间服务时间服务率服务率 .表示顾客到达间隔时间序列，其表示顾客到达间隔时间序列，其1|nnnnss 中中 表示

12、第表示第n个顾客的到来时刻个顾客的到来时刻.n 可以证明可以证明：服从参数服从参数 为的泊松分布的充为的泊松分布的充()X tt负指数分布负指数分布.要条件是到要条件是到达间隔时间序列达间隔时间序列 独立同分布且服从独立同分布且服从ns记记Z Z为服务时间，为服务时间，Z Z服从参数为服从参数为 的负指数分布的负指数分布：01()00tteP Ztt 则则 ，即为每个顾客平均服务时间为，即为每个顾客平均服务时间为 ，从，从1EZ 1 而单位时间内被服务的顾客的平均数为而单位时间内被服务的顾客的平均数为 ，称为平均，称为平均 (iii)排队规则排队规则按顾客的到达的先后顺序服务，即先到先服务按顾

13、客的到达的先后顺序服务，即先到先服务.满足满足以上三个条件的模型在排队论中记为模型以上三个条件的模型在排队论中记为模型 M/M/1模模型型，其中其中1 1为为服务员的个数服务员的个数.n关于 的几点说明：)1(/1/1(2)01(3)p顾客平均到达率顾客平均到达率顾客平均服务率顾客平均服务率一个顾客服务时间一个顾客服务时间一个顾客到达时间一个顾客到达时间服务强度服务强度,1)4(即顾客的顾客平均到达率即顾客的顾客平均到达率小于顾客平均服务率时，小于顾客平均服务率时，系统才能达到统计平稳。系统才能达到统计平稳。系统中至少有系统中至少有一个顾客的概一个顾客的概率；率；服务台处于忙服务台处于忙的状态

14、的概率；的状态的概率；反映系统繁忙反映系统繁忙程度程度 求解：求解：np:系统达到平稳后，系统有系统达到平稳后，系统有n n个顾客的概率。个顾客的概率。1n 0)(0n 01110nnnPPPPP平衡方程：平衡方程：1n )1(1 0nnPP1:令，且当，且当时时01102101.,.2,1,ppCnpCpnnnnnnnnn其中其中 计算有关指标计算有关指标101.)2(.)32()1(3232321n0nsnnsLnnPLn队长队长n队列长队列长 1)1()1(201n10nssnnnnqLPLPnPPnL 计算有关指标计算有关指标 n逗留时间逗留时间:可以证明可以证明,Ws服从参数为服从参

15、数为-的的负指数分布负指数分布.则则:n等待时间等待时间1 sW1 sqWW服务WWWsq 计算有关指标计算有关指标计算有关指标计算有关指标nLittle公式（相互关系）qsqsqqssLLWWWLWL 1 小小结结1 sWqW qLsL平均服务平均服务时间时间平均在忙的服务平均在忙的服务台数台数/正在接受正在接受服务的顾客数服务的顾客数有效到达率有效到达率n平均忙期平均忙期 B,忙期出现的概率忙期出现的概率 n平均闲期平均闲期 I,闲期出现的概率闲期出现的概率(1-)n忙期忙期 B:闲期闲期 I=:(1-)n平均闲期平均闲期 I=1/n平均忙期平均忙期 B=(/(1-)/=1/(-)计算有关

16、指标计算有关指标n忙期与闲期忙期与闲期 与逗留时间与逗留时间WsWs相同相同例：某医院手术室每小时就诊病人数和手术例：某医院手术室每小时就诊病人数和手术 时间的记录如下：时间的记录如下：到达的病人数到达的病人数 出现次数出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上以上 1 合计合计 100完成手术时间完成手术时间 出现次数出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合计合计 100n解：到达的病人数 出现次数 n un 0 10 1 28 2

17、 29 3 16 4 10 5 6 6 以上 1 合计 100每小时病人平均到达率每小时病人平均到达率1.2100nnu（人（人/小时）小时）每次手术平均时间每次手术平均时间4.0100rrv（小时（小时/人）人）每小时完成手术人数每小时完成手术人数（平均服务率）（平均服务率）5.24.01（人（人/小时）小时）?,n解：到达的病人数 出现次数 n un 0 10 1 28 2 29 3 16 4 10 5 6 6 以上 1 合计 100每小时病人平均到达率每小时病人平均到达率1.2100nnu（人（人/小时）小时）每次手术平均时间每次手术平均时间4.0100rrv（小时（小时/人）人）每小时

18、完成手术人数每小时完成手术人数（平均服务率）（平均服务率）5.24.01（人（人/小时）小时）完成手术时间完成手术时间 出现次数出现次数 r vr 0.00.2 38 0.20.4 25 0.40.6 17 0.60.8 9 0.81.0 6 1.01.2 5 1.2 以上以上 0 合计合计 1005.2,1.2解：5.2,1.21 sWqW 41.425.55.21.2sqLL25.51.25.21.2sL2 2 系统容量有限制的情形系统容量有限制的情形 (M/M/1/N/FCFSM/M/1/N/FCFS）n状态转移图n状态转移方程 Nn 1-Nn )(0n 11101NNnnnPPPPPP

19、PN-1N 1)1(20NP求排队系统顾客数的分布状况求排队系统顾客数的分布状况 n队长队长n队列长队列长 1101)1(1NNNnnsNnPL)1()1(00PLPnLsNnnq计算有关指标计算有关指标 n逗留时间逗留时间 n等待时间等待时间111Little1 100）（）（公式根据）（）或（有效到达率：NqsesseNePLPLLWPP1sqWW计算有关指标计算有关指标系统已满顾客不能系统已满顾客不能到达的概率到达的概率-损失损失率率/10eP）服务强度：（有有6个椅子接待人们排队，超过个椅子接待人们排队，超过6人人顾客就离开，平均到达率顾客就离开，平均到达率3人人/小时，理小时，理发需

20、时平均发需时平均15分钟。分钟。7为系统中的最大顾客数。为系统中的最大顾客数。举例：单人理发馆排队问题 n 顾客到达就能理发的概率顾客到达就能理发的概率 -相当于理发店内没有顾客相当于理发店内没有顾客n等待顾客数的期望值等待顾客数的期望值2778.0)4/3(14/3111810NP39.1)2778.01(11.2)1(11.2)4/3(1)4/3(84/314/31)1(108811PLLNLsqNNs n 求有效到达率求有效到达率 n顾客在理发馆内逗留的期望时间顾客在理发馆内逗留的期望时间8.4373.089.2/11.2/essLW小时小时分钟分钟89.2)2778.01(41 10e

21、eNePP）（）或（人人/小时小时 n可能的顾客中有百分之几不等待就离开可能的顾客中有百分之几不等待就离开 -求系统中有求系统中有7 7个顾客的概率个顾客的概率%7.3)4/3(14/31)43()/(1/1)(87877P 设：设：m：为顾客总体数，为顾客总体数，：每个顾客的到达率，每个顾客的到达率，m-Ls ：系统外顾客的平均数，：系统外顾客的平均数，e=（m-Ls）：）：为系统有效到达率。为系统有效到达率。3 3 顾客源有限制的情形顾客源有限制的情形 (M/M/1/m/FCFSM/M/1/m/FCFS）含义与上节不同含义与上节不同对顾客而言，对顾客而言，而不是对系统而不是对系统m对系统而

22、言对系统而言,有有一个顾客到达一个顾客到达的概率的概率状状态态转转移移图图01mn-1n(m-n+1)(m-n)n+1.m-1m.(m-1)2状态转移方程状态转移方程 mn 1-mn )()1(0n 11101mmnnnPPPnmPnmPPmP11mnnPF注意到注意到 ，求解状态转移方程得求解状态转移方程得m1,2,.,n )()!(!)()!(!1010PnmmPimmPnnimi有效到达率有效到达率)(seLm）（01 Pe求解顾客数概率分布求解顾客数概率分布 n等待时间等待时间n正常运转的平均设备台数正常运转的平均设备台数1sqWW)1(0PLms计算有关指标计算有关指标 n队长队长n

23、队列长队列长n逗留时间逗留时间)1(0PmLs)1(0PLLsq1)1(0PmWs计算有关指标计算有关指标三三.多服务台负指数分布多服务台负指数分布排队系统分析排队系统分析规规定：定：n各服务台工作是相互独立的，且平均服务率相各服务台工作是相互独立的，且平均服务率相同，均为同，均为 。n整个服务机构的平均服务率为：整个服务机构的平均服务率为：c c (当当n n c)c)，n n (当当n c);n c);n记记 =/,s s=/c c =/c/c 为服务系统的平均利用率为服务系统的平均利用率 当当 /c c 1 1时，不会排成无限队列。时，不会排成无限队列。1 2 c.系统人数系统人数n n

24、人人 1 2 c.系统人数系统人数n n人人n=c 1 2 c.系统人数系统人数n n人人 状状态态转转移移图图01n-1nn(n+1)n+1.22n-1nccn+1.n=c n状态转移方程状态转移方程 n )(cn 1 )()1(0n 111101cPcPPcPnPPnPPnnnnnn解差分方程，求得状态概率为解差分方程，求得状态概率为 )(!1)(!1)(11!1)(!1001100cnPcccnPnPckPncnnnckck n顾客等候的概率顾客等候的概率 )(!1)(!1010cnPcccnPnPnnnn0)1(!)(PcPcnPsccnn n平均正接受服务的顾客数平均正接受服务的顾客

25、数=正忙的服务台数正忙的服务台数cnncnnPcnPc10qsLL解释解释?)(!1)(!1010cnPcccnPnPnnnn n队长队长n队列长队列长n逗留时间及等待时间逗留时间及等待时间qqsLLL021)1(!)()(PcPcnLssccnnqssqqLWLW ;唯一唯一 某售票所有三某售票所有三个窗口，顾客到达个窗口，顾客到达服从服从Poisson过程，过程，到达到达 =0.9 人人/分钟，服务分钟，服务 =0.4人人/分钟。设分钟。设顾客到达后依次排顾客到达后依次排成一队向空闲的窗成一队向空闲的窗口购票，如图口购票，如图 a.图图 a 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口

26、窗口3 =0.4 =0.9图图 a 窗口窗口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.9n属于M/M/c型系统 c=3,=/=2.25,s=/c=2.25/3 1,符合要求.整个售票所空闲概率整个售票所空闲概率平均队长平均队长95.370.10748.0)4/1(!34/3)25.2(23qsqLLL0748.03/25.211!325.2!25.212030nnnp )(!1)(!1)(11!1)(!1001100cnPcccnPnPckPncnnnckck

27、平均等待时间和逗留时间平均等待时间和逗留时间分钟分钟39.44.0/189.1/189.19.0/70.1qsqqWWLW57.00748.04/1!3)25.2()3(3nP顾客到达后必须等待概率顾客到达后必须等待概率 以上例说明以上例说明,设顾设顾客到达后在每个窗口前客到达后在每个窗口前各排一队各排一队(其它条件不其它条件不变变),),共三队共三队,每队平均每队平均到达率为到达率为:3.03/9.0321 窗口窗口1 =0.4 窗口窗口2 =0.4 窗口窗口3 =0.4 =0.3 =0.3 =0.3 =0.9图图 b结果比较结果比较n状态图是多服务台和容量有限的综合状态图是多服务台和容量有

28、限的综合n平衡方程平衡方程你会你会吗吗?Nncccnnnnnn 0 N 01N,0,1,2,1 )1(!1 )1(!)1(!0 !1101101000ccncnccnccNccncnnnncNcncnpNncpcccnpnpn求系统有求系统有n位顾客的概率分布位顾客的概率分布 )(!1)(!1)(11!1)(!1001100cnPcccnPnPckPncnnnckckn求系统的指标求系统的指标)1(Nep有效到达率有效到达率)1(10NNcnncnnppcnpc平均被占用的服务台平均被占用的服务台cnncnnPcnPc10n求系统的指标求系统的指标1 ,)(seqqessqsNcnnqWLWL

29、WcLLpcnLssqqLWLW ;021)1(!)()(PcPcnLssccnnq 每逢每逢“五一五一”“”“十一十一”节假日，人节假日，人们就免不了与排队不期而遇：高速公路们就免不了与排队不期而遇：高速公路上汽车排队，景区买门票排队，饭馆吃上汽车排队，景区买门票排队，饭馆吃饭排队，就连上厕所也要排队饭排队，就连上厕所也要排队 微观经济学理论认为，资源稀缺导致我们不得不排队，也就是微观经济学理论认为，资源稀缺导致我们不得不排队，也就是说，人们都是因为供不应求的商品而排队。排队现象虽然看起来效说，人们都是因为供不应求的商品而排队。排队现象虽然看起来效率不高，但为了保证公平，排队也是最合理的方法

30、率不高，但为了保证公平，排队也是最合理的方法如果有人插队，如果有人插队，就会损害了他人利益（增加他人时间成本）。就会损害了他人利益（增加他人时间成本）。“囚徒困境囚徒困境”理论：理论：经济学里有一个经济学里有一个“囚徒困境囚徒困境”理论，理论，这个理论映射了部分不排队者的心这个理论映射了部分不排队者的心理，就是不相信他人会排队，生怕理，就是不相信他人会排队，生怕自己老老实实排队吃了亏。于是，自己老老实实排队吃了亏。于是，只要有一个人乱插队，就会引起整只要有一个人乱插队，就会引起整个队伍秩序的混乱，导致资源配置个队伍秩序的混乱，导致资源配置的效率降低，而插队者自身利益最的效率降低，而插队者自身利

31、益最终也可能受到损害。终也可能受到损害。在中国，也有一些经济学者一直关在中国，也有一些经济学者一直关注春运之类的排队现象，某专家认为，注春运之类的排队现象，某专家认为，中国的春运综合征的核心，不是车票短中国的春运综合征的核心，不是车票短缺，因为能满足人们需要的商品总是不缺，因为能满足人们需要的商品总是不够的，总是多多益善的，春运火车票一够的，总是多多益善的，春运火车票一票难求是因为票难求是因为价！格！价！格！过！低！过！低！。问题来了问题来了：公平合理的排队，是冲着稀缺资源去的；而价格提高，公平合理的排队，是冲着稀缺资源去的；而价格提高，就可以让稀缺资源在不增加数量的前提下变为不稀缺。就可以让

32、稀缺资源在不增加数量的前提下变为不稀缺。姓名：薛兆丰姓名：薛兆丰生日：生日：1968年年 职业：经济学者职业：经济学者简介：薛兆丰，经济学者，美国西北大简介：薛兆丰，经济学者，美国西北大学法学院（学法学院（Northwestern University School of Law）博士后研究员，北京）博士后研究员，北京大学大学“法律经济学研究中心法律经济学研究中心”研究员，研究员，美国乔治美国乔治梅森大学（梅森大学（George Mason University）经济学博士。）经济学博士。相关事迹：曾经为春运一票难求问题提相关事迹：曾经为春运一票难求问题提出宝贵意见，并收到网友们关切问候。出宝

33、贵意见，并收到网友们关切问候。以上不过是理论上的推理。饭馆排队，店家可以用提高菜价赶走一部分客人；以上不过是理论上的推理。饭馆排队，店家可以用提高菜价赶走一部分客人；可是，厕所排队，难道要提高如厕费用，让一部分不能承受高价的人随地大小便可是，厕所排队，难道要提高如厕费用，让一部分不能承受高价的人随地大小便吗？所以，提价恐怕不总是灵丹妙药。吗？所以，提价恐怕不总是灵丹妙药。排队从某种角度看，是资源配置供需不平衡的结果。而要满足资源排队从某种角度看，是资源配置供需不平衡的结果。而要满足资源配置的最优化需求，需要大量的资金投入，需要大量的基础设施配套跟配置的最优化需求，需要大量的资金投入，需要大量的

34、基础设施配套跟进，但这种投入这种跟进，有一个过程，需要循序渐进，不可能一蹴而进，但这种投入这种跟进，有一个过程，需要循序渐进，不可能一蹴而就。而在一时尚无法解决供需矛盾的情况下，排队却是解决供求矛盾的就。而在一时尚无法解决供需矛盾的情况下，排队却是解决供求矛盾的一个相对公平的方式，因为它遵循了一个相对公平的方式，因为它遵循了“先来后到先来后到”的时间优先原则，给的时间优先原则，给排队的人一个预期：只要按照顺序排着，总能轮到自己。排队的人一个预期：只要按照顺序排着，总能轮到自己。BUTBUT排队的不公平性：排队的不公平性：特权特权黄牛黄牛n系统设计最优化：系统设计最优化：(静态优化问题静态优化问

35、题)设备达到最大效益设备达到最大效益n系统控制最优化：系统控制最优化：(动态优化问题动态优化问题)如何运营使某个目如何运营使某个目标函数最优。标函数最优。服务水平服务水平总费用总费用等待费用等待费用服务费用服务费用费费用用极小点极小点84 五五.应应 用用 综综 述述85排排 队队 论论 的的 应应 用用 综综 述述1.1.2.2.3.3.4.4.排队论在通信领域的应用排队论在通信领域的应用排队论在分配问题中的应用排队论在分配问题中的应用排队论在医疗领域的应用排队论在医疗领域的应用 排队论在交通领域的应用排队论在交通领域的应用 5 5 排队论在银行领域的应用排队论在银行领域的应用86排队论的一

36、般模型排队论的一般模型87一一.排队论在通信领域的应用排队论在通信领域的应用排队论在通信领域中应用的发展排队论在通信领域中应用的发展 2020世纪初期世纪初期 主要研究应用于电话网和远程通信系统等无队列的排队系统主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制损失制)2020世纪中期世纪中期 主要研究通信系统中有队列主要研究通信系统中有队列(等待制等待制)的排队系统和排队网络的排队系统和排队网络 从从2020世纪世纪6060年代至今年代至今主要是研究大规模复杂排队系统的理论分析、数值分析和近似分析，主要是研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带

37、有各种网络控制的排队系统的研究。尤其注重对业务突发性和带有各种网络控制的排队系统的研究。88排队论在通信领域的应用排队论在通信领域的应用经典排队理论经典排队理论 (1)(1)相继到达顾客的到达时间的间隔与服务时间都相互独立；相继到达顾客的到达时间的间隔与服务时间都相互独立；(2)(2)由于到达和服务的无后效性的特点，一般可以用生灭过程来描述。由于到达和服务的无后效性的特点，一般可以用生灭过程来描述。近百年以来，经典排队理论在通信领域的主要成果大致可总结如下近百年以来，经典排队理论在通信领域的主要成果大致可总结如下:(1)(1)得到了单服务台排队模型得到了单服务台排队模型(M/M/1)(M/M/

38、1)在到达间隔和服务时间相互独立条在到达间隔和服务时间相互独立条件下的稳态解；件下的稳态解；89(2)(2)对于多服务台排队系统对于多服务台排队系统(M/M/s)(M/M/s)，得到了在服务时间满足指数，得到了在服务时间满足指数分布的稳态解；分布的稳态解；排队论在通信领域的应用排队论在通信领域的应用90(3)3)优先排队模型也得到了比较明确的结果，尤其在输入流满足优先排队模型也得到了比较明确的结果，尤其在输入流满足泊松分布以及优先级固定的情况下的排队泊松分布以及优先级固定的情况下的排队排队论在通信领域的应用排队论在通信领域的应用91排队论在通信领域的应用排队论在通信领域的应用现代现代通信技术中

39、的排队论理论：通信技术中的排队论理论：现代通信的发展趋势是业务综合，在同一个网络中实现多种业务的传现代通信的发展趋势是业务综合，在同一个网络中实现多种业务的传输。因此输入将是复合业务流，比较复杂，一般不再具有泊松过程无后输。因此输入将是复合业务流，比较复杂，一般不再具有泊松过程无后效性的特点；效性的特点；服务过程与排队策略也变得比较复杂。服务过程与排队策略也变得比较复杂。显然，经典的排队理论并不能把问题解决显然，经典的排队理论并不能把问题解决 现代现代通信研究中常用通信研究中常用的排队分析方法：的排队分析方法：扩大状态空间法扩大状态空间法1 1 NeutesNeutes矩阵几何分析法矩阵几何分

40、析法4 4半马氏分析法半马氏分析法2 2流体流方法流体流方法3 35 5 大偏差理论方法大偏差理论方法92扩大状态空间法扩大状态空间法 将非马尔可夫过程的排队化成一个状态空间为多维的马尔可夫过程将非马尔可夫过程的排队化成一个状态空间为多维的马尔可夫过程求解求解半马氏分析方法半马氏分析方法 对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可夫性质，只是在某些特殊的随机时刻系统具有这种性质，我们马尔可夫性质，只是在某些特殊的随机时刻系统具有这种性质，我们称这种随机时刻点为再生点，即从这个时刻起，系统好像又重新开始称这种随机时刻

41、点为再生点，即从这个时刻起，系统好像又重新开始一样。一样。利用再生点，一般服务或一般到达的排队系统可化为马尔可夫链，利用再生点，一般服务或一般到达的排队系统可化为马尔可夫链，用马尔可夫链的方法予以解决用马尔可夫链的方法予以解决 排队论在通信领域的应用排队论在通信领域的应用93流体流方法流体流方法 流体流方法流体流方法(Fluid Flow M(Fluid Flow M ethodethod)是一种排队近似分析法。是一种排队近似分析法。它忽略到达过程及排队队长的离散性质它忽略到达过程及排队队长的离散性质,将到达及队长变化看将到达及队长变化看成连续变化。成连续变化。计算简单、物理意义明确计算简单、

42、物理意义明确,流体流方法的计算复杂度与排队容量流体流方法的计算复杂度与排队容量大小无关大小无关矩阵几何分析方法矩阵几何分析方法随机模型有指数分布为可信发展到广泛应用相位型分布随机模型有指数分布为可信发展到广泛应用相位型分布大偏差理论方法大偏差理论方法 一种近似分析方法一种近似分析方法 没有没有Markov Markov 假设假设排队论在通信领域的应用排队论在通信领域的应用总结：现代通信技术中的排队论分析方总结：现代通信技术中的排队论分析方法是多种多样的，因此，针对不同的实法是多种多样的，因此，针对不同的实际情况，需要选择合适的方法，是得到际情况，需要选择合适的方法，是得到最高的效率及最好的准确

43、率。最高的效率及最好的准确率。94NO.2 NO.2 排队论在分配问题中的应用排队论在分配问题中的应用95分分 配配 问问 题题 对资源的合理利用对资源的合理利用 多目标的合理处理多目标的合理处理 解决的问题：减少资源浪费，防止拥塞，对目标的即时解决的问题：减少资源浪费，防止拥塞，对目标的即时处理，提高系统工作速度效率等等处理，提高系统工作速度效率等等96发发 展展 历历 程程 199019901995 1995 工程上的应用、医疗上的应用、图书馆信息处理，军事上的应用；工程上的应用、医疗上的应用、图书馆信息处理，军事上的应用；199519952000 2000 码头与船舶的分配，工程土方的创

44、新，停车场面积的计算；码头与船舶的分配，工程土方的创新，停车场面积的计算；200020002005 2005 智能地雷反坦克研究，灭火兵力部署；智能地雷反坦克研究，灭火兵力部署；200520052010 2010 新的前沿应用，公测建筑面积的分配，图书馆服务，信息技术中新的前沿应用，公测建筑面积的分配，图书馆服务，信息技术中的应用。的应用。97排队论在公厕面积设计上的应用排队论在公厕面积设计上的应用 由于各方面的原因，男女厕相同面积的设计存在着一定的不合理性；由于各方面的原因，男女厕相同面积的设计存在着一定的不合理性；地点、场合的不同影响公厕的使用效率，需要综合分析得到合适的建地点、场合的不同

45、影响公厕的使用效率，需要综合分析得到合适的建筑面积分配；筑面积分配；将人们入厕这一过程，看成一个随机服务系统的服务过程。每个入厕将人们入厕这一过程，看成一个随机服务系统的服务过程。每个入厕的人是一个顾客，厕所坑位则为服务台；的人是一个顾客，厕所坑位则为服务台；收集某一公厕一定时间内到达人次及使用时间数据，建立模型求解最收集某一公厕一定时间内到达人次及使用时间数据，建立模型求解最佳等待时间以取得最佳服务满意度佳等待时间以取得最佳服务满意度；评估公厕面积分配是否合理，应如何评估公厕面积分配是否合理，应如何改进改进。98排队论解决分配问题的未来展望排队论解决分配问题的未来展望 宇航相关问题宇航相关问

46、题 军事相关问题军事相关问题 医院相关问题医院相关问题 计算机相关问题计算机相关问题 民用设施相关问题民用设施相关问题99NO.3 NO.3 排队论在医疗领域的应用排队论在医疗领域的应用100 医院中存在着各种有形无形的排队现象医院中存在着各种有形无形的排队现象(如：就诊、挂号、如：就诊、挂号、取药、划价，病床医生等资源的调度，等等取药、划价，病床医生等资源的调度，等等)，如何使医院工作既能满足患者的需要如何使医院工作既能满足患者的需要,又能让医疗资源又能让医疗资源得到充分利用，这部分主要说明使用排队理论分析了不同类型得到充分利用，这部分主要说明使用排队理论分析了不同类型医疗过程，并以此优化医

47、疗过程。医疗过程，并以此优化医疗过程。排队论在医疗领域的应用排队论在医疗领域的应用101排队叫号流程排队叫号流程挂号挂号患者拿到小票患者拿到小票患者在等候区等待患者在等候区等待医生根据医生根据HISHIS系统直接叫号系统直接叫号语音文字多屏同步叫号语音文字多屏同步叫号患者到诊室就诊患者到诊室就诊请：请：*到二诊室等候到二诊室等候生殖中心生殖中心叫号已至叫号已至一诊室一诊室 6 6二诊室二诊室 8 8三诊室三诊室 5 5102 近年来旨在提高医疗体系的服务效率，提高资源利用率，提高病人满近年来旨在提高医疗体系的服务效率，提高资源利用率，提高病人满意度以及缓解患者于医院之间的矛盾；提出了一些具体的

48、优化标准如下：意度以及缓解患者于医院之间的矛盾；提出了一些具体的优化标准如下：以费用作为优化指标计算最优目标值条件下最优的服以费用作为优化指标计算最优目标值条件下最优的服 务水平：总费用务水平：总费用=排队损失费排队损失费+服务费；服务费；“优先权选择或等级优先权选择或等级”来优化医院服务；来优化医院服务；构造合理的调度方式来进行优化；构造合理的调度方式来进行优化；建立了建立了“预留病床模型，逐步优先权就诊模式预留病床模型，逐步优先权就诊模式”。排队论在医疗领域的应用排队论在医疗领域的应用103排队论在医疗领域的应用排队论在医疗领域的应用总结及预测总结及预测 一系列的研究发现，相对于经验的管理

49、方法，一系列的研究发现，相对于经验的管理方法，排队理论排队理论 能较为科学，量能较为科学，量化地分析医院的排队系统，并提出化地分析医院的排队系统，并提出合理合理 的整改意见，适应了新经济时代的的整改意见，适应了新经济时代的个性化就诊趋势。个性化就诊趋势。运用排队论方法，通过对医院排队系统的研究，科学运用排队论方法，通过对医院排队系统的研究，科学、量化、准确地描量化、准确地描述排队系统的规律性，同时对诊室和述排队系统的规律性，同时对诊室和医医 生的安排进行最优化和最优运营提生的安排进行最优化和最优运营提出科学有效的整改出科学有效的整改意意 见，为医护工作的安排提供量化、科学的依据，以见，为医护工

50、作的安排提供量化、科学的依据，以增增加加 预见性，减少盲目性从而最大限度得满足患者和预见性，减少盲目性从而最大限度得满足患者和家属家属 的要求，同时采的要求，同时采用排队论的理论与方法评价门诊服务用排队论的理论与方法评价门诊服务流程流程效率合理性和可行性，值得推广。效率合理性和可行性，值得推广。最终目的实现双赢！最终目的实现双赢！104人民医院排队叫号系统人民医院排队叫号系统网网 络络 架架 构构105 人民医院排队叫号系统是在现有医院信息系统（人民医院排队叫号系统是在现有医院信息系统（HISHIS）的基）的基础上，利用等离子或者液晶电视设备作为系统的显示终端，集础上，利用等离子或者液晶电视设