排队论(Queueing-Theory)

排队论（QueueingTheory）排队论课件2基本模型M/M/1模型M/M/c模型其他模型结束语♂※排队论课件3基本的排队模型基本组成概念与记号指数分布和生灭过程♂排队论课件4基本组成输入来源队列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.•输入过程(顾客按照怎样的规律到达);•排队规则(顾客按照一定规则排队等待服务);•服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)♂排队论课件5基本排队模型－输入过程顾客来源有限/无限顾客数量有限无限经常性的顾客来源.顾客到达间隔时间:到下一个顾客到达的时间.服从某一概率分布.(指数分布)顾客的行为假定为:在未服务之前不会离开;当看到队列很长的时候离开；从一个队列移到另一个队列。♂排队论课件6基本排队模型－队列/排队规则队列队列容量有限/无限排队规则先来先服务（FCFS）；后来先服务；随机服务；有优先权的服务；♂排队论课件7基本排队模型－服务规则服务机构服务设施，服务渠道与服务台服务台数量服务时间分布:指数,常数,k级Erlang♂排队论课件8基本排队模型－记号方案ServerQueueArrival顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall记号)M/M/1///FCFSM/M/1/M:指数分布(Markovian)D:定长分布(常数时间)Ek:k级Erlang分布G:普通的概率分布(任意概率分布)排队论课件9基本排队模型－记号系统状态=排队系统顾客的数量。N(t)=在时间t排队系统中顾客的数量。队列长度=等待服务的顾客的数量。Pn(t)=在时间t,排队系统中恰好有n个顾客的概率。s=服务台的数目。排队论课件10基本排队模型－统计平稳条件下的记号n=系统有n个顾客时的平均到达率（单位时间平均到达的顾客人数即是平均到达率）n=系统有n个顾客时的平均到达率=对任何n都是常数的平均到达率.=对任何n都是常数的平均到达率.1/=期望到达间隔时间1/=期望服务时间=服务强度，或称使用因子,/(s)排队论课件11统计平稳条件下的记号LqLqWW平均队长平均等待队长平均等待时间平均逗留时间排队论课件12L,W,Lq,WqLittle’sformulaWLqqWL1qWW♂排队论课件13指数分布密度函数0fort00)(tforetftT均值1)(TE方差21)(TVar随机变量T分布函数tetTP1)(fT(t)t1)(TE排队论课件14指数分布性质1)()0(ttTtPtTPfT(t)tttfT(t)是一个严格下降函数排队论课件15指数分布性质2)()/(tTPtTttTP无后效性)()()()()()/()()(tTPeeeeeetTPttTPtTPtTandttTPtTttTPttttttt不管多长时间(t)已经过去，逗留时间的概率分布与下一个事件的相同.排队论课件16指数分布性质3tnnetUPTTTMinU)...(2121)(),...,,.(几个独立的指数分布的随机变量的最小有一个指数分布几个独立的指数分布的随机变量的和还是一个指数分数的随机变量T1(1)T1(2)T1(3)T(1+2+3)排队论课件17指数分布性质4指数分布0fort00)(tforetftT1)(TE!)())((netntXPtnPoisson分布ttXE))((服务时间的概率=t在t时间内已经服务n个顾客的概率1/:平均服务时间平均服务率=排队论课件18指数分布性质5tsmallforttTttTP)/()/(0ttTttTPpreciselyMoreLimt♂排队论课件19M/M/1//或M/M/1模型一个基本地排列模型.一个服务台,到达率和服务率都服从指数分布。2,111,(1)(1)(1)qqnnLLWWP排队论课件20M/M/1举例M/M/squeuingcomputationsArrivalrate5Servicerate6Numberofservers1Utilization83.33%P(0),probabilitythatthesystemisempty0.1667Lq,expectedqueuelength4.1667L,expectednumberinsystem5.0000Wq,expectedtimeinqueue0.8333W,expectedtotaltimeinsystem1.000000.050.10.150.20246810121416182022242628303234363840NUMBERINSYSTEMProbability排队论课件21M/M/1/N/单一服务台，固定长度固定长度排队意味着若到了最大系统容量顾客将不能进入系统.111001,,211(1)(1),,1(1)(1)(1),11,(1)NNnnNNqqNNNPLaNaNaaaaaaLLPPL排队论课件22M/M/1/N/举例M/M/swithFiniteQueueArrivalrate5Servicerate6Numberofservers1Maximumqueuelength4Utilization74.94%P(0),probabilitythatthesystemisempty0.2506Lq,expectedqueuelength1.2294L,expectednumberinsystem1.9788Wq,expectedtimeinqueue0.2734W,expectedtotaltimeinsystem0.4401Probabilitythatacustomerwaits0.7494Probabilitythatacustomerbalks0.100700.050.10.150.20.250.30246810121416182022242628303234363840NUMBERINSYSTEMProbability♂排队论课件23增加更多服务台M/M/c所有服务台是空的概率P0,和所有服务台都在忙的概率P,需要下面比较复杂的公式。11000()(),!!(1)()!(1),111,nccncqqccPcnccPPcPPLLcL排队论课件24M/M/c举例M/M/squeuingcomputationsArrivalrate10Servicerate6Numberofservers2Utilization83.33%P(0),probabilitythatthesystemisempty0.0909Lq,expectedqueuelength3.7879L,expectednumberinsystem5.4545Wq,expectedtimeinqueue0.3788W,expectedtotaltimeinsystem0.545500.020.040.060.080.10.120.140.160246810121416182022242628303234363840NUMBERINSYSTEMProbability♂排队论课件25其他模型M/M/c/K/K顾客来源是有限的服务系统.例如：一个饭店有X张桌子和Y个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及指数分布服务时间.例如：医生赴约治病的时间表.M/Ek/1服务服从Erlang分布.例如：用相同平均时间去完成一些程序。♂排队论课件26结束语排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。排队论应用十分广泛。