第6章 排队系统分析

第6章排队系统分析（QueueingSystemsAnalysis）第一节排队的基本概念第二节到达与服务的规律第三节M/M/1排队模型第四节M/M/C排队模型第五节M/G/1排队模型第六节排队系统优化按维基百科(Wikipedia)的定义：传统的排队论以复杂的计算来确定等候时间、服务时间、服务员（台）的使用情况和其它衡量标准，用于测算排队效果。AsWikipediadefinesit,classicQueuingTheoryinvolvescomplexcalculationstodeterminewaitingtime,servicetime,serverutilizationandothermetricsthatareusedtomeasurequeuingperformance.第一节排队的基本概念一.排队系统的组成队列服务机构顾客源到达离去现实世界中形形色色的排队系统到达的顾客要求服务的内容服务机构不能运转的机器修理修理技工修理技工领取修配零件发放零件的管理员电话呼唤通话交换台1.输入过程（1）顾客源：分为•无限(如电话呼唤)•有限m（如车间里待修理的机器）（2）到达规律：指到达间隔时间T的分布分为•定长D•负指数M•k阶爱尔朗Ek2.排队规则（1）损失制指顾客到达时若所有服务实施均被占用，则顾客自动离去。（2）等待制指顾客到达时若所有服务实施均被占用，则留下来等待，直至被服务完离去。等待的服务规则又可分为•先到先服务（FCFS）•后到先服务（LCFS）（3）混合制分为•系统容量有限制•等待时间有限制3.服务机构（2）服务规律：指服务时间v的分布分为•定长D•负指数M•k阶爱尔朗Ek•一般分布G（1）服务台个数C11(并列多台)二.排队模型的表示用记号（X/Y/Z/A/B/C）表示，其中X：顾客到达时间间隔的分布Y：服务时间的分布Z：服务台个数A：系统容量B：顾客源数量C：服务规则例1（M/M/1/FCFS）表示：到达间隔为负指数分布，服务时间也为负指数分布，1个服务台，顾客源无限，系统容量也无限，先到先服务。//若只讨论先到先服务的情况，可略去第6项。排队论（也称随即服务系统理论）研究的内容主要有以下三部分：（1）性态（描述）问题，即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布以及相应的期望值指标等；（2）最优化问题，又分静态优化和动态优化，前者指系统的最优设计，后者指现有排队系统的最优运营；（3）排队系统的统计推断，即应用统计方法判断一个给定的排队系统符合哪种模型，以便根据排对理论进行分析研究。三.排队问题的求解主要是计算描述系统运行状态的指标：1.队长和排队长队长：系统中的顾客数；其概率分布称状态概率，记为Pn，表示系统中有n个顾客的概率；队长的平均值记为Ls。排队长：系统中正在排队等待的顾客数，记其均值为Lq。2.逗留时间和等待时间逗留时间：一个顾客在系统中的停留时间，记为W，其均值记为Ws。等待时间：一个顾客在系统中排队等待的时间，记其均值为Wq。第二节到达与服务的规律一.到达的规律描述顾客到达规律可从两方面到达数（人数）到达间隔（时间）现实中有许多服务系统，其顾客的到达具有下述特征：（1）无后效性：任一时段的到达数不受前一时段的影响；（2）平稳性：顾客到达是均匀的；（3）稀有性：瞬时内只可能有1个顾客到达。称具有上述特征的输入为泊松流，其在t时段内到达n个顾客的概率为,1,0,!)()(nenttPtnn即参数为的泊松分布。t本课程只讨论统计平衡状态（稳态）由概率论知识可知，泊松分布的参数即其均值。因此，的含义是单位时间到达系统的平均顾客数，即平均到达率。下面考察，当顾客按泊松流到达时，其到达的间隔时间T是服从什么分布呢？因为到达为泊松流，所以，t时段内没有来顾客的概率为,0!)(00tteettP)(所以，t时段内有顾客到来（即间隔Tt）的概率为ttetFetTP1)(1)(，即而这正是负指数分布的分布函数，说明T服从负指数分布，且参数同为。可证反之也成立。于是得到关于到达规律的重要性质：到达数为泊松流到达间隔服从负指数分布（同参数）。由概率论知识可知，负指数分布的表达式（密度函数）为参数即其均值的倒数。因此，的含义是平均间隔时间，这与为单位时间到达系统的平均顾客数的含义一致。0,00,)(ttetftT1负指数分布有一个有趣的性质：无记忆性，即)()(00tTPtTttTP事实上，直观上看，在已知Tt0的条件下估计Tt的概率，与无条件时估计Tt的概率相同，把以前的t0时间给忘了。假若T表示某种电子元件的寿命，则当元件已使用了t0时间后估计它还能再使用t时间的概率，与刚开始用时的概率一样。说明这种元件是高度耐磨损的。)()()()())()()(00)(0000000tTPeeetTPttTPtTPtTPttTPtTttTPtttt二.服务的规律主要讨论服务时间v服从负指数分布的情形，参数为，即00,0,)(ttetftv由于v的均值为，即平均对每位顾客的服务时间为，可得11注：负指数分布的一般化——爱尔朗分布，可用于描述由k道程序组成的1个服务台的服务时间的分布。参数的含义：服务率，即单位时间平均服务完人。补充练习1.设到达一个加工中心的零件平均为60件/h，该中心的加工能力为75件/h。问系统达到稳态时加工中心的输出是60件/h还是75件/h？简要说明理由。解：因加工能力大于零件到达率，因此到达的零件全部可加工。又因到达零件平均数小于加工能力，因此稳态时平均输出应是60件/h。2.顾客来到一个快餐店的平均到达率为75/h，店内有3名服务员，来到的顾客排成一队按先到先服务的规则接受服务，每名服务员服务一个顾客的平均时间是2min，求该系统内服务员的平均繁忙率。解：服务员的繁忙率等于服务员用于为顾客服务时间占全部服务时间的比例。本例中每名服务员能力为30人/h。故三名服务员的平均繁忙率为833.090753*3075正是M/M/C中服务强度C3.顾客按泊松流到达某餐厅，平均每小时20人。该餐厅每天11:00开始营业，试求上午11:07餐厅内有18人，到11:12餐厅内有20人的概率。解：由泊松分布：...2,1,0!)()(nenttPtnn，即时间t内有n名顾客到达的概率11:07~11:12即5分钟即1/12小时内到达2名顾客的概率2623.0!2)121*20()121()121*20(22eP4.某机械师维修一台设备的时间服从负指数分布，平均需4小时，如果他使用专用工具，则可将平均时间缩短为2小时。若规定该机械师能在2小时内维修完一台设备，付报酬100元，否则只付80元。问该机械师使用专用工具较之未使用专用工具时，每维修一台设备预期增加的报酬值。解：负指数分布概率密度和分布函数：000)(ttetftvttedxxftF1)()(0机械师维修1台设备得到报酬的期望值222222010080100100))1(1(80)1(100)2(80)2(*100eeeeetPtPEI未使用专用工具时h/25.01，使用专用工具时h/5.02故)(772.4)3679.06065.0(20)(2015.012元eeEIEI第三节M/M/1排队模型一.标准的M/M/1模型（M/M/1/）/1.问题的一般提法设：泊松输入/负指服务/单服务台/系统容量无限制/顾客源无限制求：（1）系统状态概率Pn；（2）系统运行指标Ls，Lq，Ws，Wq。2.系统状态概率（1）利用状态转移图列出平衡方程状态转移图是处理稳态M/M/C系统的一种工具，设到达与服务率分别为，则由此列出平衡方程：1,)(1110nPPPPPnnn和n-1nn+1021......由平衡方程1,)(1110nPPPPPnnn可解得状态概率：1),1()(10nPPnn记，称为服务强度，规定（为什么？），则1001PPPnn（2）由平衡方程解得状态概率3.系统运行指标（1）Ls与Lq1)11))1(201100(11)(1dd)(1dd)(1dd)(1(11nnnnnnnnnnssnnnpLL数，由期望定义，表示系统中的平均顾客ssnnnnnnqLPLPnPPnL)1()1(0101。其中1）呢？而不是问题：为什么1(1qsLL——因为是均值。（2）Ws与Wq11sqs时间，即逗留时间减去平均服务平均等待时间等于平均均逗留时间于其参数的倒数，故平而负指数分布的均值等的负指数分布，服从参数为首先可证，逗留时间见教材（第3版)P281（3）上述4个指标之间的关系——里特(Little)公式1qsqsqqssWWLLWLWL。统容量无限制，故系统率。本模型中因系际进入，称有效到达率，即实应为一般的里特公式中ee例2某修理店只有一个修理工人，来修理的顾客到达数服从泊松分布，平均每小时4人；修理时间服从负指数分布，平均需6分钟。求：（1）修理店空闲的概率；（2）店内有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）店内顾客的平均数；（5）顾客在店内的平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待修理时间；（8）必须在店内消耗15分钟以上的概率。。小时，人分钟人小时，人模型，解：此为标准的52/10/61/4M/M/1。人）小时小时）人人）小时小时）人0.223)41(1)41(1)41((8);/(151101611(7);/(1545232(6);/(611(5);/(3264(4);521(3)0.0384;)53()52()(1(2);531(1)1.5414)(1003330eeFWPWPWWLLLWLPPPsqsqsss补充练习5.某小型家电维修部声称对一般家电维修做到1小时内完成，并保证顾客等待时间超过1小时修理免费。已知每项修理收费10元，修理成本为5.5元。若送达修理的家电服从泊松分布，平均6件/小时；修理每件的时间服从负指数分布，平均每件需7.5分钟。该维修部只有1名修理工。问：(a)该维修部能否做到盈利？(b)当维修时间不变，则送修家电到达率达到何值时，该维修部收支达到盈亏平衡？解：服务时间的概率分布：tWetWPtF)(1)()((a)送达家电在1小时内维修完的概率865.0135.0111)1(1)68(1)(eeWP每维修一件盈利4.5元，不能按时维修，损失5.5元。因4.5*0.865-5.5*0.135=3.149故在此修理条件下可盈利。(b)处于盈亏平衡时应有)1(*5.5)1(*5.4WPWP2.78.045.0ln)8(45.0)5.55.4(5.4*5.5)1(5.4)8()8()8()8(eeee解得：2.7补充练习6.汽车按平均每小时90辆的泊松流到达高速路上的一个收费关卡，通过关卡的平均时间为35秒。由于驾驶人员反映等待时间太长，主管部门打算采用新装置，使汽车通过关卡的时间减少到平均30秒，但增加新装置只有在原系统中等待的汽车平均数超过6辆和新装置的利用率不低