随机过程与排队论16分析

1、随机过程与排队论,计算机科学与工程学院 顾小丰 Email： 2020年7月7日星期二,2020/7/7,计算机科学与工程学院顾小丰,上一讲内容回顾,M/M/c/K混合制排队系统 问题的引入 队长 等待时间与逗留时间 有限源的简单排队系统 M/M/c/m/m系统 问题的引入 队长故障的机器数 等待时间与逗留时间故障机器等待维修的时间 其它重要指标,442,2020/7/7,计算机科学与工程学院顾小丰,本讲主要内容,M/M/c/m/m损失制系统 问题的引入 队长故障的机器数 有备用品的M/M/c/m+K/m系统 问题的引入 故障的机器数 二阶段循环排队系统 问题的引入 号台的队长 车辆在号台的等

2、待时间,443,2020/7/7,计算机科学与工程学院顾小丰,第六章 有限源的简单排队系统,顾客总体是有限的 输入过程是简单流 服务时间服从负指数分布,典型例子：机器维修模型,444,2020/7/7,计算机科学与工程学院顾小丰,6.1 M/M/c/m/m系统,问题的叙述 c个工人共同看管m(mc)台机器，机器运转时会发生故障而停止生产，这时需要工人进行适当的维修，修复后立即投入运转； 每台机器的寿命，即连续正常运转时间均服从参数(0)的负指数分布，即P(t)e-t，t0； m台机器各自独立运转，一旦发生故障，有空闲的工人立即对其进行修理，每个工人对每台发生故障的机器的修理时间均服从参数为(0

3、)的负指数分布； 如果没有空闲的工人，发生故障的机器就等待修理，直到有空闲的工人为止； 每台机器的运转相互独立，修理与运转相互独立，每个工人之间的修理也相互独立。,445,2020/7/7,计算机科学与工程学院顾小丰,2.故障的机器数,假定N(t)表示在时刻t发生故障的机器数，令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2, 则,1)pi,i+1(t)P在t内m-i台正常的机器 有一台发生故障，而修复0台,当0ic时,446,2020/7/7,计算机科学与工程学院顾小丰,故障的机器数(续1),pi,i-1(t),类似分析可得 pij(t)o(t)，|i-j|2,当cim时,故p

4、i,i+1(t)(m-i)t+o(t)，0im,P在t内又故障0台，而修复1台,447,2020/7/7,计算机科学与工程学院顾小丰,故障的机器数(续2),综合上述1)2)3)得,于是，N(t)，t0是有限状态空间E0,1,2, ,m上的生灭过程，而且顾客源是有限的，其参数为,448,2020/7/7,计算机科学与工程学院顾小丰,状态转移速度图,449,2020/7/7,计算机科学与工程学院顾小丰,定理,令pj ，j=0,1,2,，则pj，j=0,1,2,存,在，且,其中,特别地，当c1时，有,证明 由生灭过程的极限定理即得。,4410,2020/7/7,计算机科学与工程学院顾小丰,结论,我们

5、仍然用N和Nq分别表示在统计平衡的条件,下发生故障的机器数和等待修复的机器数，则,平均发生故障的机器数为,平均等待修复的机器数为,平均忙的维修工人数为,4411,2020/7/7,计算机科学与工程学院顾小丰,3.故障机器等待维修的时间分布,假定机器是先故障先维修。,定理 令Wq表示在统计平衡下，该故障机器的等待修理时间，则分布函数Wq(t)PWqt为,等待修理的平均时间为,4412,2020/7/7,计算机科学与工程学院顾小丰,证明,令pj-表示在统计平衡下一台机器发生故障时已有j台,机器早已处于故障状态的概率，由于在j台机器发生故障的条件下，只有m-j台机器正常工作，根据负指数分布的无记忆性

6、（马氏性）和各台机器工作的独立性，有,其中k为比例因子。,于是,故,4413,2020/7/7,计算机科学与工程学院顾小丰,证明(续),在所有修理工均忙的条件下，新故障的机器必须等待前面j-c+1故障机器修复后才能接受修理。由于修理时间服从负指数分布，一台机器发生故障时，各个正接受修理的机器的剩余修理时间仍服从相同参数的负指数分布。在每个修理工均忙的条件下，每个修理工的输出流是参数的泊松流，c个独立工作的修理工组成的输出流是参数c的泊松流，因此相邻修复完毕的故障机器之间的间隔时间应服从参数为c的j-c+1阶爱尔朗分布，于是等待修理的平均时间为,4414,2020/7/7,计算机科学与工程学院顾

