一種模糊關鍵路徑求解新方法

摘 要：由于不能用傳統的前向計算和后向計算方法求解模糊網絡關鍵路徑，通過定義模糊必然關鍵路徑、可能關鍵路徑和不可能關鍵路徑，提出一種求解模糊關鍵路徑的新算法。該算法擴充圖的鄰接表的存儲結構，通過判斷每個子模糊網絡的關鍵路徑，當成為關鍵路徑的可能性為零時，在節點鏈表中刪除相應的節點，減少下回重復遍歷該子路徑的次數，從而提高算法執行效率。該算法數據結構形式簡單直觀，易于實現。

關鍵詞：模糊網絡計劃；關鍵路徑；必然關鍵路徑；復雜度

中圖分類號：TP399文獻標志碼：A

文章編號：1001-3695(2009)06-2050-03

doi:10.3969/j.issn.1001-3695.2009.06.015

New approach for fuzzy critical path

ZHANG Hong-guo， CHEN Shao-wen

(College of Computer Science Technology， Harbin University of Science Technology， Harbin 150080， China)

Abstract:In order to solve the question of fuzzy critical path， this article defined necessarily critical path and bound to the critical path， produced a new algorithm for critical path of the fuzzy network plan. The algorithm expanded the storage structure of adjacent table.Judging the possibility of each path became a critical path， when the possibility of a path becomes critical path was zero， removed the related node， reduced the number of judges repeated the nodes next time， thereby improving the efficiency of algorithms. The algorithm data structure was simple， and easy to realize.

Key words:fuzzy network plan；critical path；bound to the critical path；complexity

網絡計劃是一種組織生產和進行計劃管理的科學方法，通常把工程計劃表述為帶權的有向無環圖，節點表示事件，以有向邊表示活動，邊上的權值表示該活動的持續時間。在工程項目計劃管理中，為了進行人力、物力的調試和分配、縮短工期，往往需要求解網絡的總工期，而求解網絡的總工期實際上就是網絡關鍵路徑的求解。

文獻[1]提出了利用圖的廣度優先搜索與動態規劃算法相結合求解關鍵路徑的新算法。該算法采用圖的鄰接表結構形式，不需要進行拓撲排序，較之傳統算法具有較高的效率，同時具有較高的健壯性。但該算法只能找出關鍵路徑，并不能找出可能關鍵路徑。文獻[2]提出的算法不需要進行網絡計劃的拓撲排序，算法執行效率有一定的提高，但采用十字鏈表作為存儲結構，顯得比較復雜，需要對圖進行三次廣度優先搜索，可以輸出所有的關鍵活動，但同樣沒能把所有的關鍵路徑輸出。文獻[3]在深度優先搜索的基礎上，求出從源點到匯點的所有路徑，經過分析比較后找出最長的路徑，從而求取關鍵路徑。由于在求解過程中需要進行多次遞歸回溯，算法的執行效率低。文獻[4]把Soroush的“最關鍵路徑”概念用于模糊網絡計劃中，利用模糊推理實現對整個計劃按期完工可能性的估計。通過引用一些特殊的路徑形式把MCP的求解問題轉換為系統的有向無環圖的最長路問題，從而求解模糊網絡的關鍵路徑，但算法是一個迭代過程，執行效率較低，并且不能計算出可能關鍵路徑。文獻[5]提出模糊網絡中K度工序的概念。為分析K度工序的差別問題，給出了一般工序的若干性質，結合分析K度工序的需要，討論了模糊數的序關系，基于工序性質和模糊數序關系對模糊關鍵路徑進行判斷。

傳統的求解模糊關鍵路徑算法存在以下不足^[6~11]：a）算法需要分別求出所有事件的最早和最遲開始時間以及每項活動的最早和最遲結束時間，而在模糊數的計算當中，模糊數的減法并不是模糊數加法的逆運算，運算模糊減法使工序時間越來越模糊，并有可能產生負的工序時間參數，而負的時間參數在模糊數中是沒有意義的，從而不能準確地計算出模糊網絡計劃的最遲開始時間和最遲結束時間。b）對于模糊網絡，目前較常用的方法是分析每條路徑的關鍵度，關鍵度越高的路徑越有可能成為關鍵路徑。但從關鍵度的角度判斷關鍵路徑，在實際應用中，尤其是對大型網絡，其計算量很大，通過逐一計算每個路徑的關鍵度來確定關鍵路徑是十分困難的。

1 基本概念和理論基礎

定義1 G=〈V，E，W〉中vi∈V，設succ(vi)為節點vi的后續節點，prod(vi)為節點vi的前續節點，|succ(vi)|為節點vi的后續節點個數，|prod(vi)|為節點vi的前續節點個數。當succ(vi)=，節點vi為收點，當prod(vi)=，節點vi為發點。

定義2 G=〈V，E，W〉為n階有向帶權圖，滿足V是簡單圖，V中無環，有一個節點入度為0，稱為發點，有一個節點出度為0，稱為收點；邊〈vi，vj〉帶的權記為wi，wi為模糊數。在此模糊網絡中求關鍵路徑即求從發點到收點的一條最長路徑。

