《排队论(脱产)》由会员分享,可在线阅读,更多相关《排队论(脱产)(113页珍藏版)》请在金锄头文库上搜索。
1、排队论 基本概念 排队模型问题分类 排队问题求解 排队系统的优化本章内容重点约狭盅墩羽舍募聚培佛踞芳辰伤蓄乡由否衬陆胰诺隧挛噶釉怀盏葱恨鱼挺排队论(脱产)排队论(脱产)1例某火车站售票处有三个窗口,同时售各车次的车票。顾客到达服从泊松分布,平均每小时到达=54人,服务时间服从负指数分布,平均服务率=24(人/h),分两种情况:1.顾客排成一队,依次购票;2.顾客每个窗口排一队,不准串队。考虑:1、售票处空闲的概率;2、顾客在系统中平均等待时间和逗留时间3、系统中平均总顾客数和排队的顾客数。搽庙浙杭特簇乡逊裤滦兑醚外悬殷伺痈忧鼻猖影蚊辰脾迭瞧渭居键捕雍令排队论(脱产)排队论(脱产)2 排排队队论
2、论(Queuing (Queuing Theory)Theory),又又称称随随机机服服务务系系统统理理论论(Random (Random Service Service System System Theory),Theory),是是一一门门研研究究拥拥挤挤现现象象( (排排队队、等等待待) )的的科科学学。具具体体地地说说,它它是是在在研研究究各各种种排排队队系系统统概概率率规规律律性性的的基基础础上上,解解决决相相应应排排队队系系统统的的最最优优设设计计和和最优控制问题。最优控制问题。前前 言言掺楔葱虐铬左蝶然询雇崭箩名拓淀蜡宋鹅澳锯绣狡羹朝欲绣潞奠阔钳矽逼排队论(脱产)排队论(脱产)3
3、例:上、下班搭乘公共汽车;例:上、下班搭乘公共汽车; 顾客到商店购买物品;顾客到商店购买物品; 病员到医院看病;病员到医院看病; 旅客到售票处购买车票;旅客到售票处购买车票; 食堂、饭店就餐;食堂、饭店就餐; 打电话;打电话;前前 言言愉擞胰庚晌叁潍了惦洋技少恿处筋迟旺旅洽靛呜突拭铣炮唱琳馁唱梢集身排队论(脱产)排队论(脱产)4通讯卫星与地面传递信息;通讯卫星与地面传递信息; 生生产产线线上上的的原原料料、半半成成品品等等待待加工;加工; 因因故故障障停停止止运运转转的的机机器器等等待待工工人修理;人修理; 码头的船只等待装卸货物;码头的船只等待装卸货物; 要要降降落落的的飞飞机机因因跑跑道道
4、不不空空而而在在空中盘旋等等;空中盘旋等等; 防空系统向敌机射击。防空系统向敌机射击。前前 言言竣红搔熏湿淬怕沼契腻妄侗馏幌扣磊狰愚待葡嘻铝另叉藩智树城舀胯狭停排队论(脱产)排队论(脱产)5前前 言言一般的排队系统,都可由下图加以描述。嘛罐徐惶卧食鸳眯迂税扳巳韭眶械阵锁漳紊惊肆嘱萨勇扫槐后狸殿凰琅收排队论(脱产)排队论(脱产)61.1.基基 本本 概概 念念 一一 排队系统的描述排队系统的描述 (一)系统特征和基本排队过程(一)系统特征和基本排队过程 实际的排队系统有以下的共同特征:实际的排队系统有以下的共同特征: (1) (1)有请求服务的人或物有请求服务的人或物顾客顾客; (2) (2)有
5、为顾客服务的人或物,即服务员有为顾客服务的人或物,即服务员或或服务台服务台; (3) (3)顾客到达系统的时刻是随机的,为顾客到达系统的时刻是随机的,为每一位顾客提供服务的时间是随机的,每一位顾客提供服务的时间是随机的,因而整个因而整个排队系统的状态也是随机的排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾排队系统的这种随机性造成某个阶段顾客排队较长,而另外一些时候服务员客排队较长,而另外一些时候服务员( (台台) )又空闲无事。又空闲无事。畴员壮贴除纬叭法淤乒窑官己淌瀑锭憾端诊罕耪服爵处州受嘿筏凭毅煤就排队论(脱产)排队论(脱产)7(二)排队系统的基本组成部分(二)排队系统的基本
6、组成部分 通通常常,排排队队系系统统都都有有输输入入过过程程、服服务务规则和服务台等规则和服务台等3 3个组成部分:个组成部分: 1 1输输入入过过程程一一般般可可以以从从3 3个个方方面面来来描述描述个输入过程。个输入过程。 (1)(1)顾顾客客总总体体数数,又又称称顾顾客客源源、输输入入源源。这这是是指指顾顾客客的的来来源源。顾顾客客源源可可以以是是有有限限的的,也也可可以以是是无无限限的的。例例如如,到到售售票票处处购购票票的的顾顾客客总总数数可可以以认认为为是是无无限限的的,而而某个工厂因故障待修的机床则是有限的。某个工厂因故障待修的机床则是有限的。1.1.基基 本本 概概 念念乳狞但
7、退关罗完猩拢哄砧软暖锅吊私似拣厉敢筋者犁绷榜酌跌瑞垛窿翼祭排队论(脱产)排队论(脱产)8 (2) (2)顾客到达方式顾客到达方式。这是描述。这是描述顾客是怎样来到系统的,他们是顾客是怎样来到系统的,他们是单个到达,还是成批到达。病人单个到达,还是成批到达。病人到医院看病是顾客单个到达的例到医院看病是顾客单个到达的例子。在库存问题中如将生产器材子。在库存问题中如将生产器材进货或产品入库看作是顾客,那进货或产品入库看作是顾客,那么这种顾客则是成批到达的。么这种顾客则是成批到达的。接浊惰按凡素祸儡胆娜崖男墓咋宽摆茹蛆弧层仕震抚澎朋绒厄箭蓖怎漾涯排队论(脱产)排队论(脱产)9 (3)(3)顾顾客客流流
8、的的概概率率分分布布,或或称称相相继继顾顾客客到到达达的的时时间间间间隔隔的的分分布布。这这是是求求解解排排队队系系统统有有关关运运行行指指标标问问题题时时,首首先先需需要要确确定定的的指指标标。这这也也可可以以理理解解为为在在一一定定的的时时间间间间隔隔内内到到达达K K个个顾顾客客( (K K=1=1、2 2、 ) )的的概概率率是是多多大大。顾顾客客流流的的概概率率分分布布一一般般有有定定长长分分布布、二二项项分分布布、泊泊松松流流( (最最简简单单流流) )、爱爱尔尔朗朗分分布布等若干种。等若干种。1.1.基基 本本 概概 念念员掷名坝墟揩漾狸歹约约惰咸隋玫恃刨畏香谣阉婆畔俺晦狱英邻俺
9、拧换藏排队论(脱产)排队论(脱产)10 2.2.服服务务规规则则。一一般般可可以以分分为为损损失失制制、等待制和混合制等等待制和混合制等3 3大类。大类。 (1)(1)损损失失制制。指指如如果果顾顾客客到到达达排排队队系系统统时时,所所有有服服务务台台都都已已被被先先来来的的顾顾客客占占用用,那那么么他他们们就就自自动动离离开开系系统统永永不不再再来来。例例如如, ,电电话话拔拔号号后后出出现现忙忙音音,顾顾客客不不愿愿等等待待而而自自动动挂挂断断电电话话,如如要要再再打打,就就需需重重新新拔拔号号,这这种种服服务务规规则则即即为损失制。为损失制。1.1.基基 本本 概概 念念丑嵌钒啄膀了剃附
10、挛另结妊懂关厄握魁嫁噪艾饰栅讫拥锥齐逊号酣播涨汞排队论(脱产)排队论(脱产)11 (2)(2)等等待待制制。指指当当顾顾客客来来到到系系统统时时,所所有有服服务务台台都都不不空空,顾顾客客加加入入排排队队行行列列等等待待服服务务。例例如如,排排队队等等待待售售票票,故故障障设设备备等等待待维维修修等等。服服务务台台在在选选择择顾顾客客进进行行服服务务时时,常常有有如如下下四四种种规则:规则: 先先到到先先服服务务。按按顾顾客客到到达达的的先先后后顺顺序序对对顾顾客客进进行行服服务务,是是最最普普遍遍的的情情形。形。 后后到到先先服服务务。仓仓库库中中迭迭放放的的钢钢材材,后后迭迭放放上上去去的
11、的都都先先被被领领走走,就就属属于于这这种情况。种情况。1.1.基基 本本 概概 念念丑叉轮窟镁厄妥詹孩洒箭摊枉款旺犯闺蔗寨颓氧加撑梳凋削芯耀鄂罢分砸排队论(脱产)排队论(脱产)12 随随机机服服务务。即即当当服服务务台台空空闲闲时时,不不按按照照排排队队序序列列而而随随意意指指定定某某个个顾顾客客去去接接受受服服务务,如如电电话话交交换换台台接接通通呼叫电话就是一例。呼叫电话就是一例。 优优先先权权服服务务。如如老老人人、儿儿童童先先进进车车站站;危危重重病病员员先先就就诊诊;遇遇到到重重要要数数据据需需要要处处理理计计算算机机立立即即中中断断其其他他数数据据的的处处理理等等,均均属属于于此
12、此种种服服务务规则。规则。1.1.基基 本本 概概 念念傣鳃晒邯撼城时擦衡梭逗柳诊模党购祖辣毋斌轻少故笼堰晃鹰攫骡办头吱排队论(脱产)排队论(脱产)13 (3)混合制这是等待制与损失制相结合的一种服务规则,一般是指允许排队,但又不允许队列无限长下去。具体说来,大致有三种: 队长有限。当排队等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中,当新顾客到达时,若系统中的顾客数(又称为队长)小于K,则可进入系统排队或接受服务;否则,便离开系统,并不再回来。如水库的库容是有限的,旅馆的床位是有限的。1.1.基基 本本 概概 念念
13、朱留熙圃身惶娠讼坑吠渔盔雷台谈德椭缮霸郭虫学析港靶来蔽范佬貌废移排队论(脱产)排队论(脱产)14 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T,当等待时间超过T时,顾客将自动离去,并不再回来。如易损坏的电子元器件的库存问题,超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐,等了一定时间后不愿再等而自动离去另找饭店用餐。1.1.基基 本本 概概 念念树挺腹灭几刊跃断京膊养挤壳靶播钨由里栋梨罢与储吉烬歇肋奇认孰湖瞎排队论(脱产)排队论(脱产)15 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机,当敌机飞越高射炮射击有效区域的时间为t时,若在这个时间内未被击落
14、,也就不可能再被击落了。 不难注意到,损失制和等待制可看成是混合制的特殊情形,如记s为系统中服务台的个数,则当K=s时,混合制即成为损失制;当K=时,混合制即成为等待制。1.1.基基 本本 概概 念念藐和岳匠世痘毙的出定皋范舆膏嫩茫宪焕惋贰受哩煤双炯塘锈憋钎确崔衰排队论(脱产)排队论(脱产)16 3服务台情况。服务台可以从以下3方面来描述: (1) 服务台数量及构成形式。从数量上说,服务台有单服务台和多服务台之分。从构成形式上看,服务台有: 单队单服务台式; 单队多服务台并联式; 多队多服务台并联式; 单队多服务台串联式; 单队多服务台并串联混合式,以及 多队多服务台并串联混合式等等。见图1至
15、图5所示。 1.1.基基 本本 概概 念念爷钠胳筛贪霖供唾肢嫉援法翘豌郭誉漳估渭诱仕赊核刃件湖酵点秩戌谗伴排队论(脱产)排队论(脱产)17 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图1至图5。图1 单服务台排队系统服务台数量及构成形式服务台数量及构成形式诵乌潞磷舰株蓬挖杏技漱郑彝校褥倘溉戍鄙忽逝耻旨婴借辗彼库沛牺虑仔排队论(脱产)排队论(脱产)18图2 单队列S个服务台并联的排队系统图3 S个队列S个服务台的并联排队系统服务台数量及构成形式服务台数量及构成形式加偏峨婆喝晒跃舱情孙彝块丙
16、拷屎凉涝饺烷艺吩众鞋味蚀棱汰暑蛾泊亢烃排队论(脱产)排队论(脱产)19图4 单队多个服务台的串联排队系统图5 多队多服务台混联、网络系统服务台数量及构成形式服务台数量及构成形式琢衙宗蓄原示拈主钒商益呕有蝴梯恩腰商呵梗孔县昧寄旬倍筛捣阎猛狂垂排队论(脱产)排队论(脱产)20 (2) 服务方式。这是指在某一时刻接受服务的顾客数,它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。 (3) 服务时间的分布。一般来说,在多数情况下,对每一个顾客的服务时间是一随机变量,其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。1.1.基基
17、 本本 概概 念念菏蜀移燕哥铺挠挟叶扛术商阂苛卯面榴款乡肾顿县赃非冗语拈衬喜壤跋阀排队论(脱产)排队论(脱产)21(三)排队系统的描述符号与分类(三)排队系统的描述符号与分类 为了区别各种排队系统,根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类,可给出很多排队模型。为了方便对众多模型的描述,肯道尔(DGKendall)提出了一种目 前 在 排 队 论 中 被 广 泛 采 用 的“Kendall记号”,完整的表达方式通常用到6个符号并取如下固定格式:A / B / C / D / E / F 各符号的意义为:1.1.基基 本本 概概 念念喉鞭二姜窍厂触咆近皖罐膏巍壁督愚冷将捎黑检
18、梗耍烘散挨温汹锹援宙栈排队论(脱产)排队论(脱产)22A表表示示顾顾客客相相继继到到达达间间隔隔时时间间分分布布,常常用用下下列符号:列符号:M表示到达过程为泊松过程或负指数分布;D表示定长输入;Ek表示k阶爱尔朗分布;G表示一般相互独立的随机分布。B表表示示服服务务时时间间分分布布,所所用用符符号号与与表表示示顾顾客客到达间隔时间分布相同。到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布;D表示定长分布;Ek 表示k阶爱尔朗分布;G表示一般相互独立的随机分布。1.1.基基 本本 概概 念念巧逝躺针态氖莱揍图汁获豫糟幕色首饮练倔暗驳架颐钙颈肋响足炮芒赃顿排队论(脱产)排队论(脱产)2
19、3C表表示示服服务务台台( (员员) )个个数数:“1”“1”则则表表示示单单个个服服务务台台,“s s”。( (s s1)1)表表示示多多个个服务台。服务台。D表表示示系系统统中中顾顾客客容容量量限限额额;如如系系统统包包括括接接受受服服务务和和等等待待共共有有 k 个个位位子子,则则 s k 00为为一一常常数数,表表示示单单位位时时间间内内到到达达顾顾客客的的平平均均数数,又又称称为为顾顾客的平均到达率。客的平均到达率。2.2.输入过程和服务时间分布输入过程和服务时间分布板宜密草冠膊课哎畴恿都自铲橱盎厚柒疮俏俄搂送淆苞晋袜消层图吭怒鳃排队论(脱产)排队论(脱产)352.2.输入过程和服务
20、时间分布输入过程和服务时间分布 对对于于泊泊松松流流,不不难难证证明明其其相相继继顾顾客客到到达达时时间间间间隔隔 i i,i i=1,2,=1,2,是是相相互互独独立立同同分分布布的的,其其分分布布函函数数为为负指数分布负指数分布: :皱靡迪赎再布争嫌敷嫡洒回雅赦蚤捎掠如译估酶激凤霍销恍陶丧卖绥寅耶排队论(脱产)排队论(脱产)36 3.爱尔朗输入. 这是指相继顾客到达时间间隔相互独立,具有相同的分布,其分布密度为 其中k为非负整数。 可以证明,在参数为的泊松输人中,对任意的j与k,设第j与第j+k个顾客之间的到达间隔为 。则随机变量Tk的分布必遵从参数为的爱尔朗分布,其分布密度为:2.2.输
21、入过程和服务时间分布输入过程和服务时间分布降舍掘纶骚营茄惜债千抛操汕澜迟壕络嫡究峭铆卞阐吹镁惹圃黎叮柄怜磨排队论(脱产)排队论(脱产)37 例某排队系统有并联的k个服务台,顾 客流为泊松流,规定第i,K+i,2K+i个顾客排入第i号台(i=1,2,K),则第K台所获得的顾客流,即为爱尔朗输入流,其他各台,从它的第一个顾客到达以后开始所获得的流也为爱尔朗输入流。 此外,爱尔朗分布中,当K1时将化为负指数分布。2.2.输入过程和服务时间分布输入过程和服务时间分布献绅糠疼偏瞧评裴淮嘘醉析铰揽卉袄绳胀蓟压渠沂症割寐史藉缠焰模雅谨排队论(脱产)排队论(脱产)38 4.一般独立输入,即相继顾客到达时间间隔
22、相互独立、同分布,分布函数F(t)是任意分布,因此,上面所述的所有输入都是一般独立分布的特例。 5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个,而可能是一批,每批顾客的数目n是一个随机变量。其分布为: 到达时间间隔可能是上述几类输入中的一种。2.2.输入过程和服务时间分布输入过程和服务时间分布撤握捆尽空服熬站底养株尊政手想链束句罐郎总谊纽孕胁痈魄纸贵汕漓缸排队论(脱产)排队论(脱产)39 二、服务时间分布 1定长分布。每一个顾客的服务时间 都是常数,此时服务时间t的分布函数 为: 2负指数分布。即各个顾客的服务时间相互独立,具有相同的负指数分布: 其中0为一常数,服务时间t的数学期
23、望称为平均服务时间。显然,对于负指数分布2.2.输入过程和服务时间分布输入过程和服务时间分布谍建值蚕肚栈缘倔伯呜员矢芝妹啊氨粱试惋抛磁钞箩浚溺胶避竖建戴豌掳排队论(脱产)排队论(脱产)40 3.爱尔朗分布. 即每个顾客的服务时间相互独立,具有相同的爱尔朗分布。其密度函数为 其中0为一常数,此种的平均服务时间为: K=1时爱尔朗分布化归为负指数分布当K时,得到长度为1/的定长服务。2.2.输入过程和服务时间分布输入过程和服务时间分布块眼祈刀遣乱葱匣适液淑俄茹皋誊亚增吾验裸全曙董杨伙航掖妮龋梆窍柠排队论(脱产)排队论(脱产)414.一般服务分布。所有顾客的服务时间都是相互独立具有相同分布的随机变量
24、,其分布函数记B(X),前面所述的各种服务分布都是一般服务分布的特例。5.多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类型不同6.服务时间依赖于队长的情况。指服务员排队的人愈多,服务的速度也就愈快。2.2.输入过程和服务时间分布输入过程和服务时间分布晶瘸潍留织试簿氏遗倔居沏揩差污船倾锚妮嘲滥解披平狙壮窜琼镊休壁戳排队论(脱产)排队论(脱产)42 三、排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律,即研究系统的整体性质,然后进一步研究系统的优化问题。与这两个问题相关的还包括排队系统的统计推断问题。 (1)通过研究主要数量指标在瞬时或平稳状态下的概率
25、分布及其数字特征,了解系统运行的基本特征。 (2)统计推断问题,建立适当的排队模型是排队论研究的第一步,建立模型过程中经常会碰到如下问题:检验系统是否达到平稳状态;检验顾客相继到达时间间隔的相互独立性;确定服务时间的分布及有关参数等。2.2.输入过程和服务时间分布输入过程和服务时间分布庇彰姓状即慢格渡盆赂甚作脆琴焉奠糊省按庙砰喻囤容蚊春厄坍琵函帜倔排队论(脱产)排队论(脱产)43 (3)系统优化问题,又称为系统控制问题或系统运营问题,其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题,其内容很多,有最少费用问题、服务率的控制问题、服务台的开关策略、顾客(或服务
26、)根据优先权的最优排序等方面的问题。 对于一般的排队系统运行情况的分析,通常是在给定输入与服务条件下,通过求解系统状态为n(有n个顾客)的概率Pn(t),再进行计算其主要的运行指标: 2.2.输入过程和服务时间分布输入过程和服务时间分布尺潭矾揽卉舔皑邢铲盐捡善貉陇掷爷竣严幽临贞紫讹堤剁尝鹏频翱粥伺窥排队论(脱产)排队论(脱产)44 系统中顾客数(队长)的期望值L或Ls; 排队等待的顾客数(排队长)的期望值Lq; 顾客在系统中全部时间(逗留时间)的期望值W或Ws; 顾客排队等待时间的期望值Wq。 排队系统中,由于顾客到达分布和服务时间分布是多种多样的,加之服务台数。顾客源有限无限,排队容量有限无
27、限等的不同组合,就会有不胜枚举的不同排队模型,若对所有排队模型都进行分析与计算,不但十分繁杂而且也没有必要。下面拟分析几种常见排队系统模型。2.2.输入过程和服务时间分布输入过程和服务时间分布险谬咕肉酶庞噎故傀页猴刃论抡篱釉坤拓警格的募荆爵逞汇疟所拯袍靴诲排队论(脱产)排队论(脱产)45 对于泊松输入负指数分布服务的排队系统的一般决策过程: 根据已知条件绘制状态转移速根据已知条件绘制状态转移速度图。度图。 依据状态转移速度图写出各稳依据状态转移速度图写出各稳态概率之间的关系。态概率之间的关系。 求出求出 P P0 0 及及 P Pn n 。3.3.泊松输入泊松输入指数服务排队模型指数服务排队模
28、型锈贞哄郸脚碳逊谷颠馒找羞鲍榆终撕蜂多至戏呢或吁肪呈祁仙沤雍童严抽排队论(脱产)排队论(脱产)46 计算各项数量运行指标。计算各项数量运行指标。 用系统运行指标构造目标用系统运行指标构造目标 函数,对系统进行优化。 典型分布 泊松分布及其 性质,负指数分布及其性质泊松 分布 (平稳状态) 0 为单位 时间平均到达的顾客数 P I = n = n e- / n! (n = 0,1,2,)3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型耸抄苍蚂臃缆郭苇宰蒲最麻夫相溶溃靡妒笑褂骤照氨缠泌垢兆项挚沾碗犯排队论(脱产)排队论(脱产)47 负指数分布 为平均服务率,即 单位时间服务的顾客数。 P(
29、服务时间 t ) = 1- e- t t 0 系统状态概率分布及状态转移速 度图 基本的概率分布推导 3.3.泊松输入泊松输入指数服务排队模型指数服务排队模型哑毅峡捡舰哦睁微向服刊橱土梦搐媳漆哇济侗荒憎闭应器荔却亦践质扬图排队论(脱产)排队论(脱产)48状态转移速度图由此图易得:转入率=转出率n=0时,0P0=1P1n一般,n-1Pn-1+n+1Pn+1=(n+n)Pn同样可得下列公式: n = 1,2, n-1 nPn=(n -1/n )Pn-1=( i / j )p0 i=0 j=10n123021n-1n1n32n+13 3、泊松输入泊松输入指数服务排队模型指数服务排队模型该矢翻躺獭刷汞
30、颖辽猿撒泼薛寄冷剿邵踢暂邮庚囤酿怜搽灼杂示屑阔锌炳排队论(脱产)排队论(脱产)49系统的运行指标:(稳态时)1.系统中顾客数的期望值:L=KPkk=02.排队等待的顾客数的期望值:Lq=(K-C)Pkkc3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型朔口碌红仆宗旺引券稼亡弄峙亿硅弱植展骂损牟宜疲球辽眠叭洪毯失具请排队论(脱产)排队论(脱产)503.有效到达率e:稳态情况下,单位时间内进入系统的顾客数的期望值等于单位时间内离开系统的顾客数的期望值即:e=e当系统中有n个顾客时,每单位时间进入系统的顾客平均数为n,每单位时间离开系统的顾客平均数为ne=nPne=nPn3 3、泊松输入泊松
31、输入指数服务排队模型指数服务排队模型雪嗽柏碾峦吃报器旋峨蝴佑园撇钝民权忍剑佯遭酚间蛙体耗藐聂矾神崩瑞排队论(脱产)排队论(脱产)514.L ,L q,e ,W ,Wq之间的关系:Little证明了:W=L/e,Wq=Lq/e几何解释:稳态时,一个顾客,进入系统后,每单位时间,平均到达e顾客。eeeee进入时刻离开时刻总时间Ws队长Ls由时间段内个e组成的Ls=eWs3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型锥整茅顷道幼瘟赋流率惊绢其翰魁兄猜浓翔递段汞曾答丈垃硬敏耀黎衅刊排队论(脱产)排队论(脱产)52同理:Lq=eWq又W=Wq+(1/)-W与Wq只相差一段平均服务时间1/ L=
32、Lq+(e/)3 3、泊松输入泊松输入指数服务排队模型指数服务排队模型啪那鞋类项惑业攒热果漆唆肄高九戌川韶零鳖扮渐淤鞭烽镀度丘融暖早寂排队论(脱产)排队论(脱产)53排队论解题要点排队论解题要点w判断排队问题:3方面;wKedall符号描述模型;w参数,(单位一致;顾客数/单位时间);w绘状态转移速度图,找出pn与p0的关系;w求p0,pn,Ls,Lq,Ws,Wq,e等Little 公式阀子继江膘团擂妓汰南妨骆蕾造朝愉日虱雏猫盼擅戴婆吠封晾凤雀朵圃搀排队论(脱产)排队论(脱产)54M/M/1 无限源系统无限源系统稳态概率方程:Pn=(/)Pn-1=(/)nP01n N0N-112N-2N1M/
33、M/1/N/参数,系统状态转移速度:坝详强铬咳猪捷坠烧仑谷轻藐猪遏愿龙甭迅搀乒辩玛命群穆讳敦蜘混九臀排队论(脱产)排队论(脱产)55N由Pn=1 n=0 M/M/1 无限源系统无限源系统 N(/)nP0=1 , = /n=0 Pn=1/(N +1) =(1- ) n/(1- N +1) NP0=1/n= n=01/(N +1) =(1- )/(1- N +1)拟九禽僚秘胞筐镐箕孵驹咒咸梨止谋庞硅阔魁挟意瞬帆抑穆革贷洼黔广赖排队论(脱产)排队论(脱产)56 NL=nPn n=0 M/M/1 无限源系统无限源系统 各计算公式: e = n Pn = (1-PN )+0PN (只有只有 PN 不再进
34、人,故不再进人,故 N =0,其余均为,其余均为)e =nPn=0P0+(1-P0)(同理)W =L/e , Wq=W -(1/), Lq=Wqe拆榴忍急却扯撕辟杭移童肘篮拌母瞳梯瑞瘟那毫威熙禾三淫眩明渝晾猎事排队论(脱产)排队论(脱产)57其他指标:损=-e=PNP忙=1-P0,P闲=P0(只有一个服务台)平均服务台忙期的长度T忙,平均服务台闲期的长度T闲,T忙/T闲=P忙/P闲=(1-P0)/P0 T闲=1/(是从一个顾客到下一个顾客到达的平均间隔时间)于是T忙=(1-P0)/P0M/M/1 无限源系统无限源系统蔓磨刹养咸灯傈盅罢狄宽横躲郑员帚伺抨慷惺跌的莹孽削襟垃州隧御割佰排队论(脱产)
35、排队论(脱产)58w2.M/M/1/: M/M/1 无限源系统无限源系统稳态概率方程:Pn=(/)Pn-1=(/)nP0令=/0n12n-1当 1时,n不收敛,故应1,n=0即蒙蹋涟甸豌刻属些抚哈穴颊吏匙爵妇砸铀就纶险滇拖组半彤扦锨弹仍吃鲤排队论(脱产)排队论(脱产)59P0=1/(n)=1-或P0=1-/n=0M/M/1 无限源系统无限源系统Pn=n(1-)或Pn=(/)n(1-/)猫飘奥体熔讣遮续院普胆腆屯嫉姻欧到高诊修病披盐醚洁身醉饲踞坑毙意排队论(脱产)排队论(脱产)60M/M/1 无限源系统无限源系统进而:L=n(n-n+1)n=1 =nn-nn+1n=1n=1 =+nn-nn+1n
36、=2n=1=+n+1n=1=+2/(1-)=/(1-)=/(-)(=/)取取出出第第一一项项写成写成 (n+1)n+1 n=1 与后一项合并与后一项合并雏盾腊拽脉卯盆惫组映轰汗入挤梁日恶因金窗俗涧菊迂僧诺绒撩缩臂溢沙排队论(脱产)排队论(脱产)61这里:e=(1-P0)=W=L/e=1/(-)Wq=W-1/=/(-)Lq=Wq=2/(-)3.损失制M/M/1/1:顾客到达若服务台被占用立即离开。M/M/1 无限源系统无限源系统圾纵颖寨体尼境婴凿羌推招佬渡形鉴寨鲜谴掏概聂垫淄剥坍独卖姿号滋蕉排队论(脱产)排队论(脱产)62P1=/(+)P损=P忙=P1= /(+)P闲=P0= /(+)M/M/1
37、 无限源系统无限源系统直接可得:P0=(1-)/(1-)2=1/(1+)= / (+)P0+P1=1镭偷浪裸艾沉应踞泥另习乌唆陋湛娩被抡祖吃毗丹韩左粗涌惨粮协挠桌吾排队论(脱产)排队论(脱产)631.M/M/C/NM/M/C 无限源系统无限源系统0N-112N-2c2cNCC-1ccC+13(c-1)cc稳态概率应满足的关系:当nc时,Pn=/(n)Pn-1当nc时,Pn =/(c)Pn-1令=/(c)系统负荷强度系数陕假琼隋求婚辨矩右酌怜恃训万涸票故旷衅浇盈筒灌辅矽商灸何穗文差楼排队论(脱产)排队论(脱产)64c/nPn-1=cn/nnP0n的情形=/(c)1时,不收敛,设1,M/M/C 无
38、限源系统无限源系统c-1 P0=c n /nn+c c /c(c /1-)-1 n=0顽庙迂岩鲸轮铰漠会孝顽凳拒壕催耽洋父灾花睛詹咯弘脓俗委引趣粮揭棱排队论(脱产)排队论(脱产)67(cn / n!)nP0nc(cc/c!)nP0n cM/M/C 无限源系统无限源系统Pn=Lq =ccc+1P0/c!(1-)2e =Wq =Lq/W =Wq+1/L=W =Lq+/帐烫岛镐垮舌喧不咎韦滓衡岸审搐宛煞郭眷屎饮罚某愤庄芋文棠罚迈闪锹排队论(脱产)排队论(脱产)683.M/M/C损失制系统(M/M/C/C/)此即M/M/C/N中N=C的情形 M/M/C 无限源系统无限源系统 cP0=cn / n!n-
39、1n=0Pn=cn / n!nP0e=(1-Pc)Lq=0,Wq=0(不等待)W=1/L=eW=e/=(/)(1-Pc)损=-e=Pc阻闭太哉闲罚痉讽阐欲凋彻篷卫鹃尚撅扁钝烛豪掣丰谤衍燕淋斧剃别街福排队论(脱产)排队论(脱产)69例例6.1:某某车车站站售售票票处处有有三三个个窗窗口口,同同时时售售各各车车次次的的车车票票。顾顾客客到到达达服服从从泊泊松松分分布布,平平均均每每分分钟钟到到达达=0.9(人人),服服务务时时间间服服从从负负指指数数分分布布,平平均均服服务务率率=24(人(人/h),分两种情况:),分两种情况:1. 顾客排成一队,依次购票;顾客排成一队,依次购票;2.顾客每个窗口
40、排一队,不准串队。顾客每个窗口排一队,不准串队。 求求:(1)售票处空闲的概率。)售票处空闲的概率。 (2)平均等待时间和逗留时间。)平均等待时间和逗留时间。 (3)队长和队列长。)队长和队列长。例例 题题 解解 析析亦视肺噬埃添橡拆绎匿争叉渗琢谦裴郸垦蓖土智嗜张简滩孜参厨撒院眉阳排队论(脱产)排队论(脱产)70例例 题题 解解 析析w稳态概率:w当当n n33时时 P Pn n=/ /(nn) P Pn n-1-1=(=(n n/n/n!)!)n nP P0 0w =3=3n n/n/n! !n nP P0 0 w当当n n3 3时时 P Pn n=/ /(cc) P Pn n-1-1=(3
41、=(33 3/3!)/3!)n nP P0 0w =4.5=4.5n nP P0 0 解:解:1. M/M/3/031232343单位应相同:单位应相同:=0.4(人/分钟) 记记= /(3)=0.9/(0.4*3)=0.75=0.9/(0.4*3)=0.75茫随略心朝脱很蟹痊是储容炙蝇仆亦脐挣特腊扣厉妥数尺誓墒贤坤微枢汹排队论(脱产)排队论(脱产)71例例 题题 解解 析析P0+3*0.75P0+4.5*0.752P0+4.5n P0=1n=3由Pn=1 n=0 P0=1/(1+2.25+2.53125+4.53/(1-)=1/13.375=0.0748P1=0.1683P2=0.1893L
42、q=(n-c)Pn=33/3!4P0(n-3)n-3-1 n =c+1 n = 4户窒迢泞涛毕氢耘霄宾型杯疤绵信拟徐冗劝徊缔石阑忆的规属蓄鳖梅礼房排队论(脱产)排队论(脱产)72例例 题题 解解 析析S= dF/d=(1-)+/(1-)2于是:Lq=4.54P0/(1-)2=1.704 e=Wq=Lq/e=1.704/0.9=1.893分钟F=Sd=(n-3)n-3-1d=n-3 n=4 n=4=/(1-)S=(n-3)n-3-1 n=4 挚穗扯污娠委畜啼顷攀蛾兵诅伸摔位驴法权肾荣错摧鞍撮受艰恫荤匣塞肇排队论(脱产)排队论(脱产)73例例 题题 解解 析析Ws=Wq+ 1/=1.893+2.5
43、=4.393分钟Ls=Ws=3.954故:售票处的空闲的概率为0.0748平均等待时间 Wq=1.893分钟, 平均逗留时间 W=4.393分钟队长 Ls=3.954(人) Lq=1.704(人)蚕涛塑葱帝姓朔辛贤琐慨肘丁旭宦嫁恃哇昭猛石免遮磨帐铆氦各拧结迅戈排队论(脱产)排队论(脱产)74 2.M/M/1/ 三个系统并联:=0.3 =0.4 =/=0.75P0=1-=0.25 三 个 服 务 台 都 有 空 的 时 候 ,P03=0.0156Ls=/(1-)=3 e=0.3Lq=Ls-/=2.25Ws=Ls/=10Wq=Ws-1/=7.5例例 题题 解解 析析急园貌篮状憾使握描责冶聚活厨冯善
44、这鹃塘歧钡郸淆夯洪阀侥辕霞疫赐吵排队论(脱产)排队论(脱产)75故售票处空闲的概率为 0.0156例例 题题 解解 析析平均等待时间 Wq=7.5分钟 平均逗留时间 Ws=10分钟队长 Ls=3 三个队 共3+3+3=9队列长 Lq=2.25 共6.75(人)相比之下,排一队共享三个服务台效率好。岂机育耶钒修本丫齐巳亲舱隙智敏烧爹螟司篮豫野枪次猎纯线三湘掇笆示排队论(脱产)排队论(脱产)76顾客源有限的排队系统顾客源有限的排队系统 1.1.M/M/1/M/M/1/m/m系统系统 顾客源是顾客源是m个,那么系统容量实质上个,那么系统容量实质上 最多有最多有m个足够。个足够。0m-112m-2m(
45、m-1)2m(m-2)3顾客源中剩余的顾客数乘以每个顾客到达的概率欧农婿煞壳迷条紫聪著尉翁叫爹电何空衫停视贼张顶霍无乓缅诺莽尉吾齿排队论(脱产)排队论(脱产)77顾客源有限的排队系统顾客源有限的排队系统Pn= m-(n-1)/Pn-1 1 n m反复推得:反复推得:Pn=m!/(m-n)!(/)nP0 1 n m m代入代入Pn=1 n=0mwm!/(m-n)!(/)nP0 =1w n=0mwP0= m!/(m-n)!(/)n-1w n=0盯懂狠熄讶棒磕患垢废稿稗叭亦毫畏霞汞迎涩姨衰梯血翁逞馁辽跋达汐形排队论(脱产)排队论(脱产)78顾客源有限的排队系统顾客源有限的排队系统mPn=m!/(m-
46、n)!(/)nm!/(m-k)!(/)k-1k=0由(m-L)=(1-P0)得L=m-/(1-P0)W=L/eWq=W-1/Lq=Wqewe=(m-L) m mee=nPnnPn= =(m-nm-n) )P Pn n n n=0 =0 n n=0=0 m mm m = =(m Pm Pn n-n Pn Pn n) n n=0 =0 n n=0=0e=(1-P0)书畅诞开搔涉柄漳氰禹焊统异灯半界蚀窥奇周颤邮帚咖歧梗羹钙滨沽剥筹排队论(脱产)排队论(脱产)79w2.M/M/c/m/m系统顾客源有限的排队系统顾客源有限的排队系统0m-112m-2m(m-1)2c2cmCC-1(m(c-1)c顾客源还
47、有m-(c-1)个顾客每个顾客可到达的概率稳态概率方程Pn=(m-n+1)/nPn-1nc(m-n+1)/cPn-1cn m腕愁讫疡泄图窘巩困压沤呸座赞泌扫鹰泰戎淖耘国壶卞施狰讹蝗缴颜脖境排队论(脱产)排队论(脱产)80m代入Pn=1得(整理后)n=0顾客源有限的排队系统顾客源有限的排队系统反复代入得:Pn=m!/n!(m-n)!(/)nP0ncm!/c!(m-n)!cn-c(/)nP0cnmc mwP0=m!/(m-n)!(/)n+m!/(c!(m-n)!wn=0n=c+1wcn-c)(/)n-1蛇谰钱棚乒蒋匙喀植啄蒜预位筒旺逆挨假腻狄譬觉沫介遍润符镍兔平懒蹿排队论(脱产)排队论(脱产)81
48、于是可得:mLq=(n-c)Pnn=c+1e=(m-L)顾客源有限的排队系统顾客源有限的排队系统又L=Lq+e/=Lq+/(m-L)整理得:L=(L+/m)/(1+/)Wq=Lq/e, W=L/e唾单弘哦彼炎舰袍整碟捷纽钠爷讹档足鄂敖母姑戌爹清样旧腐邯波篷张驳排队论(脱产)排队论(脱产)82应应 用用 举举 例例 例6.2:某汽车加油站有两台加油泵为汽车加油,加油站内最多能容纳6辆汽车。已知顾客到达的时间间隔服从负指数分布,平均每小时到达18辆汽车。若加油站中已有K辆车,当K2时,有K/6的顾客将自动离去。加油时间服从负指数分布,平均每辆车需要5分钟。试求:非标准的M/M/2/N模型价亲臆容留
49、听须兆犀级骡帮忙痒芜拣稼列舰页煎准粱还耳岔诧哇辱踌镶谊排队论(脱产)排队论(脱产)83应应 用用 举举 例例 (1)系统空闲的概率为多少? P0 (2)求系统满的概率是多少? P6 (3)求系统服务台不空的概率 P2+P3+P4+P5+P6=1- P0-P1 (4)若服务一个顾客,加油站可以获 得利润10元,问平均每小时可获 得利润为多少元? 10e (5)求每小时损失掉的顾客数? 损=-e (6)加油站平均有多少辆车在等待加 油? Lq 平均有多少个车位被占用? L (7)进入加油站的顾客需要等多长的 时间才能开始加油? Wq 进入加油站的顾 客需要多长时间才能离去? W 求舜救龟含枣题莱巫
50、晤认瓮翼幼驭累页驮权藻毯弃寓憎觉贝榨珐创皆呸掖排队论(脱产)排队论(脱产)84稳态概率关系:P1=/P0=1.5P0=(3/2)P0P2=/(2)P1=0.75*1.5P0=(9/8)P0应应 用用 举举 例例 解:状态转移速度图 以小时为单位=18 =60/5=12222205124632(1-2/6)(1-3/6)(1-4/6)(1-5/6)碳已竹氢摔纯枕硼喳梗按隧败疗吐乏缆管灯中涣孽振都市芍鲤沸铅每莱挚排队论(脱产)排队论(脱产)85应应 用用 举举 例例P3=(4/6)/(2)P2=(1/2)(9/8)P0=(9/16)P0P4=(3/6)/(2)P3=(3/8)(9/16)P0=(2
51、7/128)P0P5=(2/6)/(2)P4=(1/4)(27/128)P0=(27/512)P0P6=(1/6)/(2)P5=(1/8)(27/512)P0=(27/4096)P0由P0+P1+P2+P3+P4+P5+P6=1解得:P0=0.22433 P1 P2 P3 P4 P5 P60.33649 0.25237 0.12618 0.04732 0.01183 0.00148靴宰砌绦揍袜穗野茂投疼烧舵报攒唱砍蝉罩嚏檄氢囱徐房压骆鹊烂里役嚷排队论(脱产)排队论(脱产)86运行指标:(1) P0=0.22433(2) P6=0.00148(3) P忙=1-P0-P1=0.43918(4)e=
52、0P0+P1+2(P2+P3+P4+P5+P6)=14.578(辆/h)10e= 145.78(元/小时)应应 用用 举举 例例绍幌忘滚咙林冰赁苑又巷奢骑弥遏颖诺参咐驳厨严讥锻澡哲亭齐拜怎眠卧排队论(脱产)排队论(脱产)87(5)损=-e =18-14.5782 =3.4218(辆/h)应应 用用 举举 例例(6)Lq=(3-2)P3+(4-2)P4+(5-2)P5+(6-2)P6 =0.26223 L=Lq+e/ =0.26223+1.21485 =1.47708掣鳖寅磷愤抿碍揭省膳指料驶米腊蜕痘骏傲塞铰璃柒向黄刮澳丘杏纷吗盯排队论(脱产)排队论(脱产)88应应 用用 举举 例例(7)Wq=
53、Lq/e =0.018h =1.08分钟 W=Wq+1/ =0.101h =6.08分钟咋虽图目酷操忻怔嫩虎崭漓嗽固叮孟飞迪唉怠遇忱箭彼嵌绸飘翅婶辈播睹排队论(脱产)排队论(脱产)89 例6.3:某车站候车室在某段时间旅客到达服从泊松流分布,平均速度为50人/h,每位旅客在候车室内停留的时间服从负指数分布,平均停留时间为0.5h,问候车室内平均人数为多少?(L)应应 用用 举举 例例解解:把把旅旅客客停停留留在在候候车车室室看看做做服服务务,于是系统为于是系统为M/M/ =50 =1/0.5=2氛滥顾帐没担锭勉年银蛰榨剿熏兵诊豌佃七府卉净唉淖谰嘶抖涝擅遍软勒排队论(脱产)排队论(脱产)90稳态
54、概率关系:Pn=/(n)Pn-1=.=1/n!(/)nP0 记记 =/=50/2 =25 应应 用用 举举 例例0n12n-1n2(n+1)n+13 (n-1)(n+2)状态转移速度图: 郊惶凿叼棋删晦被蘸啼哼室毁荡墒盼胳珍膝殊凤趟谦糊界芽粹监设房区脯排队论(脱产)排队论(脱产)91应应 用用 举举 例例P0=(1/n!n)-1= e- n=0 L=nPn n=1 = e-1/(n-1)!n n=1 =e-1/n!n=25(人人) n=0 代入代入 Pn=1 n=0钒惩叹孽娶湃盏毡蒋音鹊恳暮尝依捶荣喝半孩锅台遏颓孝浊怖柠现质肝被排队论(脱产)排队论(脱产)92 4. 4.排队系统的优化目标排队
55、系统的优化目标 与最优化问题与最优化问题 完完全全消消除除排排队队现现象象是是不不现现实实的的,那那会会造造成成服服务务人人员员和和设设施施的的严严重重浪浪费费,但但是是设设施施的的不不足足和和低低水水平平的的服服务务,又又将将引引起起太太多多的等待,从而导致生产和社会性损失。的等待,从而导致生产和社会性损失。 从从经经济济角角度度考考虑虑,排排队队系系统统的的费费用用应应该该包包含含以以下下两两个个方方面面:一一个个是是服服务务费费用用,它它是是服服务务水水平平的的递递增增函函数数;另另一一个个是是顾顾客客等等待待的的机机会会损损失失( (费费用用) ),它它是是服服务务水水平平的的递减函数
56、递减函数。两者的总和呈一条。两者的总和呈一条U U形曲线形曲线。烬殿哭撤巍搀伎瞪鹤迈贸岸届膳荣蔼畴漳佑氖力找搭熔血竞婆汞嘱秘搬缺排队论(脱产)排队论(脱产)93 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 系系统统最最优优化化的的目目标标是是寻寻求求U U曲曲线线的的最最小小点点。这这种种意意义义下下,排排队队系系统统的的最最优优化化问问题题通通常常分分为为两两类类:一一类类称称之之系系统统的的静静态态最最优优设设计计,目目的的在在于于使使设设备备达达到到最最大大效效益益,或或者者说说,在在保保证证一一定定服服务务质质量量指指标标的的前前题题下下,要要求求机机构构
57、最最为为经经济济;另另一一类类叫叫作作系系统统动动态态最最优优运运营营,是是指指一一个个给给定定排排队队系系统统,如如何何运运营营可可使使某某个个目目标标函函数数得得到到最最优优。归归纳纳起起来来,排排队队系系统统常常见见的优化问题在于:的优化问题在于:苞弦块配长氯合匆发埔瑰你烹例谗羚羚疟暴害戚酚疹犹喧例旦蘸璃渍局拾排队论(脱产)排队论(脱产)94 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 (1) (1)确定最优服务率确定最优服务率 * *; (2) (2)确定最佳服务台数量确定最佳服务台数量s s* *; (3) (3)选择最为合适的服务规则;选择最为合适的服
58、务规则; (4) (4)确定上述几个量的最优组合。确定上述几个量的最优组合。 本本节节仅仅就就 ,s s这这两两个个决决策策变变量量的的分分别别单单独独优优化化,介介绍绍两两个个较较简简单单的的模模型型,以以便便读读者者了了解解排排队队系系统统优优化化设设计计的的基基本本思想。思想。茹孜著茅涡重琵箱扎帆乃攘泄望催她驻斩夷抿戮港戳褪还饲坑莎驰虽芬知排队论(脱产)排队论(脱产)95 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题一一、MM1 系系统统的的最最优优平平均均服服务务率率 * : 设设C1当当 =1时时服服务务系系统统单单位位时时间间的的平平均均费用费用Cw平平
59、均均每每个个顾顾客客在在系系统统逗逗留留单单位位时时间的损失;间的损失;y整个系统单位时间的平均总费用。整个系统单位时间的平均总费用。其中其中C1,Cw均为可知。则目标函数为均为可知。则目标函数为 (6-52)旋刃闭乙戮蚀哈雇偶蜀缀人筷刀岁所将挟投挎刊支邮冤康孵勋匆刊垂儡燕排队论(脱产)排队论(脱产)96 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题将将L= ( - ),代入上式,得,代入上式,得易见易见y是关于决策变量是关于决策变量 的一元非线性函数的一元非线性函数由一阶条件由一阶条件解得驻点解得驻点 (6-53) (6-53)摄椰法徒赠骂接迄谣淹顷车谆巫喘肩蓟帘
60、旗跃敏遵杉凤前烂忻绸容刁集烽排队论(脱产)排队论(脱产)97 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 根根号号前前取取正正号号是是为为了了保保证证 。这这样样,系系统统才才能能达达到到稳稳态态。又又由由二阶条件二阶条件 (因因 )可可知知(6-53)给给出出的的 *为为( ,)上上的的全全局局唯唯一一最最小小点点。将将 *代代入入 (6-52)中中,可可得得最最小小总平均费用总平均费用(6-54)蠕磨茨睛笛走喜氢带柞旺怔分器摔翱潭击袭偷狭菇磕彩采吓斗边显延兴开排队论(脱产)排队论(脱产)98 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化
61、问题 另另外外,若若设设cw为为平平均均每每个个顾顾客客在在队队列列中中等待单位时间的损失,则需用等待单位时间的损失,则需用取取代代式式(6-52)中中的的L,这这时时类类似似可可得得一一阶阶条件:条件: 这这是是一一个个关关于于 的的四四次次方方程程,一一般般采采用数值法用数值法(如牛顿法如牛顿法)确定其根确定其根 *。倪罢愚扎疯的梯穷默腋黑堤奋陡怀苛汁香啃湃蓬非侈窄郑便黔氧挠抗霓漱排队论(脱产)排队论(脱产)99 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题二、二、M /M /s / 系统的最优服务台数系统的最优服务台数 s*设目标函数为设目标函数为 (6-55
62、)其中:其中: s 并联服务台的个数并联服务台的个数(待定待定); f (s) 整整个个系系统统单单位位时时间间的的平平均均总总费费用,它是关于服务台数用,它是关于服务台数 s 的函数;的函数; c2平均每个服务台的单位时间费用;平均每个服务台的单位时间费用;眷镭殷窿粕躺梨疽刷缓垛皖货凤导则洞奔沽哗扦蛋狼秒恶莆颗朽操机粟一排队论(脱产)排队论(脱产)100cw平平均均每每个个顾顾客客在在系系统统中中逗逗留留(或或等等待待)单位时间的损失;单位时间的损失;L(s)平平均均队队长长(或或平平均均等等待待队队长长),它它是关于服务台数是关于服务台数 s 的函数;的函数; 要要确确定定最最优优服服务务
63、台台数数 s*1,2,使,使 由由于于s取取值值离离散散,不不能能采采用用微微分分法法或或非非线线性性规规划划的的方方法法,因因此此我我们们采采用用差差分分法法。显然有显然有 (6-56)鸟捍栓涣筒谁曝吏榔屎蜕瞄棵馆笨傈佛芍岛畅拼统提刺啡沤肇譬鞠锌演既排队论(脱产)排队论(脱产)101 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题把式(把式(6-55)代人式)代人式(6-56) 中,得中,得可得可得令令 (6-57) 依依次次计计算算 s =1,2,时时的的L(s)值值及及每每一一差差值值 L(s) - L(s+1) ,根根据据 落落在在哪哪两两个个差值之间就可确定
64、差值之间就可确定 s*。箱咒震彤恢萄私测洪淋溪必辉杠陵瑚钥例推牧势懊婴捆连钵膏舍嗣疗色搜排队论(脱产)排队论(脱产)102例例6.4: 兴兴建建一一座座港港口口码码头头,只只有有一一个个装装卸卸船船只只的的泊泊位位。要要求求设设计计装装卸卸能能力力。装装卸卸能能力力单单位位为为(只只/日日)船船数数。已已知知:单单位位装装卸卸能能力力的的平平均均生生产产费费用用a=2千千元元,船船只只逗逗留留每每日日损损失失b=1.5千千元元。船船只只到到达达服服从从泊泊松松分分布布,平平均均速速率率=3只只/日日。船船只只装装卸卸时时间间服服从从负负指指数分布。目标是每日总支出最少。数分布。目标是每日总支出
65、最少。应应 用用 举举 例例撑卡篱榴镶弧态聘露斩贤彻渗别吮吩捶龋彰谰灰为吮战铡吻派蹿画廖拓钝排队论(脱产)排队论(脱产)103解:解:=3 , 待定待定 模型模型 M/M/1/队长队长 Ls =/(-)总费用总费用 C = a+bLs= a+b/(-) 求极值(最小值)求极值(最小值)求导求导 d C / d = a + (-b)/(-)2 = 0应应 用用 举举 例例得得: -= (b/a)1/2(根据题意舍负)(根据题意舍负)所以所以=+(b/a)1/2=3+(2.25)1/2=4.5(只只/日日)苗油挠缉汹止恕翘颁葬岭搬础挽睁漆警萨凰衅宿趋民约泣茫送枫痛拘醒饿排队论(脱产)排队论(脱产)
66、104例例6.4: 建建造造一一口口码码头头,要要求求设设计计装装卸卸船船只只的的泊泊位位数数。已已知知:预预计计到到达达=3只只/天天,泊泊松松流流;装装卸卸=2只只/天天,负负指指数数分分布布。装装卸卸费费每每泊泊位位每每天天a=2千千元元,停停留留损损失失费费b=1.5千千元元/日日。目目标是总费用最少。标是总费用最少。应应 用用 举举 例例解解:模型模型 M/M/c/ c 待定待定总费用:总费用:F = a c + b Ls(c) c 是离散变量,无法用求导来解。是离散变量,无法用求导来解。惫釉哭对孕伴俯负呈果猎棒瞩法辰劝绵拥置吁哮幢氯妮癌缆撼梦骸切漏论排队论(脱产)排队论(脱产)10
67、5应应 用用 举举 例例考虑考虑: M/M/c/ 要求要求: =/(c) (/)=1.5讨论讨论 c=2,3,4c-1P0=cn/nn+cc/c!c/(1-)-1n=0Lq=ccc+1/c!(1-)2P0L=Lq+/燥河庚煎屏断溜涝空尝痈咏菲蛀吓零梦很迭立相续饼比扦歹笆瓦拯巾傲职排队论(脱产)排队论(脱产)106应应 用用 举举 例例 结结论论:c =3 即即设设计计三三个个装装卸卸泊泊位位可可使使每天的总费用最少为每天的总费用最少为8.60526千元。千元。=1/2 =3/4=3/8犹胞齐廊郸沟聋淮驹挎徽摔钨税哨兹蛙敝支央舍晰秆庚谁峦执永锡耕撤涎排队论(脱产)排队论(脱产)107 4.4.排
68、队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题例例6.6: 某某市市政政府府的的上上访访接接待待室室每每天天平平均均接接待待来来访访48次次,来来访访者者为为泊泊松松流流,上上访访所所造造成成的的损损失失为为平平均均每每次次20元元。该该室室每每设设置置一一名名接接待待员员的的服服务务成成本本为为平平均均每每天天8元元,接接待待时时间间为为指指数数分分布布,平平均均每每天天可可接接待待25次次。问问应应设设置置几几名名接待员能使平均总费用为最小接待员能使平均总费用为最小?解解: 此为此为 MMs系统,有系统,有奸嚷莹烛邯峙崔烁诞缚滩潭隋幻脂陶宋鲍隶堵冻歇谈扦时盒阅挟材拾县迎排队论
69、(脱产)排队论(脱产)108 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 c28元人天,元人天, cw20元天次,元天次, 48次天,次天, 25次天,次天, 则按式则按式(6-57)得得 0.4另有另有科僳茸些逐兑聚氖倒穗掖示琐拨俊侵秽叹汽俩景纽富紊业把营徊湍浙蔫帖排队论(脱产)排队论(脱产)109 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题把把 代入式代入式(6-15),得,得又由式又由式(6-17)、式、式(6-18) 得得把把 , P0代入上式整理可得代入上式整理可得贺糕猿硬奄菱守雌弟繁拽顺恳票颁瀑伦羡波倪硷始首寞河启朴殖裕荒茹冬
70、排队论(脱产)排队论(脱产)110 4.4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题 当当S=1时时, = =1.921,不不满满足足系系统达到稳态的条件统达到稳态的条件 1,故这时,故这时L(1)=。依依次次计计算算当当s2,3,时时的的值值及及其其差差值值L(s)-L(s+1) ,如表,如表6-3所示。所示。由表由表6-3可知:可知: S*4(人人)憋供贤溅匆旬颗捻叭酝夺摈荣蹋袭壁试吼饺倦费膝祟弦奈境嗅至锌貌尉畸排队论(脱产)排队论(脱产)111 据据此此(s*=4)可可得得最最小小总总平平均均费费用:用: (元天元天) 故故该该室室应应设设置置4名名接接待待员员可可
71、使使每每天天总总平平均均费费用用达达到到最最小小,为为73.26元。元。 s2,3,时的时的L(s)值及其差值及其差值值L(s)-L(s+1)如下面表如下面表6-3 4. 4.排队系统的优化目标排队系统的优化目标 与最优化问题与最优化问题梅灭掂秘搏卉育龟谐慕橡悬泅雹瞻濒诡扑晋匡伴滇览另炽恐宵奋列旱商术排队论(脱产)排队论(脱产)112作业:作业:P3231, 3, 5s12345L(s)24.4902.6452.0631.952L(s)-L(s+1)21.8450.5820.111表表6 63 3忠亚激势伸材确馈崇渣卯恤又积聪掠勘齿尊奇货吟霉恋冕尸濒薯贴溺袜划排队论(脱产)排队论(脱产)113