馬爾可夫骨架過程在PERT網(wǎng)絡(luò)中的應(yīng)用

1、孔祥星孔祥星合作者：張玄、侯振挺合作者：張玄、侯振挺中中 南南 大大 學(xué)學(xué)20122012年年5 5月月2727日日2012年年“隨機圖與復(fù)雜網(wǎng)絡(luò)隨機圖與復(fù)雜網(wǎng)絡(luò)” 學(xué)術(shù)研討學(xué)術(shù)研討會會統(tǒng)籌方法統(tǒng)籌方法 想泡壺茶喝。當(dāng)時的情況是：沒有開水，開水壺要洗，茶壺茶杯要洗，茶葉沒有拿，怎么辦？bstcd12345活動1（洗茶壺）需要1分鐘，活動2（燒開水）需要15分鐘，活動3（洗茶壺）需要1分鐘，活動4（洗茶杯）需要1分鐘，活動5（拿茶葉）需要2分鐘。 在華羅庚先生所提的統(tǒng)籌方法中，項目中每個活動的持續(xù)時間是固定的，只要安排好工序就可以求出項目的完工時間。后來有人假設(shè)項目中每個活動的持續(xù)時間是相互獨立

2、服從負指數(shù)分布的隨機變量，可用馬氏鏈來研究項目的完工時間分布。我們進一步把每個活動的持續(xù)時間推廣為相互獨立服從一般分布的隨機變量，把每個活動已實施的時間作為補充變量，從而構(gòu)建一個帶有吸收態(tài)的馬爾可夫骨架過程，通過其向后方程得到了pert網(wǎng)絡(luò)完工時間分布的解析表達式。pert網(wǎng)絡(luò)網(wǎng)絡(luò) 用 表示一個具有一個源點s和一個匯點t的有向非循環(huán)網(wǎng)絡(luò)，其中， 表示節(jié)點（事件）集， 表示?。ɑ顒樱┑募?，對于任意個一個活動 ，其持續(xù)時間是服從一般分布的隨機變量。令 表示弧 的起點， 表示弧 的終點，一條 有向路徑是一個弧序列 且弧序列滿足如下的條件 ， 且 。),(avg mvvvv,21naaaa,21aa

3、)(aa)(aa),( ts),(21kaaasa)(1tak)(kiaaii, 3 , 2),()(1pert網(wǎng)絡(luò)網(wǎng)絡(luò)定義定義1 令 和 分別表示以節(jié)點 為起點和終點的弧的全體，分別可以表示如下：定義定義2 設(shè) ， ，則 割集定義為如果一個 割集 是空集，則稱 為一致有向割集。 )(vi)(vo( ):( )(),( ):( )().o vaaavvvi vaaavvvvxsxvxt),( ts.)(,)(:),(xaxaaaxx),( ts),(xx),(xxpert網(wǎng)絡(luò)網(wǎng)絡(luò)v定義定義3 在項目的實施過程中，在時刻每個活動都會處于活動、休眠的或空閑的三種狀態(tài)之一： （1）活動：如果某個活動

4、在時刻t正在施工則稱該活動處于活動的狀態(tài)。 （2）休眠：如果某個活動 已經(jīng)完工，但是 中的活動沒有都完工，此時 中的活動不能開始施工，稱 處于休眠的狀態(tài)。 （3）空閑：如果某個活動既不是活動的也不是不活動的，則稱為空閑的。)(ai)(aopert網(wǎng)絡(luò)網(wǎng)絡(luò)aa 設(shè) 是pert網(wǎng)絡(luò) 的一條路徑，路徑 的 完 工 時 間 很 明 顯 不 一 定 等 于 各 個 活 動 的完工時間之和。為了計算路徑 的完工時間分布，可采用如下的方法，令從而包含 所有活動的子圖 的完工時間等于路徑 的完工時間。 ),(21kaaalglkaaa,21l 2 , 1,),(:,1kkiaaaiaaaaaaiikkkaaa

5、a21aglpert網(wǎng)絡(luò)網(wǎng)絡(luò) 如圖（a）所示，設(shè)路徑 ，則 ，從而 。則子圖 如圖（b）所示，路徑 的完工時間與子圖 的完工時間相等。 )5 , 3 , 1 (l 35 ,a 213,4 ,1,2aa5 , 4 , 3 , 2 , 1321aaaaglgpert網(wǎng)絡(luò)網(wǎng)絡(luò)在圖(b)中所有的udc為(1,2), (2,3), (1,4), (3,4), (5)。所有udc的容許二劃分如下表所示，其中，*表示該活動處于休眠狀態(tài)。表1 如上令 和 表示所有udc中活動的和休眠的活動。對 ，令 表示活動已實施的時間，令 表示活動 的持續(xù)時間分布。則剩余efea)(ta)()(aga馬氏骨架過程馬氏骨架過

6、程時間的分布 可表示為以活動的已實施的時間 作為補充變量則表1的狀態(tài)變?yōu)楸?)()(aag)(1)()()()()()()(aaaaaaaggtgtga)(ta馬氏骨架過程馬氏骨架過程令則 是一個狀態(tài)空間為 的馬爾科夫骨架過程。令 表示 的不連續(xù)時間點（在時刻 有一個活動完工），則 是馬氏骨架過程 的骨架時序列。 為了表述的方便，把表2中10個狀態(tài)分別用1,2，10來表示，馬爾科夫骨架過程 在完成狀態(tài)1后轉(zhuǎn)移到狀態(tài)2或4或6，完成某項活動 ., 0*32, 0, 032, 0, 021e)(txe, 0210rrr )(tx) 1( nrn) 1( nrn)(tx)(tx馬氏骨架過程馬氏骨架過

7、程后繼續(xù)向后轉(zhuǎn)移，最終到達狀態(tài)10，從而整個項目完成。馬爾科夫骨架過程的狀態(tài)轉(zhuǎn)移示意圖如下所示：馬氏骨架過程馬氏骨架過程令 表示pert網(wǎng)絡(luò)的完工時間，則可以通過馬爾科夫骨架過程的向后方程計算項目工期 的分布。 令 表示從狀態(tài)9轉(zhuǎn)移到狀態(tài)10的完工時間分布，其中活動5已實施的時間長度為 ，則 t)0 , 0 , 2 , 1 ()0(| ),()(, 0minxtxttttptf)(),(59tf5 ).(:)(),( ,),(),( ,), 5(),( ,), 5(),()5(0)5(0555955tgsdgstpdsqtptftt馬氏骨架過程馬氏骨架過程 令 表示從狀態(tài)8轉(zhuǎn)移到狀態(tài)10的完工

8、時間分布，其中活動3已實施的時間長度為 ，則),(38tf3 . )()(),( ,),0 , 5()0 , 5( ,),*,4 , 3(),( ,),*,4 , 3(),(0)3()5(0033383ttsdgstgstpdsqtptf馬氏骨架過程馬氏骨架過程 令 表示從狀態(tài)1轉(zhuǎn)移到狀態(tài)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、夫骨架過程從狀態(tài)1轉(zhuǎn)移到狀態(tài)10的時間。 )5 , 3 , 1 (lg), 0 , 0()(1tfttptf, )()(0ttdfte220( )( )( )var tt df te t馬氏骨架過程馬氏骨架過程為了說明本章所得解析結(jié)果的有效性，給出一個具體的例子，設(shè)活動5的持續(xù)時間服從參數(shù) 的 -分布，則其密度函數(shù)和剩余時間分布為設(shè)活動1,2,3,4,6的持續(xù)時間分布分別服從參數(shù)為1,2,3,4,6的負指數(shù)分布。2, 1, 0, 0, 0,)()5(xxxexfx.)(5555)5(dxxedxxetgxtx例子例子 路徑 的完工時間等于子圖 的完工時間，即馬氏骨架過程 從初始狀態(tài)1到達吸收態(tài)

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