《排队论复习指南》由会员分享，可在线阅读，更多相关《排队论复习指南（28页珍藏版）》请在金锄头文库上搜索。
1、复习要求 复习要求 Littles定理 例题3.1,3.5,3.6,3.7 习题 3.2， 3.3 Poisson 过程与指数分布的无记忆性 习题3.6,3.8，3.9和3.12 M/M/*系统 这些系统的马氏链和平稳分布计算. 这些系统的统计量. 习题3.13(a),(b),3.14,3.18,3.21,3.22,3.26. M/G/1和优先级队列 (P-K)公式(3.53)及相关参数的计算 例题3.15 不可抢先的优先级队列公式(3.78-3.83) 习题3.36，3.37,3.39 可逆马氏链，Burke定理 习题3.54 开排队网络的Jacksons 定理 计算节点总到达率: 公式(3
2、.114) 乘积形式的联合分布: 公式(3.116),(3.117), (3.137)-(3.139) 例题3.19,习题3.61. 证明不要求！ 闭排队网络的Jacksons 定理 公式(3.152) 吞吐率计算:公式和特解选择方法(见讲稿) 例题3.21,3.22,3.62. 习题3.2 两个通信节点1,2分别发送文件给节点3， 节点1,2传送文件分别需要平均R1和R2个时间 单位 节点3处理来自节点1,2的文件分别需要P1和P2 个时间单位 令i分别是节点1,2处的发送文件的速率 求（ 1， 2）的可能取值范围 习题3.2： solution 对整个系统使用Little定理 在节点1,2
3、处使用Little定理 在节点3处使用Little定理 1PRPR 222111 =+）（）（ 1R1R 2211 ， 1P 2211 +P 习题3.3 一个机房有N台机器，机器随时可能发生故 障， 一旦机器出现故障，将由m个维修工中的一 个进行维修 机器维修之后会在平均R时间单位之后坏掉 维修一台机器需要平均P个时间单位 求单位时间内坏掉机器数目及同一台机器两 次维修之间的平均时间 习题3.3 machine 1 machine 2 machine N Repair 1 Repair 2 Repair m A B C 习题3.3： solution 如图，设B、C之间的延迟为D，则： 1、最
4、好情况下D=P； 2、最坏情况下m个工人都在维修，且剩余 机器也都在B处排队，此N-m台机器每台的 平均排队等待接受其前一个接受服务完成的 时间为 ，因此 。 m P ()P m P mND+= 可得A、C之间的平均延迟T满足： 根据Littles定理，系统吞吐率满足： 对修理工人处用Littles定理有： 最终得到 由Littles定理，得到T的范围： m NP RTPR+ PR N m NP R N + + P m + + PR N P m m NP R N ,min m NP RTPR m PN + +,max 36 (a)4个客户的服务时间是独立同分布的指数的 随机变量, 所以每个人先
5、离开的概率都是1/4. (b)等待时间有指数分布,参数4.平均等待时间 为1/4(分钟)， 共花费时间1.25（分钟） (c)答：不变.因为,当另一个等待客户开始接收 服务时,银行内同样有4个人在接受服务,从这时 以后他们的剩余服务时间仍是指数分布随机时 间,情况和(a)相同. 38 3.8 到达的packet和正在传输的前一个到达的packet不发生冲突当且 仅当它们之间的到达间隔前一个的传输时间;和下一个到达的 packet不发生冲突当且仅当它和下一个到达之间的间隔它自己 的传输时间.所以（参考上图）, (a)Pno collision=P2tP3t=e-2t ,式中t0.02s,2t2-
6、t1 . (b) (1).Pno collision with predecessor or successor= P2s1 P3s2,其中,s1和s2分别为predecesor的传输时间 和successor的传输时间.因为这些都是指数分布的独立的随机变 量,所以,应用以下公式（习题3.12,或讲稿）,得到： Pno collision with predecessor or successor(/（+ )2 ,将10和1/0.02,代入上式得0.694. (2).Pno collisionPzero customers in M/M/ and no arrival during his s
7、ervicee-/ Ps,为下一到达间隔,s为服务 时间.经计算可得该概率值为0.682. 上式的前一项即为队长是0的概率。 3.12 X: 指数的随机变量,参数 Y: 指数的随机变量,参数 X, Y:彼此独立 则: 1.minX, Y:也是指数的随机 变量,参数+ 2.概率: PXY=/(+) 3. qi,i+1=(/(+)(+) = 00 00 00 0 () 00 ( , ) (1) () 1 y XY y xy y yx yy yy P XYfx y dx dy eedx dy eedx dy eedy edyedy + = = = = 3.13 3.13(a) 以(n,m)系统表示系
8、统状态,n为车的数目,m为人 的数目.可能的状态为(根据题目所描述的规则，不会存在 车和人同时排队的情况): (W,0),(W-1,0),(0,0),(0,1),(0,n),. 状态转移率为: (i,0)(i-1,0)为, (0,n)(0,n1)也是, (i-1,0)(i,0)为, (0,n)(0,n-1)也是. 车的队列的分布（可根据马氏链解出 P(W,0)=1- .其他任意状态的概率可由P(W,0) 来表示。） P0辆车n0W+n(1- )=W. Pi辆车= W-i(1- ), 1iW 同样可以算出人的队列的分布: P无人=0iWP(i,0), Pi个人=P(i,0). 3.13(b)是的
9、3.13(a)应用 3.14 3.14 (a)节点A接受所有来自节点1的包,所以当10 列出DBE,解出平稳分布,并计算系统内平稳客 户数N. 3.14 源1的packet从到达系统到离开的平均时间T1=1/+N(1/)= (1+N) (1/); 源1的packet在系统内的平均数为: N1=1T1 设N为系统内客户数当到达客户要排队时,剩余服 务时间为1/m;客户要排队的概率为PQ,所以,有书上结 论.另外只有server全忙时优先级才起作用,这时系统可 视为M/M/1优先级队列,服务率为m, 平均剩余服务时 间为R=PQ/m. (b) 被中断并退回到队列的客户,再次对它服务时,服务 时间要
10、求仍是指数的,所以实际上等价于2个客户做个 交换; 又因它们是独立同分布的指数服务,交换对系统 的统计性质无影响. 所以,系统相当于M/M/m ,到达率为 =1+k ,服务率1/m. W(k) 定义为前k类客户的平均等待时间. 定义 类k 客户在队列内的平均数; 前k类客户在队列内的平均数; 有： (1) 应用Littles 定理有： 和 , 代入(1)即可得到所要证明的公 式. = )(k Q N = k Q N ) 1()( += k Q k Q k Q NNN )(1 )( )( kk k Q WN+= ) 1(11 ) 1( )( += kk k Q WN kk k Q WN= 3.3
11、9 111+2 首先,类2客户的平均延迟为.另外, 类2 客户的吞吐率为 客户/秒. 剩余服务时间R应按下式计算(回忆图形 证明): 类1客户平均延迟w1=R/(1-1) 2 1 1 X d = )( 2 1 2 2 2 11 XdXR+= 习题3.54 利用马氏链的可逆性描述M/M/1/m队列 的离开过程 1）M/M/1/m队列是可逆的，因此离开过程与逆向 链的到达过程相同。 到达过程是泊松过程但是顾客以Pm的概率不能计 入系统，因此外部有效到速率为（1-Pm）。 因此离开过程也是泊松过程，速率为 （1-Pm）。 3.65题(见讲稿和例题3.21-22) 证明: 不妨设 Server1的利用率 利用乘积形式(3.152) 11 )(=m ), 0(1)( 2 21 =+ = Mnn K K nnpMU
