1、排队论的基本知识1.11.1 排队排队模型模型1.2 1.2 排队系统的组成和特征排队系统的组成和特征运筹学排队论排队论研究的内容排队论研究的内容性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.顾客源顾客源一、排队模型排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离去后离去排队系统的的一般表示排队系统的的一般表示服务服务机构机构服务服务台台(a)a)一个一个队列、单服务队列、单服务台台(阶段阶段)服务台服务台1服务台服务台2服务服务机构机构(b)b)一个一个队列、队列、s s个服
2、务阶段个服务阶段服务台服务台1服务台服务台2服务服务机构机构(c c)一个一个队列、队列、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个个队列队列运筹学 F1.输入过程输入过程顾客总体顾客总体:有限有限,无限无限.顾客到达方式顾客到达方式:单个单个,成批成批.顾客
3、到达间隔时间顾客到达间隔时间:确定的、确定的、随机的随机的.顾客到达的独立性顾客到达的独立性:独立独立,不独立不独立.输入过程的平稳性输入过程的平稳性:与时间无关与时间无关(平稳的平稳的),与时间有关与时间有关(非平稳的非平稳的).二、二、排队系统的组成和特征排队系统的组成和特征运筹学顾客到达时间间隔的分布顾客到达时间间隔的分布::第:第n n个顾客到达的时刻;个顾客到达的时刻;设设:第:第n n个顾客与第个顾客与第n-1n-1个顾客到达的时间间隔;个顾客到达的时间间隔;令令运筹学顾客到达时间间隔的分布顾客到达时间间隔的分布:假定假定 是独立同分布,分布函数为是独立同分布,分布函数为 ,排队论
4、中常用的有两种:排队论中常用的有两种:(2 2)最简流(即)最简流(即PoissonPoisson流)(流)(M M):):顾客到达时间间隔顾客到达时间间隔 为独立的,为独立的,服从负指数分布,其密度函数为服从负指数分布,其密度函数为(1 1)定长分布()定长分布(D D):):顾客到达时间间隔为确定的。顾客到达时间间隔为确定的。因为负指数分布因为负指数分布具有无后效性具有无后效性(即(即Markov性)性)运筹学 F2.排队及排队规则排队及排队规则即时制即时制(损失制损失制)等待制等待制先到先服务先到先服务:FCFS后到先服务后到先服务:LCFS随机服务随机服务优先权服务:优先权服务:PS队
5、容量队容量:有限有限,无限无限;有形有形,无形无形.队列数目队列数目:单列单列,多列多列.运筹学 F3.服务机构服务机构服务员数量服务员数量:无无,单个单个,多个多个.队列与服务台的组合队列与服务台的组合服务方式服务方式:单个顾客单个顾客,成批顾客成批顾客.服务时间服务时间:确定的确定的,随机的随机的.服务时间服务时间和到达间隔时间至少一个是随机的和到达间隔时间至少一个是随机的.服务时间分布是平稳的服务时间分布是平稳的.运筹学服务时间分布服务时间分布:设某服务台的服务时间为设某服务台的服务时间为v v,其密度函数为其密度函数为b b(t t),),常见的分布有:常见的分布有:(1 1)定长分布
6、()定长分布(D D):):每个顾客接受服务的时间每个顾客接受服务的时间 是一个确定的常数。是一个确定的常数。(2 2)负指数分布()负指数分布(M M):):每个顾客接受服务时间每个顾客接受服务时间 相互独立,具有相互的负指数分布:相互独立,具有相互的负指数分布:其中其中 ,为一常数。,为一常数。-单位时间平均服务完成的顾客数单位时间平均服务完成的顾客数1/1/-每个顾客的平均服务时间每个顾客的平均服务时间运筹学服务时间分布服务时间分布:(3 3)k k阶爱尔朗(阶爱尔朗(ErlangErlang)分布:每个顾客接受服务分布:每个顾客接受服务 时间服从时间服从k k阶爱尔朗分布,其密度函数为
7、:阶爱尔朗分布,其密度函数为:运筹学 符号表示符号表示:X/Y/ZX 顾客到达间隔时间分布顾客到达间隔时间分布Y-服务时间分布服务时间分布Z-服务台个数服务台个数X,Y 可以是可以是:M-M-负指数分布负指数分布D-D-确定型确定型E Ek k-k-k阶阶ErlangErlang分布分布GI-GI-一般相互独立的到达时间间隔分布一般相互独立的到达时间间隔分布G-G-一般一般(General)General)时间分布时间分布三、三、排队系统的分类排队系统的分类运筹学 扩展符号表示扩展符号表示:X/Y/Z/A/B/CA-系统容量系统容量B-顾客源中顾客的数量顾客源中顾客的数量C-服务规则服务规则:
8、FCFS,LCFS,等等等等.若省略后三项,即是指下面的情形:若省略后三项,即是指下面的情形:X/Y/Z/FCFS例:M/M/s/K表示?运筹学 已知已知:顾客到达间隔时间分布顾客到达间隔时间分布,服务时间分布服务时间分布.求求:队长队长:Ls-系统中的顾客数系统中的顾客数.排队长排队长(队列长队列长):Lq-队列中的顾客数队列中的顾客数.Ls=Lq +正在接受服务的顾客数正在接受服务的顾客数逗留时间逗留时间:W S-顾客在系统中的停留时间顾客在系统中的停留时间 等待时间等待时间:Wq-顾客在队列中的等待时间顾客在队列中的等待时间.WS=Wq+服务时间服务时间忙期忙期,损失率损失率,服务强度服务强度.四、四、排队问题的求解排队问题的求解