随机过程与排队论16分析

随机过程与排队论计算机科学与工程学院顾小丰Email：[e-mail]2020年1月24日星期五2020/1/24计算机科学与工程学院顾小丰上一讲内容回顾M/M/c/K混合制排队系统•问题的引入•队长•等待时间与逗留时间有限源的简单排队系统M/M/c/m/m系统•问题的引入•队长——故障的机器数•等待时间与逗留时间——故障机器等待维修的时间•其它重要指标j10jjc1K0jjcjj0jc0jcc0cqcKc1c0ccc2cckqcqKp,1jc1j!p,pj!c!cp,cjKcc!c(Kc)(KC1)p,12c!Np1(1)(Kc1),1(1)c!N1pNNNN(1p)jjkc1jj0qjcc1k1tcxjj0j0jcK1qjjcqpq,j0,1,2,,K11pq,t0W(t)P{Wqt}c(cx)qqedx,t0(jc)!jc1Wqc1WW44－22020/1/24计算机科学与工程学院顾小丰本讲主要内容M/M/c/m/m损失制系统•问题的引入•队长——故障的机器数有备用品的M/M/c/m+K/m系统•问题的引入•故障的机器数二阶段循环排队系统•问题的引入•Ⅰ号台的队长•车辆在Ⅰ号台的等待时间44－32020/1/24计算机科学与工程学院顾小丰第六章有限源的简单排队系统顾客总体是有限的输入过程是简单流服务时间服从负指数分布典型例子：机器维修模型44－42020/1/24计算机科学与工程学院顾小丰§6.1M/M/c/m/m系统1.问题的叙述c个工人共同看管m(m≥c)台机器，机器运转时会发生故障而停止生产，这时需要工人进行适当的维修，修复后立即投入运转；每台机器的寿命，即连续正常运转时间均服从参数(＞0)的负指数分布，即P(＞t)＝e-t，t≥0；m台机器各自独立运转，一旦发生故障，有空闲的工人立即对其进行修理，每个工人对每台发生故障的机器的修理时间均服从参数为(＞0)的负指数分布；如果没有空闲的工人，发生故障的机器就等待修理，直到有空闲的工人为止；每台机器的运转相互独立，修理与运转相互独立，每个工人之间的修理也相互独立。44－52020/1/24计算机科学与工程学院顾小丰2.故障的机器数假定N(t)表示在时刻t发生故障的机器数，令pij(t)＝P{N(t+t)＝j|N(t)＝i}，i,j＝0,1,2,…则1)pi,i+1(t)＝P{在t内m-i台正常的机器有一台发生故障，而修复0台}im2n}1nnt{P台台而修复内又故障在)t(p1i,i)t(ot)im(im2n1nitu1nt1ninimtntnim)e()e1(C)e()e1(C当0≤i＜c时itu1imtt1im)e()e)(e1(C44－62020/1/24计算机科学与工程学院顾小丰故障的机器数(续1)2)pi,i-1(t)3)类似分析可得pij(t)＝o(t)，|i-j|≥21m1n}1nnt{P台台而修复内又故障在mic),t(otcci1),t(oti)t(p1i,i)t(ot)im(im2n1nctu1nt1ncnimtntnim)e()e1(C)e()e1(C当c≤i＜m时故pi,i+1(t)＝(m-i)t+o(t)，0≤i＜mitu1imtt1im)e()e)(e1(C＝P{在t内又故障0台，而修复1台}44－72020/1/24计算机科学与工程学院顾小丰故障的机器数(续2)综合上述1)2)3)得2|ji|),t(om,1c,ci;1ij),t(otc1c,,2,1i;1ij),t(oti1m,,2,1,0i;1ij),t(ot)im()t(pij于是，{N(t)，t0}是有限状态空间E＝{0,1,2,…,m}上的生灭过程，而且顾客源是有限的，其参数为m,,1c,ci1c,,2,1i,c,i1m,,2,1,0i,)im(ii44－82020/1/24计算机科学与工程学院顾小丰状态转移速度图012c-1…cc+1m-1…mm(m-1)2(c-1)(m-c+1)c(m-c)c2cc44－92020/1/24计算机科学与工程学院顾小丰定理令pj＝，j=0,1,2,…，则{pj，j=0,1,2,…}存在，且)t(plimjtm,,1c,cj,pc!c!jC1c,,2,1,0j,pCp0jcjjm0jjmj其中1mciiciim1c0iiim0c!c!iCCp,特别地，当c＝1时，有;m,,2,1j,p)!jm(!mp0jj1m0ii0)!im(!mp而证明由生灭过程的极限定理即得。■m,,1c,cj,pc!c!jC1c,,2,1,0j,pCppc!c!iCC1p0jcjjm0jjm0j211j10j1mciiciim1c0iiim1m1jj211j10044－102020/1/24计算机科学与工程学院顾小丰结论我们仍然用N和Nq分别表示在统计平衡的条件m0jjjp)N(EN下发生故障的机器数和等待修复的机器数，则mcj0cjj1c0j0jpc)!jm(j!c!mp)!jm()!1j(!mmcjjqp)cj(N平均发生故障的机器数为平均等待修复的机器数为mcjj1c1jjpcjpc平均忙的维修工人数为44－112020/1/24计算机科学与工程学院顾小丰3.故障机器等待维修的时间分布假定机器是先故障先维修。定理令Wq表示在统计平衡下，该故障机器的等待修理时间，则分布函数Wq(t)＝P{Wq≤t}为0t,)!cj()tc(tc1ep1(t)W1mcjcjtcjq等待修理的平均时间为)Nm(Npc1cjWqj1mcjq44－122020/1/24计算机科学与工程学院顾小丰证明令pj-表示在统计平衡下一台机器发生故障时已有j台机器早已处于故障状态的概率，由于在j台机器发生故障的条件下，只有m-j台机器正常工作，根据负指数分布的无记忆性（马氏性）和各台机器工作的独立性，有1m,,1,0j,p)jm(kpjj其中k为比例因子。m1jj01p1kmN根据，可得于是1m,,1,0j,pNmjmpjj故1mcjt0xccjj1c0jjqdxe)!cj()c(cpp(t)W0t,)!cj()tc(tc1ep11mcjcjtcj44－132020/1/24计算机科学与工程学院顾小丰证明(续)在所有修理工均忙的条件下，新故障的机器必须等待前面j-c+1故障机器修复后才能接受修理。由于修理时间服从负指数分布，一台机器发生故障时，各个正接受修理的机器的剩余修理时间仍服从相同参数的负指数分布。在每个修理工均忙的条件下，每个修理工的输出流是参数的泊松流，c个独立工作的修理工组成的输出流是参数c的泊松流，因此相邻修复完毕的故障机器之间的间隔时间应服从参数为c的j-c+1阶爱尔朗分布，于是等待修理的平均时间为)Nm(Npc1cjWqmcjjq44－142020/1/24计算机科学与工程学院顾小丰4.其它重要指标1)平均忙的维修工人数为mcjj1c0jjcpcjpN2)平均运行的机器数为Nmp)jm(Nm0jjm3)统计平衡下单位时间内发生故障的平均机器数为)Nm(p)jm(m0jje4)统计平衡下单位时间内平均修复的机器数为cmcjj1c0jjNpcjp5)统计平衡下单位时间内平均修复的机器数等于发生故障的平均数，即ej台机器故障的概率等于m-j台机器运行的概率44－152020/1/24计算机科学与工程学院顾小丰§6.2M/M/c/m/m损失制系统1.问题的叙述c个工人共同看管m(m≥c)台机器，机器运转时会发生故障而停止生产，这时需要工人进行适当的维修，修复后立即投入运转；每台机器的寿命，即连续正常运转时间均服从参数(＞0)的负指数分布，即P(t)＝e-t，t≥0；m台机器各自独立运转，一旦发生故障，有空闲的工人立即对其进行修理，每个工人对每台发生故障的机器的修理时间均服从参数为(＞0)的负指数分布；当c个维修工人都忙于维修故障的机器时，发生故障的机器不是等待维修，而是立刻送到其它地方去修理，或者停产大修；每台机器的运转相互独立，修理与运转相互独立，每个工人之间的修理也相互独立。44－162020/1/24计算机科学与工程学院顾小丰2.故障的机器数假定N(t)表示在时刻t发生故障的机器数，令pij(t)＝P{N(t+t)＝j|N(t)＝i}，i,j＝0,1,2,…则类似于§6.1的分析可得2|ji|),t(oc,,2,1i;1ij),t(oti1c,,2,1,0i;1ij),t(ot)im()t(pij于是，{N(t)，t0}是有限状态空间E＝{0,1,2,…,c}上的生灭过程，而且顾客源是有限的，其参数为c,,2,1i,i1c,,2,1,0i,)im(ii44－172020/1/24计算机科学与工程学院顾小丰状态转移速度图012c-1…cm(m-1)2(c-1)(m-c+1)c44－182020/1/24计算机科学与工程学院顾小丰定理令pj＝，j=0,1,2,…,c，则对任意，{pj，0≤j≤c}存在，且)t(plimjtc,,2,1,0j,CCpc0kkkmjjmj证明由生灭过程的极限定理即得。■c,,2,1,0j,pCppC1p0jjm0j211j10j1c0iiim1m1jj211j100当jc时，j和j+1不存在c0kkkmccmcCC)m(p上述分布{pj，0≤j≤c}称为恩格塞特(Engset)分布，而称为恩格塞特损失公式，这是损失的概率。44－192020/1/24计算机科学与工程学院顾小丰结论当m=c时，即m台机器m个维修工人，我们有1mjpNm0jj此时，平均发生故障的机器数为m,,2,1,0j,)1(Cpmjjmj44－202020/1/24计算机科学与工程学院顾小丰§6.3有备用品的M/M/c/m+K/m系统1.问题的叙述m台机器正常工作，另有K台机器备用，有c个维修工人。当运转的机器发生故障时，发生故障的机器立刻由维修工去修理，修好后转入备用；处于正常运转的机器不足m台时，只好缺额生产；每台机器的寿命，即连续正常运转时间均服从参数(＞0)的负指数分布，即P(＞t)＝e-t，t≥0；m台机器各自独立