《随机过程与排队论16讲述》由会员分享，可在线阅读，更多相关《随机过程与排队论16讲述（44页珍藏版）》请在金锄头文库上搜索。
1、随机过程与排队论 计算机科学与工程学院 顾小丰 Email：guxf * *计算机科学与工程学院 顾小丰 上一讲内容回顾 M/M/c/K混合制排队系统 问题的引入 队长 等待时间与逗留时间 有限源的简单排队系统 M/M/c/m/m系统 问题的引入 队长故障的机器数 等待时间与逗留时间故障机器等待维 修的时间 其它重要指标 442 *计算机科学与工程学院 顾小丰 本讲主要内容 M/M/c/m/m损失制系统 问题的引入 队长故障的机器数 有备用品的M/M/c/m+K/m系统 问题的引入 故障的机器数 二阶段循环排队系统 问题的引入 号台的队长 车辆在号台的等待时间 443 *计算机科学与工程学院
2、顾小丰 第六章 有限源的简单排队系统 v顾客总体是有限的 v输入过程是简单流 v服务时间服从负指数分布 典型例子：机器维修模型 444 *计算机科学与工程学院 顾小丰 6.1 M/M/c/m/m系统 问题的叙述 vc个工人共同看管m(mc)台机器，机器运转时会发生故障而停止生 产，这时需要工人进行适当的维修，修复后立即投入运转； v每台机器的寿命，即连续正常运转时间均服从参数(0)的负指 数分布，即P(t)e-t，t0； vm台机器各自独立运转，一旦发生故障，有空闲的工人立即对其进 行修理，每个工人对每台发生故障的机器的修理时间均服从参数 为(0)的负指数分布； v如果没有空闲的工人，发生故障
3、的机器就等待修理，直到有空闲 的工人为止； v每台机器的运转相互独立，修理与运转相互独立，每个工人之间 的修理也相互独立。 445 *计算机科学与工程学院 顾小丰 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 *计算机科学与工程学院 顾小丰 故障的机器数(续1) 2)pi,i-1(t) 3) 类似分析可得 pij(t)o(t)，|i-j|2 当cim时 故pi,i+1(t)(m-i)t+o(t)，0im P在t内又
4、故障0台，而修复1台 447 *计算机科学与工程学院 顾小丰 故障的机器数(续2) 综合上述1)2)3)得 于是，N(t)，t0是有限状态空间E0,1,2, ,m上的生灭过程，而且顾客源是有限的，其参 数为 448 *计算机科学与工程学院 顾小丰 状态转移速度图 012 c-1 cc+1m-1 m m (m-1) 2(c-1) (m-c+1) c (m-c) c 2 c c 449 *计算机科学与工程学院 顾小丰 定理 令pj ，j=0,1,2,，则pj，j=0,1,2,存 在，且 其中 特别地，当c1时，有 证明 由生灭过程的极限定理即得。 4410 *计算机科学与工程学院 顾小丰 结论 我
5、们仍然用N和Nq分别表示在统计平衡的条件 下发生故障的机器数和等待修复的机器数，则 平均发生故障的机器数为 平均等待修复的机器数为 平均忙的维修工人数为 4411 *计算机科学与工程学院 顾小丰 3.故障机器等待维修的时间分布 假定机器是先故障先维修。 定理 令Wq表示在统计平衡下，该故障机器的 等待修理时间，则分布函数Wq(t)PWqt为 等待修理的平均时间为 4412 *计算机科学与工程学院 顾小丰 证明 令pj-表示在统计平衡下一台机器发生故障时已有j台 机器早已处于故障状态的概率，由于在j台机器发生故障 的条件下，只有m-j台机器正常工作，根据负指数分布的 无记忆性（马氏性）和各台机器
6、工作的独立性，有 其中k为比例因子。 于是 故 4413 *计算机科学与工程学院 顾小丰 证明(续) 在所有修理工均忙的条件下，新故障的机器必 须等待前面j-c+1故障机器修复后才能接受修理。由 于修理时间服从负指数分布，一台机器发生故障时 ，各个正接受修理的机器的剩余修理时间仍服从相 同参数的负指数分布。在每个修理工均忙的条件下 ，每个修理工的输出流是参数的泊松流，c个独立 工作的修理工组成的输出流是参数c的泊松流，因 此相邻修复完毕的故障机器之间的间隔时间应服从 参数为c的j-c+1阶爱尔朗分布，于是等待修理的平 均时间为 4414 *计算机科学与工程学院 顾小丰 4.其它重要指标 1)平
7、均忙的维修工人数为 2) 平均运行的机器数为 3) 统计平衡下单位时间内发生故障的平均机器数为 4) 统计平衡下单位时间内平均修复的机器数为 5) 统计平衡下单位时间内平均修复的机器数等于发生故障 的平均数，即 j台机器故障的概 率等于m-j台机 器运行的概率 4415 *计算机科学与工程学院 顾小丰 6.2 M/M/c/m/m损失制系统 问题的叙述 vc个工人共同看管m(mc)台机器，机器运转时会发生故障而停止 生产，这时需要工人进行适当的维修，修复后立即投入运转； v每台机器的寿命，即连续正常运转时间均服从参数(0)的负 指数分布，即P(t)e-t，t0； vm台机器各自独立运转，一旦发生
8、故障，有空闲的工人立即对其 进行修理，每个工人对每台发生故障的机器的修理时间均服从参 数为(0)的负指数分布； v当c个维修工人都忙于维修故障的机器时，发生故障的机器不是等 待维修，而是立刻送到其它地方去修理，或者停产大修； v每台机器的运转相互独立，修理与运转相互独立，每个工人之间 的修理也相互独立。 4416 *计算机科学与工程学院 顾小丰 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 *计算机科学与工程学院 顾小丰 状态转移速度图 012 c-1 c m (m-1) 2(c-1) (m-c+1) c 4418 *计算机科学与工程学院 顾小丰 定理 令pj ，j=0,1,2,c，则对任意 ， pj， 0jc存在，且 证明 由生灭过程的极限定理即得。 当jc时，j 和j+1不存在 上述分布pj，0jc称为恩格塞特(Engset)分布，而 称为恩格塞特损失公式，这是损失的概率。 4419 *计算机科学与工程学院 顾小丰 结论 当m=c时，即m台机器m个维修工人，我们有 此时，平均发生故障的机器数为 4420 *计算机科学与工程学院 顾小丰 6.3 有备用品的M/M/c/m+
10、K/m系统 问题的叙述 vm台机器正常工作，另有K台机器备用，有c个维修工 人。当运转的机器发生故障时，发生故障的机器立刻 由维修工去修理，修好后转入备用； v处于正常运转的机器不足m台时，只好缺额生产； v每台机器的寿命，即连续正常运转时间均服从参数 (0)的负指数分布，即P(t)e-t，t0； vm台机器各自独立运转，一旦发生故障，有空闲的工人 立即对其进行修理，每个工人对每台发生故障的机器 的修理时间均服从参数为(0)的负指数分布； v每台机器的运转相互独立，修理与运转相互独立，每 个工人之间的修理也相互独立。 4421 *计算机科学与工程学院 顾小丰 2.故障的机器数 假定N(t)表示
11、在时刻t发生故障的机器数，令 pij(t)PN(t+t)j|N(t)i，i,j0,1,2, 则类似于6.1的分析可得 1)当cK，即维修工人数小于等于备用机器台数 时，有 4422 *计算机科学与工程学院 顾小丰 故障的机器数(续1) 间E0,1,2,m+K上的生灭过程，其参数为 于是，当cK时，N(t)，t0是有限状态空 4423 *计算机科学与工程学院 顾小丰 2.故障的机器数(续2) 2)当cK，即维修工人数大于备用机器台数 时，有 4424 *计算机科学与工程学院 顾小丰 2.故障的机器数(续3) 于是，N(t)，t0是有限状态空间E0,1, 2,m+K上的生灭过程，其参数为 4425
12、 *计算机科学与工程学院 顾小丰 cK时的状态转移速度图 m m 2 (c-1) m c m c (m-1) c c m 01c-1c KK+1m+K m+K-1 2 c 4426 *计算机科学与工程学院 顾小丰 cK时的状态转移速度图 m m 2K m (K+1) (m-1) (c-1) (m-c+1) c c 01KK+1 c-1cm+K m+K-1 2 c 4427 *计算机科学与工程学院 顾小丰 定理1 当cK时，令pj ，j=0,1,2,c，则对任意 ，pj，0jm+K存在，且 证明 由生灭过程的极限定理即得。 4428 *计算机科学与工程学院 顾小丰 定理2 当cK时，令pj ，j
13、=0,1,2,c，则对任意 ，pj，0jm+K存在，且 证明 由生灭过程的极限定理即得。 4429 *计算机科学与工程学院 顾小丰 注 在cK时，若c固定，当K充分大时，可近似 地看成无限总体的系统，具有到达率为m，可用 M/M/c/型系统的有关结果作近似计算反而简单 ，因为当K时，若m/1，则可化为 M/M/c/型系统的有关结果；在当cK时，若K 0（即无备用机器），则可化为M/M/c/m/m型系 统的有关结果。 4430 *计算机科学与工程学院 顾小丰 例 某航空公司要保证正常的运营，应保证有12 台发动机处于良好状态的概率不低于0.995，设每 台发动机正常运转时间服从负指数分布，平均连
14、 续运转时间为3个月，有2个维修工负责其修理工 作，修理时间也服从负指数分布，平均修复时间 为5天，问：在满足要求的前提下，应该备用多少 台发动机？ 4431 *计算机科学与工程学院 顾小丰 解 由题设知，m12(台)，c2(个)，1/3 (台/月)， 6(台/月)，1/18，要保证使得同时有12台发动机处于 良好状态的概率不低于0.995，则等价于故障的发动机不超 过备用发动机数的概率不低于0.995，于是 1) 当备用机器数K2（c）时，有 2) 当备用机器数K3（c）时，有 所以，应取备用发动机台数K3。 4432 *计算机科学与工程学院 顾小丰 6.4 二阶段循环排队系统 问题的叙述
15、vn辆卡车担任运输任务，在生产厂与仓库（或车站、码 头等）之间来回运输。 v把生产厂叫做号服务台，仓库叫做号服务台，把 从号到号之间的路途时间及在号台的实际服务 时间之和看作“号台的服务时间”；把从号到号 之间的路途时间及在号台的实际服务时间之和看作 “号台的服务时间”；、两个服务台的服务时间 分别服从参数为1、2的负指数分布；工作相互独立。 vn辆卡车在、号台之间轮番排队，若在号台的车 辆（包括正在接受服务的）为i辆，则在号台的车辆 为n-i辆，用(i,n-i)表示系统所处的状态。 4433 *计算机科学与工程学院 顾小丰 二阶段循环排队模型 1 2 队长i队长n-i 由于二阶段循环排队系统的状态完全由号台 的状态决定，因此，我们仅讨论号台的情况。 4434 *计算机科学与工程学院 顾小丰 2. 号台的队长 假定N(t)表示时刻t在号台的车辆，包括正在接受 服务的车