7、小丰,4.其它重要指标,平均忙的维修工人数为,平均运行的机器数为,统计平衡下单位时间内发生故障的平均机器数为,统计平衡下单位时间内平均修复的机器数为,统计平衡下单位时间内平均修复的机器数等于发生故障的平均数，即,j台机器故障的概率等于m-j台机器运行的概率,4415,2020/7/7,计算机科学与工程学院顾小丰,6.2 M/M/c/m/m损失制系统,问题的叙述 c个工人共同看管m(mc)台机器，机器运转时会发生故障而停止生产，这时需要工人进行适当的维修，修复后立即投入运转； 每台机器的寿命，即连续正常运转时间均服从参数(0)的负指数分布，即P(t)e-t，t0； m台机器各自独立运转，一旦发生

8、故障，有空闲的工人立即对其进行修理，每个工人对每台发生故障的机器的修理时间均服从参数为(0)的负指数分布； 当c个维修工人都忙于维修故障的机器时，发生故障的机器不是等待维修，而是立刻送到其它地方去修理，或者停产大修； 每台机器的运转相互独立，修理与运转相互独立，每个工人之间的修理也相互独立。,4416,2020/7/7,计算机科学与工程学院顾小丰,2.故障的机器数,假定N(t)表示在时刻t发生故障的机器数，令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2, 则类似于6.1的分析可得,于是，N(t)，t0是有限状态空间E0,1,2,c上的生灭过程，而且顾客源是有限的，其参数为,44

9、17,2020/7/7,计算机科学与工程学院顾小丰,状态转移速度图,4418,2020/7/7,计算机科学与工程学院顾小丰,定理,令pj ，j=0,1,2,c，则对任意 ，,pj， 0jc存在，且,证明 由生灭过程的极限定理即得。,当jc时，j和j+1不存在,上述分布pj，0jc称为恩格塞特(Engset)分布，而,称为恩格塞特损失公式，这是损失的概率。,4419,2020/7/7,计算机科学与工程学院顾小丰,结论,当m=c时，即m台机器m个维修工人，我们有,此时，平均发生故障的机器数为,4420,2020/7/7,计算机科学与工程学院顾小丰,6.3 有备用品的M/M/c/m+K/m系统,问题

10、的叙述 m台机器正常工作，另有K台机器备用，有c个维修工人。当运转的机器发生故障时，发生故障的机器立刻由维修工去修理，修好后转入备用； 处于正常运转的机器不足m台时，只好缺额生产； 每台机器的寿命，即连续正常运转时间均服从参数(0)的负指数分布，即P(t)e-t，t0； m台机器各自独立运转，一旦发生故障，有空闲的工人立即对其进行修理，每个工人对每台发生故障的机器的修理时间均服从参数为(0)的负指数分布； 每台机器的运转相互独立，修理与运转相互独立，每个工人之间的修理也相互独立。,4421,2020/7/7,计算机科学与工程学院顾小丰,2.故障的机器数,假定N(t)表示在时刻t发生故障的机器数

11、，令,pij(t)PN(t+t)j|N(t)i，i,j0,1,2, 则类似于6.1的分析可得 1)当cK，即维修工人数小于等于备用机器台数时，有,4422,2020/7/7,计算机科学与工程学院顾小丰,故障的机器数(续1),间E0,1,2,m+K上的生灭过程，其参数为,于是，当cK时，N(t)，t0是有限状态空,4423,2020/7/7,计算机科学与工程学院顾小丰,2.故障的机器数(续2),2)当cK，即维修工人数大于备用机器台数,时，有,4424,2020/7/7,计算机科学与工程学院顾小丰,2.故障的机器数(续3),于是，N(t)，t0是有限状态空间E0,1,2,m+K上的生灭过程，其参

12、数为,4425,2020/7/7,计算机科学与工程学院顾小丰,cK时的状态转移速度图,4426,2020/7/7,计算机科学与工程学院顾小丰,cK时的状态转移速度图,4427,2020/7/7,计算机科学与工程学院顾小丰,定理1,当cK时，令pj ，j=0,1,2,c，则对任意,，pj，0jm+K存在，且,证明 由生灭过程的极限定理即得。,4428,2020/7/7,计算机科学与工程学院顾小丰,定理2,当cK时，令pj ，j=0,1,2,c，则对任意,，pj，0jm+K存在，且,证明 由生灭过程的极限定理即得。,4429,2020/7/7,计算机科学与工程学院顾小丰,注,在cK时，若c固定，当

