马尔可夫骨架过程在PERT网络中的应用

1、孔祥星孔祥星合作者：张玄、侯振挺合作者：张玄、侯振挺中中 南南 大大 学学20122012年年5 5月月2727日日2012年年“随机图与复杂网络随机图与复杂网络” 学术研讨学术研讨会会统筹方法统筹方法 想泡壶茶喝。当时的情况是：没有开水，开水壶要洗，茶壶茶杯要洗，茶叶没有拿，怎么办？bstcd12345活动1（洗茶壶）需要1分钟，活动2（烧开水）需要15分钟，活动3（洗茶壶）需要1分钟，活动4（洗茶杯）需要1分钟，活动5（拿茶叶）需要2分钟。 在华罗庚先生所提的统筹方法中，项目中每个活动的持续时间是固定的，只要安排好工序就可以求出项目的完工时间。后来有人假设项目中每个活动的持续时间是相互独立

2、服从负指数分布的随机变量，可用马氏链来研究项目的完工时间分布。我们进一步把每个活动的持续时间推广为相互独立服从一般分布的随机变量，把每个活动已实施的时间作为补充变量，从而构建一个带有吸收态的马尔可夫骨架过程，通过其向后方程得到了pert网络完工时间分布的解析表达式。pert网络网络 用 表示一个具有一个源点s和一个汇点t的有向非循环网络，其中， 表示节点（事件）集， 表示弧（活动）的集合，对于任意个一个活动 ，其持续时间是服从一般分布的随机变量。令 表示弧 的起点， 表示弧 的终点，一条 有向路径是一个弧序列 且弧序列满足如下的条件 ， 且 。),(avg mvvvv,21naaaa,21aa

3、)(aa)(aa),( ts),(21kaaasa)(1tak)(kiaaii, 3 , 2),()(1pert网络网络定义定义1 令 和 分别表示以节点 为起点和终点的弧的全体，分别可以表示如下：定义定义2 设 ， ，则 割集定义为如果一个 割集 是空集，则称 为一致有向割集。 )(vi)(vo( ):( )(),( ):( )().o vaaavvvi vaaavvvvxsxvxt),( ts.)(,)(:),(xaxaaaxx),( ts),(xx),(xxpert网络网络v定义定义3 在项目的实施过程中，在时刻每个活动都会处于活动、休眠的或空闲的三种状态之一： （1）活动：如果某个活动

4、在时刻t正在施工则称该活动处于活动的状态。 （2）休眠：如果某个活动 已经完工，但是 中的活动没有都完工，此时 中的活动不能开始施工，称 处于休眠的状态。 （3）空闲：如果某个活动既不是活动的也不是不活动的，则称为空闲的。)(ai)(aopert网络网络aa 设 是pert网络 的一条路径，路径 的 完 工 时 间 很 明 显 不 一 定 等 于 各 个 活 动 的完工时间之和。为了计算路径 的完工时间分布，可采用如下的方法，令从而包含 所有活动的子图 的完工时间等于路径 的完工时间。 ),(21kaaalglkaaa,21l 2 , 1,),(:,1kkiaaaiaaaaaaiikkkaaa

5、a21aglpert网络网络 如图（a）所示，设路径 ，则 ，从而 。则子图 如图（b）所示，路径 的完工时间与子图 的完工时间相等。 )5 , 3 , 1 (l 35 ,a 213,4 ,1,2aa5 , 4 , 3 , 2 , 1321aaaaglgpert网络网络在图(b)中所有的udc为(1,2), (2,3), (1,4), (3,4), (5)。所有udc的容许二划分如下表所示，其中，*表示该活动处于休眠状态。表1 如上令 和 表示所有udc中活动的和休眠的活动。对 ，令 表示活动已实施的时间，令 表示活动 的持续时间分布。则剩余efea)(ta)()(aga马氏骨架过程马氏骨架过

6、程时间的分布 可表示为以活动的已实施的时间 作为补充变量则表1的状态变为表2)()(aag)(1)()()()()()()(aaaaaaaggtgtga)(ta马氏骨架过程马氏骨架过程令则 是一个状态空间为 的马尔科夫骨架过程。令 表示 的不连续时间点（在时刻 有一个活动完工），则 是马氏骨架过程 的骨架时序列。 为了表述的方便，把表2中10个状态分别用1,2，10来表示，马尔科夫骨架过程 在完成状态1后转移到状态2或4或6，完成某项活动 ., 0*32, 0, 032, 0, 021e)(txe, 0210rrr )(tx) 1( nrn) 1( nrn)(tx)(tx马氏骨架过程马氏骨架过

7、程后继续向后转移，最终到达状态10，从而整个项目完成。马尔科夫骨架过程的状态转移示意图如下所示：马氏骨架过程马氏骨架过程令 表示pert网络的完工时间，则可以通过马尔科夫骨架过程的向后方程计算项目工期 的分布。 令 表示从状态9转移到状态10的完工时间分布，其中活动5已实施的时间长度为 ，则 t)0 , 0 , 2 , 1 ()0(| ),()(, 0minxtxttttptf)(),(59tf5 ).(:)(),( ,),(),( ,), 5(),( ,), 5(),()5(0)5(0555955tgsdgstpdsqtptftt马氏骨架过程马氏骨架过程 令 表示从状态8转移到状态10的完工

8、时间分布，其中活动3已实施的时间长度为 ，则),(38tf3 . )()(),( ,),0 , 5()0 , 5( ,),*,4 , 3(),( ,),*,4 , 3(),(0)3()5(0033383ttsdgstgstpdsqtptf马氏骨架过程马氏骨架过程 令 表示从状态1转移到状态10的完工时间分布，其中活动1和2已实施的时间长度分别为 和 则2q112(, )ft 1马氏骨架过程马氏骨架过程() () ()()1122112121222012110(1)(1)(2)(2)( , , )(1,2, , ), ,( , )(1,2, , ), ,(2,3,0)(2,3,0),( , )(

9、1,2, , ), ,(1,4,0)(1,4,0),( , )( )()( )()(3,4,0,0),(ttftptqdsspstsqdsspstsgsgsgsgsptsqqqqq qq qf fq qqqf fq qqqf ff=+-+-+-()()()()21121122(2)(1)220(1)(2)410(1)(1)(2)(2)6, )1( )(,0,)( )1( )(,0,)( )( )()( )()(0,0,) .s ttts tgs fsts dgsgs fsts dgsgsgsgsgsftsqqqqqqqqfqq=-+-+-+-+- 路径 的完工时间等于子图 的完工时间，即马尔科

10、夫骨架过程从状态1转移到状态10的时间。 )5 , 3 , 1 (lg), 0 , 0()(1tfttptf, )()(0ttdfte220( )( )( )var tt df te t马氏骨架过程马氏骨架过程为了说明本章所得解析结果的有效性，给出一个具体的例子，设活动5的持续时间服从参数 的 -分布，则其密度函数和剩余时间分布为设活动1,2,3,4,6的持续时间分布分别服从参数为1,2,3,4,6的负指数分布。2, 1, 0, 0, 0,)()5(xxxexfx.)(5555)5(dxxedxxetgxtx例子例子 路径 的完工时间等于子图 的完工时间，即马氏骨架过程 从初始状态1到达吸收态

11、10的时间。完工时间的分布、期望与方差如下：)5 , 3 , 1 (lg)(tx,432435325287913257211)(223457tttttttteteteeeeeetf,5119. 3)()(0ttdfte.9910. 2)()()(202tetdfttvar例子例子1 kulkarni v., adlakha v. markov and markov-regenerative pert networks. operations research, 1986, 34:7697812 azaron a., katagiri h., sakawa m., et al. multi-ob

12、jective resource allocation problem in pert networks. european journal of operational research, 2006, 172:8388543 azaron a., tavakkoli-moghaddam r. a multi-objective resource allocation problem in dynamic pert networks. applied mathematics and computation, 2006, 181:1631744 azaron a, katagiri h, kato k, etal. longest path analysis in network of queues. european journal of operational research, 2006