排队论第2章

信息与通信工程学院主讲：黄湘松2012年9月所谓无限源的简单排队系统是指顾客的来源是无限的，输入过程是简单流，服务时间是负指数分布的排队系统。本章主要讨论一些典型的简单排队系统。顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去M/M/1模型无限输入过程服从参数为的Poisson过程单队队长无限先到先服务服务时间服从参数为的负指数分布生灭过程（1）系统状态：系统中的顾客数M/M/1/∞系统状态转移速度图圆圈表示状态符号；箭头表示从一个状态到另一个状态的转移。012n-1nn+1010PP001PPPλ1第二项：0120P)(PP0020P)(PP∴0202021PP)(P)(P第三项：继续打开，计算整理得（或用数学归纳法）0231P)(PP00230P)(PP∴0303022231PP)(P)(P00)(PPPnnnn=0,1,2,…10nnP由概率性质知：111000PPnn(数列的极限为)∴1110Pnn)(P1∴系统稳态概率系统的运行指标对ρ的实际意义的解释◦ρ＝λ/μ，是平均到达率与平均服务率之比，即在相同时区内顾客到达的平均数与被服务的平均数之比。◦若将ρ表示为ρ＝(1/μ)/(1/λ)，它是一个顾客的服务时间与到达间隔时间之比，称ρ为服务强度(trafficintensity)，或话务强度。◦由前面的公式可知，ρ=1-P0，它刻画了服务机构的繁忙程度，所以ρ又称为服务机构的利用率。3.系统的运行指标计算(1)系统中的队长Ls（平均队长）nnnnsnPnL001...)((n...)()()(n11312132...nn...nn1433223322132......n(0ρ1)1Ls即:期望(2)队列中等待的平均顾客数LqnnnnqnPnL111)1()1(nnnn)(n111112sL(3)顾客在系统中的平均逗留时间Ws顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为μ-λ的负指数分布，分布函数11nn和密度函数为：w)(e)w(F1w)(e)()w(f（w≥0）)WsLs(1wEWs∴(4)顾客在队列中的平均逗留时间Wq111WsWq)WqLq(等待时间顾客在队列中的平均逗留时间应为Ws减去平均服务时间。考虑LS与WS的关系四个指标的关系为(Little公式)：s2sqsρLλμρλρ1ρρLLρ1ρλμλLλLλμρμ1WWλLλμ1Wqsqss计算有关指标Little公式（相互关系）qsqsqqssLL小结1sWqWqLsL平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率4.系统的忙期与闲期系统处于空闲状态的概率：10P系统处于繁忙状态的概率：010PnP)(服务强度平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/闲期的分布与顾客到达时间间隔的相同----服从参数为的负指数分布计算有关指标忙期与闲期WHY?1-P0=平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/平均忙期B=(/(1-))/=1/(-)计算有关指标忙期与闲期与逗留时间Ws相同!!!?23在繁忙状态下，队列中的平均顾客数Lb：Ls)N(PLLqb0顾客平均等待时间:Ws)N(PWWqb10忙期的平均长度:1B1IB(由来)一个忙期平均服务的顾客数为：111Lb×P(N≥0)=Lq24到达的病人数n出现次数fn010128229316410566以上1合计100为病人完成手术时间v(小时)出现次数fv0.0－0.2380.2－0.4250.4－0.6170.6－0.890.8－1.061.0－1.251.2以上0合计100表9-4表9-5261.参数的确定算出每小时病人平均到达率＝＝2.1(人/小时)每次手术平均时间＝＝0.4(小时/人)每小时完成手术人数(平均服务率)＝＝2.5(人/小时)2.取λ＝2.1，μ＝2.5，可以通过统计检验的方法(例如χ2检验法)，认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的负指数分布。3.它说明服务机构(手术室)有84％的时间是繁忙(被利用)，有16％的时间是空闲的。2.10.842.5100nnf100vvf274.依次算出各指标：在病房中病人数(期望值)排队等待病人数(期望值)病人在病房中逗留时间(期望值)病人排队等待时间(期望值)2.15.25()2.52.1sL人0.845.254.41()qL人12.5()2.52.1sW小时0.842.1()2.52.1qW小时解：这是一个模型//1/MM28.11QL（1）排队等待维修的平均电话数；（2）等待维修电话的多于2部的概率；（3）如果使等待维修的电话数平均为2部，维修速率应提高多少？所以，接待速率应提高：例战时，集团军通信团的通信设备以指数速率每小时6台损坏，有一个维修技师，其维修速率是指数速率每小时8台，设备损坏而没有得到及时维修造成的损失是每台设备每小时100次通话，问：由于损坏的设备引起的平均通话损失率是多少？解：该问题是一个排队模型，其中//1/MM因此，平均通话损失率等于每小时300次。而损坏设备的平均数就是L则平均通话损失率＝每台设备每小时100次损坏设备的平均数例：某火车站的售票处设有一个窗口．若购票者是以最简单流到达，平均每分钟到达1人，假定售票时间服从负指数分布，平均每分钟可服务2人，试研究售票窗口前排队情况．解由题设(人／分)，(人／分)，平均队长(人)平均等待队长人)平均等待时问(分)．平均逗留时间(分)．超过5人的概率为顾客不需要等待的概率为等待的顾客人数例在某工地卸货台装卸设备的设计方案中，有三个方案可供选择，分别记作甲、乙、丙。目的是选取使总费用最小的方案，有关费用(损失)如下表所示：方案每天固定费用每天可变操作费(元)每小时平均装卸袋数甲乙丙60130250100150200100020006000设货车按最简单流到达，平均每天(按10小时计算)到达15车，每车平均装货500袋，卸货时间服从负指数分布．每辆车停留1小时的损失为10元．于方案解平均到达率车／小时，服务率依赖由，1辆车在系统内平均停留时间为1sW每天货车在系统停留的平均损失费为W(平均停留时间)×10×15(总车辆)，每天的实际可变费用(如燃料费等)为(可变操作费／天)×设备忙的概率＝c×p(元／天)而所以每个方案的费用综合如下表所示从上表知方案乙的总费用最省。例：要购置计算机，有两种方案．甲方案是购进一大型计算机，乙方案是购置n台小型计算机．每台小型计算机是大型计算机处理能力的1/n倍．设要求上机的题从平均逗留时间、等待时间看，应该选择哪一个方案．目是参数为的最简单流，大型计算机与小型计算机计算题目的时间是负指数分布，大型计算机的参数是试解设按甲方案，购大型计算机．平均等待时问平均逗留时间到达率为服务率为平均等待时间平均逗留时间所以只是从平均等待时间，平均逗留时间考虑，应该购置大型计算机按乙方案，购n台小型计算机，每台小计算机的题目例设船到码头，在港口停留单位时间损失cI元，进港船只是最简单流，参数为，装卸时间服从参数为的负指数分布，服务费用为是一个正常数．求使整个系统总费用损失最小的服务率解因为平均队长的损失费为所以船在港口停留服务费用为因此总费用为使F达到最小，先求F的导数求让解出因为最优服务率是当时平均队长L、平均等待队长Lq、平均逗留时间W、平均等待时间Wq是排队系统的重要特征．这些指标反映了排队系统的服务质量，是顾客及排队系统设计者关心的几个指标．由上述公式，得到这四个指标之间的关系．这两组关系式，可以作这样直观解释：当系统内有顾客时，平均等待队长Lq应该是平均队长L减1，当系统内没有顾客时，平均等待队长Lq与平均队长L相等，所以单位时间内平均进入系统的顾客为个．每个顾客在系Wq个顾客在等待服务．统内平均逗留W单位时间．因此系统内平均有W个顾客同样理由，系统内平均有上式在更一般的系统也成立，通常称为Little公式课堂练习1例：(病人候诊问题)某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布，试分析该科室的工作状况(即求队长、队列长、逗留时间和等待时间)。（1）如果满足99%以上的病人有座，此科室至少应设多少座位?解:由题意知，，从而排队系统的稳态概率为4545081,,.pnnn0208012..,,该科室平均有病人数为该科室内排队候诊病人数为看一次病平均所需的时间为排队等候看病的平均时间为ρ1ρλμλLρLλμρλρ1ρρLL2qλLλμ1WλLλμρμ1WWqq（1）为满足99%以上的病人有座，设科室应设m个座位，则m应满足Pm{}.医务室病人数099（2）如果该单位24小时上班，则每天平均有病人人，病人看病所花去的总时间为小时，因看病平均每天损失元。WqWqLL如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。当N=1时为即时制的情形；当N→∞时为容量无限制的情形系统中共有N个位置可供进入系统的顾客占用，一旦N个位置已被顾客占用(包括等待服务和接受服务的顾客)，新到的顾客就自动离开服务系统永不再回来．如果系统中有空位置，新到的顾客就进入系统排队等待服务，服务完后离开系统．排队系统有一个服务台，服务时间是负指数分布，参数是顾客以最简单流到达，参数为稳态下各状态间概率强度的状态转移速度图状态转移方程Nn1-Nn)(0n11101NNnnnPPPPPPP求排队系统顾客数的分布状况01102101......,...2,1,ppCnpCpnnnnnnnnn其中11......,...2,1,002000110210pppppCwherenpCpNNnnnnnnnnnnnN1,2,...,n1111110nNnNPP1)1(20NP求排队系统顾客数的分布状况◦队长◦队列长1101)1(1NNNnnsNnPL)1()1(00PLPnLsNnnq计算有关指标◦逗留时间◦等待时间111Little1100）（）（公式根据）（）或（有效到达率：NqsesseNePLPLLWPP1