管理运筹学第十章排队论

上海应用技术学院经济与管理学院运筹学上海应用技术学院经管学院龚有容Email：[e-mail]电话：62088001上海应用技术学院经济与管理学院第十章排队论上海应用技术学院经济与管理学院第十章排队论•§10.1概述•排队论（QueingTheory）也称随机服务•系统。任何一个服务系统均由客体和主•体组成。前者是要求服务的对象，我们•一律称之为“顾客”；后者是提供服务的•机构或人员，一律称之为“服务员”。顾•客可泛指机器、病人、飞机、轮船等，•服务员可泛指机修工、医生、码头等。上海应用技术学院经济与管理学院第十章排队论•.服务系统顾客:机器、飞机、轮船、病人……顾客到达——等待服务——接受服务——顾客离去服务员：机修工、码头设备、医生……到达时间服务时间系统空闲到达时间=服务时间充分利用,无排队到达时间服务时间排队越来越长上海应用技术学院经济与管理学院第十章排队论问题是:到达间隔、服务时间均为随机变量，这也是随机服务系统的基本特征。所以难以确定系统状态，只能求期望值。我们希望借助随机服务系统理论来揭示这些规律。上海应用技术学院经济与管理学院第十章排队论例：某港口装卸台负责货轮装卸工作，货轮即顾客以某固定周期间隔到达港口，比如每隔a=6小时到达一艘，而装卸台卸货需要一段时间，假定它对每艘货轮的服务时间也是定长的，比如每艘需卸时间为s=4小时。这一服务系统的特征是到达和服务时间均是确定不变的定长。结论：如果sa,则服务员的空闲时间为总时间的倍；如果s=a，则服务员得到充分利用，且无货轮等待；如果sa，则形成等待卸货队伍，且队长不断增加。asa上海应用技术学院经济与管理学院第十章排队论.如果货轮到达时间间隔是随机变量,码头卸货时间也为随机变量,则构成一个随机服务系统。即便货轮到达时间间隔的平均时间还为6小时，但每一个间隔时间Xi（i=1、2……）并不都是6小时，只是指：同理，平均服务时间为4小时，从而会产生排队或服务空闲时间。但事先无法确定。小时6/1nxnii上海应用技术学院经济与管理学院第十章排队论对于随机服务系统希望知道：1、在系统中平均队长L——从长远来看，平均等待服务加上正接受服务的货轮期望数；2、在队中平均队长Lq——从长远来看，平均等待服务的货轮期望数；3、系统中平均逗留时间——从长远看，任一进入系统货轮用于等待服务加上接受服务的期望时间；4、在队中平均等待时间——从长远看，任一进入系统货轮用于等待服务的期望时间。WqW上海应用技术学院经济与管理学院第十章排队论•一、服务系统的结构•假如将要求服务的对象统称为“顾客”，•进行服务的统称为“服务机构”或“服务员”，一•个排队系统就能抽象地描述为：•为了获得某种服务而到达的顾客，若不能立即•获得服务，而又允许排队等待，则加入等待队•伍，获得服务之后离开系统。•作为服务系统基本上由三个部分组成：上海应用技术学院经济与管理学院第十章排队论•1、输入过程刻划顾客按怎样的规律到达服务系统，主要有以下几方面：•1）顾客总体（顾客源）数可能是有限的（例厂内故障设备数）也可能是无限的（到达售票窗口前的顾客总体）；•2）顾客可能是单个到达，也可能是成批到达；•3）顾客相继到达的间隔时间分布可以是确定型，也可以是随机型；•4）顾客的到达可以是相互独立的，即以前的到达情况对以后顾客的到来没有影响；上海应用技术学院经济与管理学院第十章排队论•5）输入过程可以是平稳的（指描述相继到达的•间隔时间分布和所含参数（如）•都与时间无关，否则称为非平稳的；•6）具有不耐烦顾客的输入•a）弃长队而去•b）排队太久而去•c）转队等和2x上海应用技术学院经济与管理学院第十章排队论•2、排队规则（到达的顾客按什么样的规则接受服务）•1）损失制即服务台一旦占用，顾客随即离去；•2）等待制顾客到达后须等待服务，服务次序为：•a）先到先服务•b）后到先服务•c）随机服务•d）有优先权的服务•3）混合制（损失制与等待制的混合）•a）队长有限制的情形•队长k，排队;队长k，离去上海应用技术学院经济与管理学院第十章排队论•b）等待（或逗留）时间有限制的情形•排队时间t0,离去;反之排下去•4)从队伍的数目看,可以是单列,也可以是多列•a)顾客可转移;•b)顾客不可转移;上海应用技术学院经济与管理学院第十章排队论•3、服务机构•1）服务员的数目•串列、并列、串并混合•2）服务方式•对单个顾客服务或对成批顾客服务•3）服务时间•分确定型和随机型服务时间上海应用技术学院经济与管理学院第十章排队论•二、表示排队模型的符号•D.G.Kendall于1953年提出排队符号:(i/j/c)•i:到达过程的分布;j:服务过程分布;c:服务员数•到了1971年进一步定为：(到达分布/服务分布/服务员数/系统容量/顾客源/排队规则)(M/M/1/∞/∞/FCFS)常规表示法为(M/M/1)上海应用技术学院经济与管理学院第十章排队论•三、排队模型中常用参数•：到达速度（单位时间到达顾客数）；•：服务速度（单位时间服务完成数）；•1/：相继顾客到达的平均间隔时间；•1/：一个顾客的平均服务时间；•=（1/：1/）=/称为服务强度，指相同时•间区间内顾客到达的平均数与能被服务完的平均顾•客数之比；上海应用技术学院经济与管理学院第十章排队论•四、系统的稳态性态•1、j——稳态概率•j定义为稳态系统中有j个顾客（包括正在服务的）•的概率。00jjj0=1-——称为系统空闲的概率上海应用技术学院经济与管理学院第十章排队论•2、•3、•4、•5、（系统人数）10jjjL（排队人数））（1211jjqjL（逗留时间））（111W（等待时间））（1qW上海应用技术学院经济与管理学院第十章排队论•6、•7、tse）（　　1t}{w•te）（　　1qt}P{w•进入系统的顾客逗留时间超过t的概率。进入系统的顾客等待时间超过t的概率。上海应用技术学院经济与管理学院第十章排队论•五、稳态性态中各量值的分析•1、=/的意义•1）平均到达速度与平均服务速度之比；•2）服务员利用率•=1-0•3）一个平均服务时间内到达的顾客平均数1上海应用技术学院经济与管理学院第十章排队论•4）正在接受服务的顾客平均数•=0×0+1×（1-0）•2、L与Lq的关系qqLLLL即）（11112•表示系统中平均人数等于队中平均人数加上正在接•受服务顾客平均人数。上海应用技术学院经济与管理学院第十章排队论•3、的关系与qWW1111）（）（qWW1qWW•系统逗留时间减排队时间恰为服务时间的期望值。上海应用技术学院经济与管理学院第十章排队论•4、WL）（11/1WL上海应用技术学院经济与管理学院第十章排队论•5、qqWL）（1/12qqWL上海应用技术学院经济与管理学院第十章排队论•§10.2M/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人上海应用技术学院经济与管理学院第十章排队论小时14511W小时8.0458.0qW•工人在医务室平均逗留时间：•病人平均在医务室内排队和看病时间约为1小时。•工人在医务室平均排队时间：•病人平均在医务室内排队时间约为0.8小时。上海应用技术学院经济与管理学院第十章排队论•系统空闲概率0=1-=1-0.8=0.2•系统忙的概率1-0==0.8•以该厂每天工作8小时计,则每天平均来看病的人数为:•L总=8=8×4=32人/天;•全体病人每天平均等待看病所化时间为:•W总=小时3213232W3679.0)11)8.01(5)1(eeWPt（•病人逗留时间和排队超过1小时的概率分别为：29424.08.0)11)8.01(5)1(eeWPtq（上海应用技术学院经济与管理学院第十章排队论•若要计算系统中大于10个病人的概率,则:•n10=11=0.811=0.086•即医务室中大于10个病人的概率仅为8.6%101111)1(1)1(11kkjkjkjjkn•医务室中病员大于K的概率上海应用技术学院经济与管理学院第十章排队论例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上海应用技术学院经济与管理学院第十章排队论小时124/13/111W一台电机从到达到修理完毕的平均时间为：一台电机排队的平均时间为：小时94/13/14/3qW上海应用技术学院经济与管理学院第十章排队论•服务员空闲概率0=1-=1-3/4=1/4•每天空闲时间=1/4×8=2小时/天•系统中平均人数L=/(1-)=3/4/1/4)=3人•系统中平均队长Lq=2/(1-)=3/42/1/4=9/4人上海应用技术学院经济与管理学院第十章排队论•例3、某装卸台装卸设备的设计方案中，有三个•方案可供选择，有关费用见下表：方案每天固定费用Fi（元）每天可变操作费Vi（元）每小时装卸率μi（袋）16010010002130150200032502006000上海应用技术学院经济与管理学院第十章排队论设货车按Poisson流到达，平均每天（按10小时计算）到达15车，每车平均装货500袋，卸装时间遵从负指数分布，每辆车停留一小时的损失费为10元，问该选择哪个方案？解：本系同属M/M/1模型平均到达率=15/10=1.5车/小时服务率1=(1000袋/小时)/(500袋/车)=2车/小时或=1.5×500=750袋/小时;1=(1000袋/小时)上海应用技术学院经济与管理学院第十章排队论车小时车袋小时袋小时；车车袋小时袋12/500/6000/4/500/200032上海应用技术学院经济与管理学院第十章排队论.一辆车在系统中的平均停留时间为:)(095.05.11211)(4.05.1411);(25.1211332211小时小时小时上海应用技术学院经济与管理学院第十章排队论因此,每天货车在系统里逗留时间的平均损失费为:天车小时元车小时/15/10/1天元　　　　：方案/30015102;5.121111;/6015104.0,4.05.141122天元：方案天元方案/25.141510095.0,095.05.11211:3上海应用技术学院经济与管理学院第十章排队论•服务强度：125.0125.1;375.045.1;75.025.1332211每天实际可变费用：.25125.0200;25.5