13、K充分大时，可近似,地看成无限总体的系统，具有到达率为m，可用M/M/c/型系统的有关结果作近似计算反而简单，因为当K时，若m/1，则可化为M/M/c/型系统的有关结果；在当cK时，若K0（即无备用机器），则可化为M/M/c/m/m型系统的有关结果。,4430,2020/7/7,计算机科学与工程学院顾小丰,例,某航空公司要保证正常的运营，应保证有12,台发动机处于良好状态的概率不低于0.995，设每台发动机正常运转时间服从负指数分布，平均连续运转时间为3个月，有2个维修工负责其修理工作，修理时间也服从负指数分布，平均修复时间为5天，问：在满足要求的前提下，应该备用多少台发动机？,4431,20

14、20/7/7,计算机科学与工程学院顾小丰,解,由题设知，m12(台)，c2(个)，1/3 (台/月)，,6(台/月)，1/18，要保证使得同时有12台发动机处于良好状态的概率不低于0.995，则等价于故障的发动机不超过备用发动机数的概率不低于0.995，于是,当备用机器数K2（c）时，有,当备用机器数K3（c）时，有,所以，应取备用发动机台数K3。,4432,2020/7/7,计算机科学与工程学院顾小丰,6.4 二阶段循环排队系统,问题的叙述 n辆卡车担任运输任务，在生产厂与仓库（或车站、码头等）之间来回运输。 把生产厂叫做号服务台，仓库叫做号服务台，把从号到号之间的路途时间及在号台的实际服务

15、时间之和看作“号台的服务时间”；把从号到号之间的路途时间及在号台的实际服务时间之和看作“号台的服务时间”；、两个服务台的服务时间分别服从参数为1、2的负指数分布；工作相互独立。 n辆卡车在、号台之间轮番排队，若在号台的车辆（包括正在接受服务的）为i辆，则在号台的车辆为n-i辆，用(i,n-i)表示系统所处的状态。,4433,2020/7/7,计算机科学与工程学院顾小丰,二阶段循环排队模型,1,2,队长i,队长n-i,由于二阶段循环排队系统的状态完全由号台的状态决定，因此，我们仅讨论号台的情况。,4434,2020/7/7,计算机科学与工程学院顾小丰,2. 号台的队长,假定N(t)表示时刻t在号

16、台的车辆，包括正在接受,服务的车辆，令 pij(t)PN(t+t)j|N(t)i，i,j0,1,2, 则,1)pi,i-1(t),pn,n-1(t),P在t内号台服务完1辆， 号台一辆也没服务完,P在t内号台服务完1辆,4435,2020/7/7,计算机科学与工程学院顾小丰,号台的队长(续1),pi,i+1(t),p0,1(t),类似分析可得 pij(t)o(t)，|i-j|2,P在t内号台服务完1辆， 号台一辆也没服务完,P在t内号台服务完1辆,4436,2020/7/7,计算机科学与工程学院顾小丰,号台的队长(续2),综合上述1)2)3)得,于是，N(t)，t0是有限状态空间E0,1,2,

17、n上的生灭过程，其参数为,状态转移速度图,4437,2020/7/7,计算机科学与工程学院顾小丰,定理,令pj ，j=0,1,2,，则pj，j=0,1,2,存,在，且,其中,特别地，当12时，有,证明 由生灭过程的极限定理即得。,4438,2020/7/7,计算机科学与工程学院顾小丰,结论,在号台的平均对长,在号台的平均等待对长,4439,2020/7/7,计算机科学与工程学院顾小丰,3.车辆在号台的等待时间,假定车辆是按先到先服务。,令pj-表示到达号台的车辆看到号台已有j辆车的平稳概率，则,pj-P号台恰好有j辆车|新车进入,4440,2020/7/7,计算机科学与工程学院顾小丰,定理,令Wq表示在统计平衡下，该车辆在号台的,等待时间，则分布函数Wq(t)PWqt为,平均等待时间为,4441,2020/7/7,计算机科学与工程学院顾小丰,某系统利用2台计算机进行容错处理。如果1台计算机正常工作时间服从负指数分布，平均10天，而计算机损坏时由1名工程师维修，维修1台计算机的时间是负指数分布的，平均5天。求：2台计算机都正常运行的概率和由于计算机损坏无法运行的概率，系统中平均运行的计算机数。 某电视台有2部发射机，1部发射1部备用。如果1部正常工作时间服从负指