管理运筹学排队论.ppt

运筹学,上海应用技术学院经管学院,1,第十章 排队论,2,第十章 排队论,10.1概述排队论（Queing Theory）也称随机服务系统。任何一个服务系统均由客体和主体组成。前者是要求服务的对象，我们一律称之为“顾客”；后者是提供服务的机构或人员，一律称之为“服务员”。顾客可泛指机器、病人、飞机、轮船等，服务员可泛指机修工、医生、码头等。,3,第十章 排队论,.,服务系统,顾客:机器、飞机、轮船、病人,顾客到达等待服务接受服务顾客离去,服务员：机修工、码头设备、医生,到达时间服务时间 系统空闲,到达时间=服务时间 充分利用,无排队,到达时间服务时间 排队越来越长,4,第十章 排队论,问题是:到达间隔、服务时间均为随机变量，这也是随机服务系统的基本特征。所以难以确定系统状态，只能求期望值。我们希望借助随机服务系统理论来揭示这些规律。,5,第十章 排队论,例：某港口装卸台负责货轮装卸工作，货轮即顾客以某固定周期间隔到达港口，比如每隔a=6小时到达一艘，而装卸台卸货需要一段时间，假定它对每艘货轮的服务时间也是定长的，比如每艘需卸时间为s=4小时。这一服务系统的特征是到达和服务时间均是确定不变的定长。结论：如果sa，则形成等待卸货队伍，且队长不断增加。,6,第十章 排队论,.如果货轮到达时间间隔是随机变量,码头卸货时间也为随机变量,则构成一个随机服务系统。即便货轮到达时间间隔的平均时间还为6小时，但每一个间隔时间Xi（i=1、2）并不都是6小时，只是指：同理，平均服务时间为4小时，从而会产生排队或服务空闲时间。但事先无法确定。,7,第十章 排队论,对于随机服务系统希望知道：1、在系统中平均队长L从长远来看，平均等待服务加上正接受服务的货轮期望数；2、在队中平均队长Lq从长远来看，平均等待服务的货轮期望数；3、系统中平均逗留时间 从长远看，任一进入系统货轮用于等待服务加上接受服务的期望时间；4、在队中平均等待时间 从长远看，任一进入系统货轮用于等待服务的期望时间。,8,第十章 排队论,一、服务系统的结构假如将要求服务的对象统称为“顾客”，进行服务的统称为“服务机构”或“服务员”，一个排队系统就能抽象地描述为：为了获得某种服务而到达的顾客，若不能立即获得服务，而又允许排队等待，则加入等待队伍，获得服务之后离开系统。作为服务系统基本上由三个部分组成：,9,第十章 排队论,1、输入过程 刻划顾客按怎样的规律到达服务系统，主要有以下几方面：1）顾客总体（顾客源）数可能是有限的（例厂内故障设备数）也可能是无限的（到达售票窗口前的顾客总体）；2）顾客可能是单个到达，也可能是成批到达；3）顾客相继到达的间隔时间分布可以是确定型，也可以是随机型；4）顾客的到达可以是相互独立的，即以前的到达情况对以后顾客的到来没有影响；,10,第十章 排队论,5）输入过程可以是平稳的（指描述相继到达的间隔时间分布和所含参数（如）都与时间无关，否则称为非平稳的；6）具有不耐烦顾客的输入a）弃长队而去b）排队太久而去c）转队,11,第十章 排队论,2、排队规则（到达的顾客按什么样的规则接受服务）1）损失制 即服务台一旦占用，顾客随即离去；2）等待制 顾客到达后须等待服务，服务次序为：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:服务员数到了1971年进一步定为：,(到达分布/服务分布/服务员数/系统容量/顾客源/排队规则),(M/M/1/FCFS),常规表示法为(M/M/1),15,第十章 排队论,三、排队模型中常用参数：到达速度（单位时间到达顾客数）；：服务速度（单位时间服务完成数）；1/：相继顾客到达的平均间隔时间；1/：一个顾客的平均服务时间；=（1/：1/）=/称为服务强度，指相同时间区间内顾客到达的平均数与能被服务完的平均顾客数之比；,16,第十章 排队论,四、系统的稳态性态1、j稳态概率j定义为稳态系统中有j个顾客（包括正在服务的）的概率。,0=1-称为系统空闲的概率,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的关系,表示系统中平均人数等于队中平均人数加上正在接受服务顾客平均人数。,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.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总=,病人逗留时间和排队超过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/41,29,第十章 排队论,一台电机从到达到修理完毕的平均时间为：,一台电机排队的平均时间为：,30,第十章 排队论,服务员空闲概率0=1-=1-3/4=1/4每天空闲时间=1/48=2小时/天系统中平均人数L=/(1-)=3/4/1/4)=3人系统中平均队长Lq=2/(1-)=3/42/1/4=9/4人,31,第十章 排队论,例3、某装卸台装卸设备的设计方案中，有三个方案可供选择，有关费用见下表：,32,第十章 排队论,设货车按Poisson流到达，平均每天（按10小时计算）到达15车，每车平均装货500袋，卸装时间遵从负指数分布，每辆车停留一小时的损失费为10元，问该选择哪个方案？,解：本系同属M/M/1模型,平均到达率=15/10=1.5车/小时,服务率1=(1000袋/小时)/(500袋/车)=2车/小时,或=1.5500=750袋/小时;1=(1000袋/小时),33,第十章 排队论,34,第十章 排队论,.,一辆车在系统中的平均停留时间为:,35,第十章 排队论,因此,每天货车在系统里逗留时间的平均损失费为:,36,第十章 排队论,服务强度：,每天实际可变费用：,37,第十章 排队论,.,各方案总费用:,结论:应选方案2。,38,第十章 排队论,10.3容量有限的M/M/1/K/FCFS模型,本模型与前相比为系统容量有限。,若在某一时刻有一顾客到达时，如系统中已有K个顾客，,那个顾客就被拒绝进入系统,当系统已满（N=K），则到达率=0，所以有必要找出,有效的到达率e,e=（1-Pk）,39,第十章 排队论,系统的状态概率：,40,第十章 排队论,41,第十章 排队论,例4、某美容院有6个椅子接待顾客等待理发。当6个椅子都坐满时，后到的顾客就被拒绝。顾客到达时间服从负指数分布，平均到达率为3人/小时，每人的理发时间也服从负指数分布，平均需要5分钟。试分析这一系统。解（k=7 6人排队，1人接受服务）,这是M/M/1/7/FCFS系统，=3人/小时，=4人/小时,1、求某顾客一到美容院就理发的概率，即求系统空闲概率,42,第十章 排队论,.,2、求系统逗留顾客人数及排队人数,43,第十章 排队论,.,3、求有效到达率,4、求每一顾客在美容院内逗留时间的期望值,5、求每一顾客在美容院排队时间的期望值,44,第十章 排队论,.,6、求系统客满时顾客流失率,45,第十章 排队论,例5、某汽车加油车站只有一台加油泵，且场地最多只能容纳三辆车，当站内场地占满时，到达的汽车只能去别处加油。汽车到达间隔时间服从普阿松分布，其中均值为每8分钟一辆。服务时间间隔服从负指数分布，其平均值为4分钟一辆。加油站有机会租赁毗邻的一块空地，以供多停放一辆前来加油的车（无加油泵），租地费用为每周1000元，每周从每个顾客那里期望净收益是50元，这个站每天开放10小时，问租赁空地是否有利？,46,第十章 排队论,.,解:本系统属M/M/1/3/FCFS模型,已知:=60/8=7.5辆/小时;=60/4=15辆/小时,=/=7.5/15=0.5,1、系统空闲概率,47,第十章 排队论,.,2、求系统逗留顾客人数及排队人数,3、求有效到达率,48,第十章 排队论,4、求每一辆车在加油站内逗留时间的期望值,5、求每一辆车在加油站内排队时间的期望值,49,第十章 排队论,6、求系统客满时车辆流失率,7.逗留时间超过半小时的概率,PW S0.5=e-(1-)t=e-4(1-0.5)0.5=0.3678,50,第十章 排队论,若是租赁场地，则新系统变为：M/M/1/3/FCFS模型此时顾客流失率为：,加油站每周将增加服务车辆数为：,51,第十章 排队论,每周将增加收入为：50元/辆18.38辆/周=919元1000元/周由于增加的收入不足以支付每周的场地租赁费,所以租赁空地不经济。,52,53,