《运筹学排队论》由会员分享，可在线阅读，更多相关《运筹学排队论（53页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学管理运筹学 排队论排队论 第十章 排队论2第十章 排队论10.1概述排队论（Queing Theory）也称随机服务系统。任何一个服务系统均由客体和主体组成。前者是要求服务的对象，我们一律称之为“顾客”；后者是提供服务的机构或人员，一律称之为“服务员”。顾客可泛指机器、病人、飞机、轮船等，服务员可泛指机修工、医生、码头等。3第十章 排队论.服服务务系系统统顾客顾客:机器、飞机、轮船、病人机器、飞机、轮船、病人顾客到达顾客到达等待服务等待服务接受服务接受服务顾客离去顾客离去服务员：机修工、码头设备、医生服务员：机修工、码头设备、医生到达时间到达时间服务时间服务时间 系统空闲系统空闲到达
2、时间到达时间=服务时间服务时间 充分利用充分利用,无排队无排队到达时间到达时间服务时间服务时间 排队越来越长排队越来越长4第十章 排队论问题是: 到达间隔、服务时间均为随机变量，这也是随机服务系统的基本特征。所以难以确定系统状态，只能求期望值。我们希望借助随机服务系统理论来揭示这些规律。5第十章 排队论 例：某港口装卸台负责货轮装卸工作，货轮即顾客以某固定周期间隔到达港口，比如每隔a=6小时到达一艘，而装卸台卸货需要一段时间，假定它对每艘货轮的服务时间也是定长的，比如每艘需卸时间为s=4小时。这一服务系统的特征是到达和服务时间均是确定不变的定长。结论：如果sa，则形成等待卸货队伍，且队长不断增
3、加。6第十章 排队论.如果货轮到达时间间隔是随机变量如果货轮到达时间间隔是随机变量,码头卸货时间也为随码头卸货时间也为随机变量机变量,则构成一个随机服务系统。即便货轮到达时间间则构成一个随机服务系统。即便货轮到达时间间隔的平均时间还为隔的平均时间还为6小时，但每一个间隔时间小时，但每一个间隔时间Xi（i=1、2）并不都是）并不都是6小时，只是指：小时，只是指：同理，平均服务时间为同理，平均服务时间为4小时，从而会产生排队或服务空小时，从而会产生排队或服务空闲时间。但事先无法确定。闲时间。但事先无法确定。7第十章 排队论对于随机服务系统希望知道：1、在系统中平均队长L从长远来看，平均等待服务加上
4、正接受服务的货轮期望数；2、在队中平均队长Lq从长远来看，平均等待服务的货轮期望数；3、系统中平均逗留时间 从长远看，任一进入系统货轮用于等待服务加上接受服务的期望时间；4、在队中平均等待时间 从长远看，任一进入系统货轮用于等待服务的期望时间。8第十章 排队论一、服务系统的结构假如将要求服务的对象统称为“顾客”，进行服务的统称为“服务机构”或“服务员”，一个排队系统就能抽象地描述为：为了获得某种服务而到达的顾客，若不能立即获得服务，而又允许排队等待，则加入等待队伍，获得服务之后离开系统。作为服务系统基本上由三个部分组成：9第十章 排队论1、输入过程 刻划顾客按怎样的规律到达服务系统，主要有以下
5、几方面：1）顾客总体（顾客源）数可能是有限的（例厂内故障设备数）也可能是无限的（到达售票窗口前的顾客总体）；2）顾客可能是单个到达，也可能是成批到达；3）顾客相继到达的间隔时间分布可以是确定型，也可以是随机型；4）顾客的到达可以是相互独立的，即以前的到达情况对以后顾客的到来没有影响；10第十章 排队论5）输入过程可以是平稳的（指描述相继到达的间隔时间分布和所含参数（如 ）都与时间无关，否则称为非平稳的；6）具有不耐烦顾客的输入a）弃长队而去b）排队太久而去c）转队11第十章 排队论2、排队规则（到达的顾客按什么样的规则接受服务）1）损失制 即服务台一旦占用，顾客随即离去；2）等待制 顾客到达后
6、须等待服务，服务次序为：a）先到先服务b）后到先服务c）随机服务d）有优先权的服务3）混合制（损失制与等待制的混合）a）队长有限制的情形队长k，离去12第十章 排队论b）等待（或逗留）时间有限制的情形排队时间t0,离去;反之排下去4)从队伍的数目看,可以是单列,也可以是多列a)顾客可转移;b)顾客不可转移;13第十章 排队论3、服务机构1）服务员的数目串列、并列、串并混合2）服务方式对单个顾客服务或对成批顾客服务3）服务时间分确定型和随机型服务时间14第十章 排队论二、表示排队模型的符号D.G.Kendall 于1953 年提出排队符号: (i/j/c)i:到达过程的分布;j:服务过程分布;c
7、:服务员数到了1971年进一步定为：(到达分布到达分布/服务分布服务分布/服务员数服务员数/系统容量系统容量/顾客源顾客源/排队规则排队规则)(M/M/1/FCFS)常规表示法为常规表示法为(M/M/1)15第十章 排队论三、排队模型中常用参数：到达速度（单位时间到达顾客数）；：服务速度（单位时间服务完成数）；1/ ：相继顾客到达的平均间隔时间；1/ ：一个顾客的平均服务时间；=（1/ ：1/ ）= / 称为服务强度，指相同时间区间内顾客到达的平均数与能被服务完的平均顾客数之比；16第十章 排队论四、系统的稳态性态1、 j稳态概率j定义为稳态系统中有j个顾客（包括正在服务的）的概率。 0=1-
8、 称为系统空闲的概率称为系统空闲的概率17第十章 排队论2、3、4、5、18第十章 排队论6、7、进入系统的顾客逗留时间超过进入系统的顾客逗留时间超过t的概率。的概率。进入系统的顾客等待时间超过进入系统的顾客等待时间超过t的概率。的概率。19第十章 排队论五、稳态性态中各量值的分析1、 =/ 的意义1）平均到达速度与平均服务速度之比；2）服务员利用率=1- 03）一个平均服务时间内到达的顾客平均数20第十章 排队论4）正在接受服务的顾客平均数=00+1（1- 0）2、L与Lq的关系表示系统中平均人数等于队中平均人数加上正在接表示系统中平均人数等于队中平均人数加上正在接受服务顾客平均人数。受服务
9、顾客平均人数。21第十章 排队论3、系统逗留时间减排队时间恰为服务时间的期望值。系统逗留时间减排队时间恰为服务时间的期望值。22第十章 排队论4、23第十章 排队论5、24第十章 排队论10.2 M/M/1模型实例例1、某厂有几千名工人，医务室平均每小时约有4位工人来看病，医生每小时平均诊断约5个病人，若到达时间间隔服从普阿松（Pisson）分布，服务时间服从负指数分布，试分析该系统。解：本例属标准(M/M/1/FCFS)问题，已知=4人/小时； =5 人/小时， =/ =4/5=0.8系统队长L= /(1- )=0.8/(1-0.8)=4人; 平均4人排队和看病队长Lq= 2/(1- )=0
10、.82/(1-0.8)=3.2人;平均有3.2人在排队或 Lq= L- =4-0.8=3.2人25第十章 排队论工人在医务室平均逗留时间：工人在医务室平均逗留时间：病人平均在医务室内排队和看病时间约为病人平均在医务室内排队和看病时间约为1小时。小时。工人在医务室平均排队时间：工人在医务室平均排队时间：病人平均在医务室内排队时间约为病人平均在医务室内排队时间约为0.8小时。小时。26第十章 排队论系统空闲概率0=1- =1-0.8=0.2系统忙的概率1- 0= =0.8以该厂每天工作8小时计,则每天平均来看病的人数为:L总=8 =84=32人/天;全体病人每天平均等待看病所化时间为:W总=病人逗
11、留时间和排队超过病人逗留时间和排队超过1小时的概率分别为：小时的概率分别为：27第十章 排队论若要计算系统中大于10个病人的概率,则:n10= 11=0.811=0.086即医务室中大于10个病人的概率仅为8.6%医务室中病员大于医务室中病员大于K的概率的概率28第十章 排队论例2、某电机修理车间，每天平均有2台电机到达修理。负责修理的是1名修理工，平均每3小时修完1台。若到达为泊松分布，修理时间为负指数分布，求1台电机从到达到修理完毕的平均时间及修理工人每天的平均空闲时间（每天以8小时计）解：本问题属(M/M/1/FCFS)模式到达速度=2台/8小时=1/4 台/小时服务速度=1台/3小时=1/3 台/小时= / =1/4/1/3=3/40.5=e- (1- )t=e-4(1-0.5)0.5=0.367850第十章 排队论若是租赁场地，则新系统变为：M/M/1/3/FCFS模型此时顾客流失率为：加油站每周将增加服务车辆数为：加油站每周将增加服务车辆数为：51第十章 排队论每周将增加收入为：50元/辆18.38辆/周=919元1000元/周由于增加的收入不足以支付每周的场地租赁费,所以租赁空地不经济。5253