定義3 一條路徑中，若出現的節點互不相同，稱為基本路。廣度優先搜索從圖的某個頂點出發，依次搜索其鄰接點，然后從這些鄰接點出發依次訪問它們的鄰接點，直到結束。

定義4 在一個模糊網絡中，有n條基本路，當其中某條路徑周期的模糊數的下界值大于其他任何路徑周期的模糊數的上界值時，這條路徑是模糊網絡的必然關鍵路徑。

定義5 在一個模糊網絡中，有n條基本路，其中幾條路徑周期的模糊數存在公共子集，由于都是模糊數，無法明確區別各數值的大小，這幾條路徑是模糊網絡的可能關鍵路徑。

定義6 在一個模糊網絡中，有n條基本路，其中某條路徑周期的模糊數的上界值小于其他任何路徑周期的模糊數的下界時，這條路徑是模糊網絡的不可能關鍵路徑。

定義7 W=(w1，w2，…，wn)為模糊數集合，wS代表模糊數的下界，wB代表模糊數的上界，wP代表模糊數最可能值。

定義8 L=〈M，W〉，M為網絡中各路徑名稱集合，mi∈M（i=1，2，…，W）為路徑周期集合，wi∈W（i=1，2，3，…，n）。

定理1 在三角模糊網絡計劃中，如果各路徑周期存在交叉部分，則這些路徑為可能關鍵路徑。

證明 wi為三角模型數，表示為wi=(wsi，wpi，wbi)，當某個模糊數的上界大于另一個模糊數的下界時，由于三角模糊數的持續時間是一個范圍的時間區域，根據這一特點，其中一個值都有可能比另一個值大，這些路徑為可能關鍵路徑。

2 算法設計

2.1 數據結構

為了使圖的存儲與算法求解過程相適應，對傳統圖的鄰接表結構進行擴展，使圖V的鄰接表用于存儲圖各相關基本路的模糊路徑的持續時間。存儲結構設計如下：

a)表頭節點表。同所有表頭節點以鏈式結構的形式存儲，以便在判斷過程中對模糊網絡各節點的刪除。

Typedef struct CodeHead{

Struct fvex *fnext;

Floatw0，w1，w2;

//分別用于存儲三角模糊數的最小值、最可能值、最大值

StructcriticalPathLen*next;

}*CodeHead;

b)路徑周期表。由圖V中入度節點不為1的節點的鄰接關系的邊組成。

Typedef struct criticalPathLen{

Int nodeno;//用于存儲各節點的代號

Float w0，w1，w2;/*用于存儲各可能關鍵路徑的三角模糊數的最小值、最可能值、最大值*/

Struct criticalPathLen*next;

}*criticalPathLen;

c)前序節點表。由指向下一前序點的鏈域和前序節點序號組成。

typedef struct fvex{

Struct fvex *next;

Intnodeno;//節點編號

}*fvex;

2.2 主要算法思想

求出模糊網絡計劃|prod(vi)|＞1的節點，并分別判斷該節點與發點所形成的子網絡，應用模糊數的特點，分別判斷各子路徑為關鍵路徑、可能關鍵路徑和不可能關鍵路徑。當存在不可能關鍵路徑時刪除不可能關鍵路徑的相關節點，從而達到減枝效果。在整個模糊網絡中，每個節點都不發生重復遍歷，并將已計算的路徑長度保存在鄰接表中，而減少重復計算周期長度，提高程序的運行效率。 

2.3 算法流程

a)初始化節點鏈表，將模糊網絡計劃中除收點和發點后的所有節點通過廣度搜索遍歷，用鏈表連接起來形成鏈表L1。

b)模糊網絡計劃中，如果|prod(vi)|＞1（i=1，2，…，n），以vi為節點形成鏈表L2。

c)根據鏈表L2的節點順序，依次對該節點與發點所組成的子網絡進行遍歷，并計算各路徑周期，L=〈M，W〉。運用三角模糊數相加的原則分別計算子網絡各條路徑的周期并比較：

（a）當wsi＞max(wb1，wb2，…，wb(i-1)，wb(i+1)，…，wbn)時，mi為必然關鍵路徑，并從鏈表L1中刪除其他路徑上與此路徑無關的節點。

（b）當wsi=max(wb1，wb2，…，wb(i-1)，wb(i+1)，…，wbn)

時，mi為可能關鍵路徑。

(c)當wbi＜min(ws1，ws2，…，ws(i-1)，ws(i+1)，…，wsn)時，mi為不可能關鍵路徑，在鏈表L1中刪除此路徑與其他路徑不相交的節點。

（d）當wbi=min(ws1，ws2，…，ws(i-1)，ws(i+1)，…，wsn)時，mi為可能關鍵路徑。

(e)除(a)~(d)四種情況外，根據定理1，則這些路徑為可能關鍵路徑。

