( 数学建模)排队论模型.ppt
《( 数学建模)排队论模型.ppt》由会员分享,可在线阅读,更多相关《( 数学建模)排队论模型.ppt(48页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、排排 队队 论论 模模 型型 朱建青朱建青(苏州科技学院信息与计算科学系)(苏州科技学院信息与计算科学系)排队论模型排队论模型 一、排队论的基本概念一、排队论的基本概念 二、单通道等待制排队问题二、单通道等待制排队问题 (MM1排队系统)排队系统)三、多通道等待制排队问题三、多通道等待制排队问题 (MMc排队系统)排队系统)一、排队论的基本概念一、排队论的基本概念(一)排队过程(一)排队过程 1.1.排队系统排队系统 “排排队队”是是指指在在服服务务机机构构处处要要求求服服务务对对象象的的一一个个等等待待队队列列,而而“排排队队论论”则则是是研研究究各各种种排排队队现现象象的的理理论。论。在在
2、排排队队论论中中,我我们们把把要要求求服服务务的的对对象象称称为为“顾顾客客”,而而将将从从事事服服务务的的机机构构或或人人称称为为“服服务务台台”。在在顾顾客客到到达达服服务务台台时时,可可能能立立即即得得到到服服务务,也可能要等待到可以利用服务台的时候为止。也可能要等待到可以利用服务台的时候为止。排队系统队列除了有形的还有无形的排队系统队列除了有形的还有无形的。排队系统中的排队系统中的“顾客顾客”与与“服务台服务台”这两个名这两个名词可以从不同的角度去理解。词可以从不同的角度去理解。排队系统排队系统顾客顾客服务台服务台上、下班的工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车
3、病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工 在上述顾客在上述顾客-服务台组成的排队系统中,顾客到服务台组成的排队系统中,顾客到来的时刻与服务台进行服务的时间一般来说是随不来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的,往往预先无法确定。因同的时机与条件而变化的,往往预先无法确定。因此,系统的状态是随机的,故而排队论也称此,系统的状态是随机的,故而排队论也称随机服随机服务系统务系统。各各式式各各样样的的排排队队现现象象呈呈现现的的基基本本特特征征:排排队队系系统统由输入过程、
4、排队规则及服务机构三部分组成。由输入过程、排队规则及服务机构三部分组成。(1)(1)输入过程输入过程 输入过程就是顾客按怎样的规律到达,它首先应输入过程就是顾客按怎样的规律到达,它首先应包括顾客总体数,是有限的还是无限的;其次应说明包括顾客总体数,是有限的还是无限的;其次应说明顾客到达的方式,是成批到达顾客到达的方式,是成批到达(每批数量是随机的还每批数量是随机的还是确定性的是确定性的)还是单个到达;最后应说明相继到达的还是单个到达;最后应说明相继到达的顾客顾客(或批或单个或批或单个)之间的时间间隔的分布是什么。之间的时间间隔的分布是什么。2.2.排队系统的组成和特征排队系统的组成和特征 排队
5、规则是指到达的顾客以怎样的规则接受服务。排队规则是指到达的顾客以怎样的规则接受服务。1 1)损损失失制制:顾顾客客到到达达,服服务务台台不不空空立立即即离离去去,另求服务。另求服务。2 2)等等待待制制:顾顾客客到到达达,排排队队等等待待。对对等等待待制制服服务务可可分分为为:先先到到先先服服务务,后后到到先先服服务务,优优先先服服务务,随随机服务,成批服务等。机服务,成批服务等。3 3)混合制:)混合制:在现实生活中,很多服务系统介于在现实生活中,很多服务系统介于损失制和等待制之间,当顾客到达时,服务台不空就损失制和等待制之间,当顾客到达时,服务台不空就排队,若排队的位置已满就离去。排队,若
6、排队的位置已满就离去。(2)(2)排队规则排队规则 服务机构主要指服务台的数目,多个服务服务机构主要指服务台的数目,多个服务台进行服务时,服务方式是并联还是串联;服台进行服务时,服务方式是并联还是串联;服务时间服从什么分布等。务时间服从什么分布等。(3)(3)服务机构服务机构 1.1.排队模型的分类排队模型的分类 D.G.KendallD.G.Kendall引引进进了了排排队队模模型型分分类类符符号号,现现已已广广泛采用,这里仅针对并列的服务台。泛采用,这里仅针对并列的服务台。记记X X:顾顾客客到到达达的的时时间间间间隔隔分分布布;Y Y:服服务务时时间间的的分布;分布;Z Z:服务台数。则
7、排队模型:服务台数。则排队模型:X XY YZ Z。常常用用的的记记号号:M M负负指指数数分分布布;D D确确定定型型;EkEkk k阶阶爱爱尔尔朗朗(ErlangErlang)分分布布;GIGI一一般般相相互互独独立立的的随随机机分分布布,G G一一般般随随机机分分布布。这这里里主主要要讨讨论论M MM M1 1,M MM MC C。(二)排队模型的分类及数量指标(二)排队模型的分类及数量指标 (1)(1)队长队长 队队长长是是指指系系统统中中的的顾顾客客数数(包包括括排排队队等等候候和和正正在在接接受受服服务务的的顾顾客客数数);等等待待队队长长是是指指系系统统中中等等待待服服务务的的顾
8、顾客客数数。无无论论是是队队长长还还是是等等待待队队长长,都都是是顾顾客客和和服服务务机机构构最最关关心心的的数数量量指指标标,特特别别是是对对系系统统设设计计者者来来说说,尤尤为为重重要要,因因为为它它涉涉及及到到系系统统等等待待空空间间的大小。的大小。2.2.排队模型的数量指标排队模型的数量指标 逗留时间是指一顾客从进入系统起一直到接受逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间;等待时间是指服务后离开系统为止所花费的时间;等待时间是指一顾客从进入系统起到接受服务时所花费的时间。一顾客从进入系统起到接受服务时所花费的时间。显然,一个顾客的逗留时间等于其等待时间与接
9、受显然,一个顾客的逗留时间等于其等待时间与接受服务的时间之和。逗留时间与等待时间对顾客来说服务的时间之和。逗留时间与等待时间对顾客来说是最关心的,因为每个顾客都希望自己用于排队等是最关心的,因为每个顾客都希望自己用于排队等待的时间愈短愈好。待的时间愈短愈好。(2)(2)逗留时间逗留时间 忙期是指从顾客到达空闲服务机构起到服务机构忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间,即服务机构连续繁忙的再次为空闲为止的这段时间,即服务机构连续繁忙的时间长度。这是服务机构最关心的数量指标,因为它时间长度。这是服务机构最关心的数量指标,因为它直接关系到服务员的工作强度,与忙期相对应的是
10、闲直接关系到服务员的工作强度,与忙期相对应的是闲期,即为服务机构连续保持空闲的时间长度。显然,期,即为服务机构连续保持空闲的时间长度。显然,在排队系统中,忙期与闲期是交错出现的。在排队系统中,忙期与闲期是交错出现的。(3)(3)忙期忙期1.1.最简单流与最简单流与PoissonPoisson过程过程 记记随随机机过过程程x x(t t):t0t0为为时时间间0 0,t t内内流流(事事件件)发发生生的的次次数数,例例如如对对于于随随机机到到来来某某电电话话交交换换台台的的呼呼叫叫,以以x x(t t)表表示示该该交交换换台台在在0 0,t t这这段段时时间间内内收收到到呼呼叫叫的的次次数数;若
11、若是是服服务务机机构构,可可以以用用x x(t t)表示该机构在表示该机构在0 0,t t时间内来到的顾客数时间内来到的顾客数。(三)(三)PoissonPoisson流与指数分布流与指数分布最简单流应最简单流应 具有以下特征称具有以下特征称(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 ,的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不交接的时间区间序列 ,是一组相互独立的随机变量。是一组相互独立的随机变量。(3)(3)流具有普通性流具有普通性即在即在 时间内,事件发生多于时间内,事件发生多于1 1次的概率为
12、次的概率为 。定理定理1 1设设 是最简单流,则对任何是最简单流,则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程,最简单流亦称过程,最简单流亦称PoissonPoisson流,特别取流,特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位时间内事件发生次数的平均数。2.2.PoissonPoisson流的发生时间间隔分布流的发生时间间隔分布 当当流流(过过程程)构构成成PoissonPoisson过过程程时时,就就称称为为PoissonPoisson流流。设设流流发发生生的的时时刻刻依依次次为为 ,
13、,发生的时间间隔记为发生的时间间隔记为 ,其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要条件是 的的流流发发生生时时间间间间隔隔 相相互互独独立立,且且服服从从相同的负指数分布,即相同的负指数分布,即3.3.负指数分布的负指数分布的MarkovMarkov特性特性定定理理3 3设设T T为为连连续续型型随随机机变变量量,且且T0T0,那那么么,T T服服从从负指数分布的充要条件是:对任何负指数分布的充要条件是:对任何 ,都有,都有上式可改写为:对任何上式可改写为:对任何 ,都有,都有 如如果果把把T T解解释释为为寿寿命命,上上式式表表明明:如
14、如果果已已知知年年龄龄大大于于 岁岁,则则再再活活x x年年的的概概率率与与以以前前的的 (年年)无无关关,所以有时又风趣地称指数分布是所以有时又风趣地称指数分布是“永远年轻永远年轻”。上上面面两两式式表表明明连连续续型型随随机机变变量量T T的的MarkovMarkov特特性性当当且仅当非负随机变量服从负指数分布时才具有。且仅当非负随机变量服从负指数分布时才具有。例例1 1 设设某某一一服服务务系系统统的的输输入入流流是是PoissonPoisson流流,平平均均每每3 3分钟进入分钟进入5 5名顾客,试计算:名顾客,试计算:(1)12(1)12分钟内进入分钟内进入1515名顾客的概率;名顾
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学建模排队论模型 数学 建模 排队 模型
限制150内