1、排队论课件1现实生活中的实例:进餐馆就餐到图书馆借书去售票处购票在车站等车等等排队论课件2一、排队系统的特征及排队论: 顾客为了得到某中服务而到达系统,若不能获得服务而允许排队等待,则加入等待队伍,待获得服务后离开系统。排队论课件3排队的形式:顾客到达队列 服务台服务完成后离去 服务台1 服务台2 服务台s顾客到达队列服务完成后离去顾客到达队列1队列2队列s 服务台1 服务台2 服务台s服务完成后离去服务完成后离去服务完成后离去排队论课件4随机服务系统:输入来源队 列服务机构排队系统排队系统顾客服务完离开排队论课件5二、排对系统的描述系统由三个部分组成:输入过程排队和排队规则服务机制排队论课件
2、61、输入过程(1)顾客总数量:有限或者无限(2)到达方式:单个到达或成批到达(3)到达方式: 顾客相继到达时间间隔的分布,这是刻画输入过程的最主要内容。 令, 00TnT01,nTTTLL表示第n个顾客到达的时刻,则有:记), 2 , 1(1nTTXnnn假设:nX是独立同分布的,并记其分布函数为),(tA关于的分布,nX排队论中经常用到以下几种:排队论课件7 定长分布(D): 顾客相继到达时间间隔为确定的常数,如产品通过传输带进入包装箱 最简流(或称poisson分布)(M):顾客相继到达时间间隔nX000)(ttetat为独立, 同负指数分布,其密度函数为:排队论课件82、排队及排队规则
3、(1)排队分为有限和无限排队损失制排队系统: 排队空间为零的系统混合制排队系统: 等待制和损失制的结合,是指允许排队,但是不允许队列无限长下去,具体的又分三种情况:()队长有限,即等待空间有限()等待时间有限,即顾客在系统中等待时间不超过某一给定的长度T()逗留时间(等待时间和服务时间之和)(系统只能容纳K个顾客)排队论课件9不难注意到损失制和等待制可以看成是混合制的特殊情况如记ssK 为系统中服务台的个数, 当时,混合制即为损失制当K时,即成为等待制。(2)排队规则:先来先服务(FCFS)排队论课件103、服务机制主要包括:服务员的数量及其连接形式(串联或并联);顾客是单个还是成批接受服务的
4、;服务时间的分布。记某服务台的服务时间为V, 其分布函数为B(t), 密度函数为b(t), 则常见的分布有: 定长分布(D):每位顾客接受的服务的时间是常数; 负指数分布(M): 每位顾客接受服务时间相互独立,具有相同的负指数分布:排队论课件11000)(ttetbt0: )(kE其中为一常数。k阶爱尔朗分布密度函数为tkkektkktb)!1()()(1排队论课件12三、排队系统的符号表示为了方便对众多的模型的描述,D.G.Kendall提出了一种目前在排队论中被广泛的使用的“Kendall记号”,一般形式为:X/Y/Z/A/B/C其中X表示顾客相继到达时间间隔的分布,Y表示服务时间分布,
5、Z表示服务台的个数; A表示系统的容纳,即可容纳最多顾客数B表示顾客源的数目;C表示服务规则;排队论课件13FCFSMM/1/表示了一个顾客的到达时间间隔服从相同的负指数分布,服务时间为负指数分布、单个服务台、系统容量为无限、顾客量无限、 排队规则为先来先服务的排队模型。排队论课件14四、排队系统的主要数量指标和记号1、队长和排队长2、等待时间和逗留时间3、忙期和闲期排队论课件15下面给出上述一些主要数量指标的常用记法:)(tTq时刻 t 系统中的顾客数,即队长)(tN)(tNq时刻 t 系统中排队的顾客数,即排队长)(tT时刻 t 到达系统的顾客在系统中的逗留时间时刻 t 到达系统的顾客在系
6、统中的等待时间上述数量指标与时间有关的随机变量,求它们的瞬时分布非常困难。排队论课件16讨论系统处于平衡状态下的性质:记)(tpn,npT为时刻t时系统处于状态n概率,即系统的瞬时分布根据前面的约定,我们将主要分析系统的平衡分布,即当系统到达统计平衡时时所处状态 n 概率,记为又记:系统处于平衡状态时队长,其均值为L,称为平均队长,WNqN系统处于平衡状态时排队长,其均值为,qL称为平均排队长;系统处于平衡状态时顾客的逗留时间, 均值为称为逗留时间;排队论课件17n,qWsn系统处于平衡状态时顾客的等待时间, 其均值记为称为平均等待时间;;qTn当系统处于状态n时,新来顾客的平均到达率,(单位
7、时间内来到系统的平均顾客数)当系统处于状态n时,整个系统的平均服务率(单位时间内完成的顾客数)当n为常数时, 记为当每个服务台的平均服务率为常数时,记为当sn 时,有:排队论课件181/ 期望到达间隔时间1/ 期望服务时间 服务强度, 或称使用因子, /(s)五、排队论原理0S01S1kS1knS1nSrnSk1rn1rnn1n1nrnrn2n1nkn1k12排队论课件19为了使系统中各个状态保持平衡,得到下列方程: 对状态0S对状态0101PP1100PP:1S2211PP021102PP对状态:1nSnnnnPP11021110PPnnn0PCPnn,21110nnnC记则平稳状态分布:排
8、队论课件20则概率分布的要求:10nnP1101PCnn有:于是:0011nnCP排队论课件21六、M/M/S等待制排队模型), 2 , 1(nnNPpn/1/MM, 2 , 1 , 0,nn1、单服务台模型队长的分布记为系统到达平衡状态后队长N的概率分布,注意到, 1, 2 , 1,nn,记并设则:, 2 , 1nCnn, 2 , 10nppnn排队论课件221111010nnnnp因此:, 1 , 0)1 (npnn其中:排队论课件23几个主要数量指标平均队长:1)1 (00nnnnnnpL平均排队长:)(1)1 () 1(2201LpLpnLnnq排队论课件241)(TEW0)(tetT
9、Pt的负指数分布,关于顾客在系统中的逗留时间T,说明服从参数因此,平均逗留时间W为:顾客在系统中逗留时间为等待时间和接受服务时间之和:VTTq排队论课件25其中V为服务时间,故由:1)()()(qqWVETETEWqW)(1WWq可得平均等待时间为:平均队长与平均逗留时间具有的关系:平均排队长与平均等待时间的关系:qqWLWL称为little公式排队论课件262、多服务台模型记), 2 , 1(nnNPpn, 2 , 1 , 0,nnsnssnnn, 2 , 1为系统到达平衡状态后队长N的概率分布, 注意到对个数s个服务台系统,有:记sss并设, 1s则:snsssssnnCsnnsnsnn!
10、, 2 , 1!/sMM排队论课件270ppnn其中:1100)1 ( !snssnsnp排队论课件28几个主要数量指标平均排队长:201)1 ( !)(ssssnnqsppsnLqLLWL平均队长:Little公式:qqWL排队论课件29其他模型nM/M/c/K/Kn顾客来源是有限的服务系统. 例如: 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客.nM/D/1n服务时间不变的服务系统.nD/M/1n确定性到达模式, 及指数分布服务时间. 例如:医生赴约治病的时间表.nM/E k/1n服务服从 Erlang 分布. 例如:用相同平均时间去完成一些程序。排队论课件30结束语n排队论是专门研究带有随机因素,产生拥挤现象的优化理论。也称为随机服务系统。n排队论应用十分广泛。