(f)存在多條可能關鍵路徑時，對各路徑進行排序，依次為最可能關鍵路徑、次可能關鍵路徑。d)輸出模糊網絡必然關鍵路徑和所有的可能關鍵路徑及路徑周期。

3 實例驗證及分析比較

3.1 實例驗證

本文引用文獻[12]中的例子，如圖1所示，圖中共有7個節點，10項工序，其中弧上的值為路徑三角模糊數周期。

求解步驟如下：

a)創建鏈表L1用于存儲模糊網絡的所有節點，包括節點2、3、4、5、6。

b)在模糊網絡中，查找|prod(vi)|＞1的節點，分別為節點3、4、6、7，并存儲于鏈表L2。

c)分別計算從發點到節點3、4、6、7各個模糊子網絡的關鍵路徑。

(a)計算節點1到3的子網絡關鍵路徑。從發點1到節點3有兩條路徑組成，即1-2-3和1-3，其路徑周期分別為(5.3，7，8.6)，(3.5，4，5)。通過判斷可知路徑1-2-3為必然關鍵路徑，路徑1-3為不可能關鍵路徑。

(b)計算節點1到4的子網絡關鍵路徑。從發點1到節點4有兩條路徑組成，分別為1-2-3-4，1-4，路徑周期分別為(9.3，12，14.9)，(5，6，7.2)。通過判斷可知路徑1-2-3-4為必然關鍵路徑，路徑1-4為不可能關鍵路徑。

(c)計算節點1到6的關鍵路徑。從發點1到節點6有三條路徑組成，分別為1-2-5-6，1-2-3-6，1-2-3-4-6，其路徑周期分別為(7.8，10，12.6)，(8.1，11，13.6)，(14.2，18，22.1)。通過判斷可知路徑1-2-3-4-6為必然關鍵路徑，并在鏈表L1中刪除節點5。

(d)計算節點1到收點7的關鍵路徑。從發點1到收點7只有一條路徑組成，1-2-3-4-6-7，其路徑周期為(18，23，28.1)。

d)求得模糊網絡的關鍵路徑為1-2-3-4-6-7及周期(18，23，28.1)。

3.2 實例分析比較

算法比較結果如表1所示。本文算法與文獻[11]的算法相比，在時間復雜度方面少一個數量級；與文獻[12]的算法相比，雖然有相同的時間復雜度，但本文算法能求出所有可能關鍵路徑。

4 結束語

本文通過定義必然關鍵路徑等概念，對圖的鄰接表的存儲結構進行擴充，提出了一種新的求解關鍵路徑的算法。算法具有如下特點：a)能高效率地求出模糊網絡中所有的必然關鍵路徑、可能關鍵路徑、關鍵路徑的持續時間以及相對應的關鍵活動；b)由于采用剪枝原理，減少了遍歷相應節點的次數，減少了在遍歷路徑時間的重復，從而使時間復雜度在很大程度上降低；c)只需要建立一個臨時存儲入度大于1的節點路徑的鄰接表，存儲空間消耗小。該算法已經應用于“網絡化制造環境下協同項目計劃與控制系統”項目中，取得了良好效果。

參考文獻：

［1］劉芳，王玲.基于動態規劃思想求解關鍵路徑的算法[J].計算機應用，2006，26(6)：1140-1142.

[2]徐鳳生.一種新的關鍵路徑求解算法[J].計算機應用與軟件，2005，22（6）：97-99.

[3]孟繁楨.求關鍵路徑的一個算法[J].計算機工程，1995，21(4)：6-9.

[4]劉春林，何建敏.模糊計劃網絡最關鍵路的求取算法[J].系統工程學報，2000，15(2)：136-142.

[5]胡勁松，達慶利.模糊網絡中K度工序分析[J].系統工程學報，1997，12（４）：78-84.

[6]王明福.一種求解關鍵路徑的新算法[J].計算機工程，2008，34(9)：106-108.

[7]CHANG I S.An efficient approach for large scale project planning based on fuzzy Delphi method[J].Fuzzy Sets and Systems，1995，7(6)：277-288.

[8]NASUTION S H.Fuzzy critical path method[J].IEEE Trans on Systems，Man and Cybernetics，1994，24(1):48-57.

[9]劉小晶.AOE網的關鍵路徑求解算法改進及其應用[J].計算機系統應用，2006(9)：47-53.

[10]潘春光，陳英武，汪浩.模糊計劃評審技術(F-PERT)中關鍵路徑的規劃解法[J].數學的實踐與認識，2004，34(8)：29-34.

[11]HUANG De-cai，ZHAO Ke-qin.Uncertainty network planning metho-dology based on the connection number a+bi+cj[C]//Proc of the 5th World Congress on Intelligent Control and Automation.2004.

[12]YAO Jin-Shing，LIN F T.Fuzzy critical path method based on signed distance ranking of fuzzy numbers[J].IEEE Trans on Systems，Man and Cybernetics，2000，30(1)：76-82.