,西北工業大學管理學院，西安nt,,Xi’,,.bject-.,2016,52（4）：234-237.：,.,ities；,.,.：s;-;m;鍵詞：活動網絡圖；面向對象；關鍵路徑算法；編碼文獻標志碼：A中圖分類號：：10.3778/j.issn.1002-8331.1505-0256引言隨著計算機科學技術的發展，圖論和計算機網絡的聯系日益密切，各個領域的許多問題都可以抽象成數學中的圖模型，圖論已成為一種分析和解決問題的有效工具。
目前，圖論在管理、交通運輸、軍事、計算機科學、互連網絡及社會科學中都顯示出了處理復雜問題能力[1-2]最短路徑、最小生成樹、拓撲排序和關鍵路徑等經典問題，是圖論在實踐中的典型應用。項目活動網絡圖（，AN）做為一種典型的圖形數據結構，在項目管理領域被廣泛使用，是網絡計劃技術的基礎[3-4]；此外，基于活動網絡技術的項目進度安排方法更是項目管理科學性的集中體現[5-6]。同時，項目活動網絡圖還是項目調度優化算法得以實現的基礎，如遺傳算法、模擬退火、禁忌搜索等智能優化算法[7-9]。因此，項目活動網絡圖的數據結構表示和編碼實現對項目進度管理很關鍵[10]在傳統的數據結構書中，主要采用鄰接矩陣或鄰接表的形式表示項目的活動網絡圖[11]。當采用鄰接矩陣時，需要開辟表示活動個數）個空間來存儲網絡結構；采用鄰接表時需要定義頂點表和邊表，每個表中都包含了指針，因而增加了編程的復雜性。此外，采用鄰接矩陣和鄰接表生成活動網絡圖都基于結構化的程序設計思路，編碼過程非常繁瑣[12-13]較大時，存儲基金項目：陜西省自然科學基金（No.）；陜西省社會科學基金（No.）；西北工業大學管理振興基金（No.）；北工業大學研究生創意創新種子基金（No.）。
作者簡介：張靜文（1976—），女，博士，副教授，研究領域為項目調度、優化算法，E-mail：；周杉（1990—），碩士研究生在讀，研究領域為項目調度優化。收稿日期：2015-05-28修回日期：2015-10-13文章編號：1002-8331（2016）04-0234-網絡優先出版：2015-10-16,效率和計算效率都很低，這主要因為結構化的程序設計將數據和操作分開，孤立地處理問題，記錄每個節點的狀態，因此維持各個節點的關系就更加麻煩。對于目前國際上非常流行的優化軟件包ILOG/CPLEX來說，其中采用了嵌套的結構體變量表示活動網絡圖[14-15]。因此，本文研究基于面向對象的項目活動網絡圖表示和關鍵路徑算法的編碼實現。采用Aon（-no-node）的方式，有向無圈的項目活動網絡圖記為。網絡圖僅有一個源節點和一個終節點，對應節點別表示虛的開始活動和虛的結束活動，它們不消耗時間和資源。Aon活動網絡圖的面向對象分析面向對象的分析和設計，注重從宏觀上考慮問題，把對問題論域和系統的認識抽象為規范的對象和對象之間的消息傳遞。
對象封裝了數據和操作，數據與操作緊密結合，對象互訪非常方便，這些都為用面向對象的思想來解決一些經典問題提供了有利條件[16]Aon活動網絡圖中，節點表示的活動可以抽象為類。不同的項目網絡圖中，活動的數目有差別，因此需要使用動態數組表示網絡圖中的活動；同時，每個活動的緊前活動和緊后活動數目也不固定，也需要使用動態數組來記錄每個活動的緊前和緊后活動；活動本屬性包括：序號id、工期、緊前活動、緊后活動。為了標記某個活動是否已被訪問，來設置活動的緊前緊后關系；用以查詢網絡中活動的數目。對類的操作如下：（）；~（）；（*（，）；（*a，**（）；*（）；（）；（）；：rray；關鍵路徑算法的面向對象實現3.1關鍵路徑算法描述關鍵路徑算法是為了找出活動網絡中的關鍵活動和關鍵路徑于關鍵路徑上的關鍵活動決定項目工期網絡圖中關鍵路徑是最短的一條路徑，是項目實施過程中需要關注的重點。
通常根據一個活動的總時差（total float）判斷它是否是關鍵活動。活 的總時差tf 的活動是關鍵活動。關鍵路徑算法分為兩個階段：正向拓撲計 算和逆向拓撲計算，具體表述如下： 步驟 0。根據網絡結構的拓撲次序，從前向后依次地計算每個活動的 es ，計算公式為：es 增加一個bool 成員變量 。 在后面的關鍵路徑算 ef es 始時間es 、最早結束時間ef 、最晚結束時間lf 、最晚開lf ，根據網絡結構的逆拓撲次序，從后向前依次地始時間 ls 和總時差tf 個時間參數也作為 計算每個活動 lf ls，計算公式為： VC++中提供了動態數組 類，它能夠實現 lf lslf 以方便地完成網絡圖訪問所需要的功能。使用 動態數組表示活動網 絡中的所有活動 是一個存儲 指針型的數組 ， 定義如下： ； 將活動網絡圖抽象為 CAc- 動態數組 表示網絡圖中的所有活 提供 個成員函數： 對象中添加一個活動； 根據公式tf ，獲得關鍵活動和關鍵路徑。
在第一階段正向拓撲算法中，根據網絡節點遞增的 拓撲次序，對于每個節點，需要檢查此節點的所有緊前節 同樣地，在第二階段的后向拓撲算法中，檢查節點的順 序正好 與第一階段相反，并且檢查每個節點的所有緊后 節點各一 次，所以其計算復雜性仍為 。綜上所述，關鍵路徑算法的計算復雜性為 3.2關鍵路徑算法實現 創建 對象 aon，依次創建多個 對象并通過 成員函數添加到 aon 絡圖表示的活動間的邏輯關系，通過 設置活 動之間的緊前緊后關系，至此完成了網絡圖的初始化。 類表示關鍵路徑，將前面創建的網 圖對象aon 賦值給 于每個活動都保存了它的緊前活動和緊后活動 先使用一個FIFO 隊列 來記錄正向拓撲序列，將開始 活動進入隊列中；然后從隊列中取出 top 活動，依次遍歷 該活動的緊后活動，判斷緊后活動的所有緊前活動是否 已經遍歷過，即 是否為 true，如果是，計算該緊后 活動的 es ，并將該緊后活動進入隊列，然后再依次取出隊列的 top 活動，繼續遍歷，直到隊列為空為止。
設 計正向拓撲計算的代碼如下： void ：：（） * a=aon->Get （）； >=t rue； a->es=0； a->ef=0； CAct act ； .push（a）； while（!.empty（）） * a=（ *）.fron（t inti=0；.Get Size（）；i++） * >[i]； > ed（）） intst art ime=0；fo（r int k=0；.Get Size（）；k++） start [k]->ef） st art_t ime=b-> ives[k]->ef； b->es=start ime；b->ef=b->es+b- >durat ion； b->visit ed=t rue； .push（b）； 給出了關鍵路徑兩階段算法的靜態結構圖，描述了算法中的類及類的屬性和方法，以及類之間的關系。
類表示網絡圖 ， 類表示網 圖中的活動，因而 包含有多個 。 動是否被訪問等信息。兩個布爾函數 ，用來判斷某個活動 緊前活動是否全都遍歷和緊后活動是否全都遍歷。在 中使用 數組表示有多個活動， 數組中存放的是 對象指針 包括 （添加活動到網絡圖）、（定 系）函數以及（計算網絡中活動數）函數。 是兩階段算法類，包含有一個 包含有（正 向拓撲計算） 算法實現的靜態圖 -id int- int- - -es int-ef int-ls int- bool+(in id int)+ ed() bool+d() - + ve(in *)+ ation(in *)+ ation(in int)+Get AonSi ze() -aon * +(in aon *) + ogy() + ogy() 數 可以正向串行調度計算出每個活動的 最早開始時間、最早結束時間以及活動網絡的總工期； 通過函數 可以逆向調度計算出每個 活動的最晚結束時間、最晚開始時間以及總時差；進一 步根據每個活動的總時差判斷出關鍵活動和關鍵路徑。
在每個類對象的屬性或操作中，“-”表示私有成員變量 或者私有成員函數（），“+”表示公有成員變量或 者公有成員函數（），“#”表示保護成員變量保或者 護成員函數（）。 3.3 面向對象技術的優勢分析 采用面向對象的類存儲活動網絡圖的空間復雜度 相比，前者較多地節省了存儲空間。當采用面向對象的類存儲活動網絡圖時，關鍵路徑算法的計算 復雜性為 用鄰接矩陣存儲活動網絡圖時，為了計算某個活動的最早開始時間 es （或最晚結束時間 lf 個活動都檢查一次，導致關鍵路徑算法的計算復雜性為 。但是，當計算某個活動的 es ，實質僅需檢查其每個緊前活動各一次；當計算某個活動的 lf ，實質僅需檢查其每個緊后活動各一次。因此，基于鄰接矩陣存儲活動網絡圖將使得 后續關鍵路徑算法的計算復雜性增加。雖然采用鄰接 表存儲活動網絡圖的空間復雜度也為 ，但是鄰接表的定義和訪問操作需要使用指針，計算和編程較麻 采用面向對象的類存儲網路圖可以避免使用指針，從而降低了計算和編程的復雜性。所以，基于面向 對象的活動網絡圖表示和關鍵路徑算法的實現，對開發 項目管理軟件和實現項目調度優化算法都具有較好的 指導作用；同時，本文的編程方法對解決圖論中的其他 問題也具有較好的推廣價值。
結論面向對象的思想符合人們的思維習慣和當前軟件 構建的潮流，本文探討了基于面向對象技術存儲項目的 活動網絡圖和實現關鍵路徑算法，提出采用面向對象的 類表示活動；進一步，設計了基于面向對象技術實現關 鍵路徑算法的代碼；從理論上分析了采用面向對象技術 的優勢。結論表明，基于面向對象的活動網絡圖表示和 實現關鍵路徑算法，在存儲空間復雜性和計算復雜性兩 方面都比傳統的處理方式有較大程度的降低。關鍵路 徑方法沒有考慮資源限量，本文后續將研究資源約束下 項目進度計劃安排方法的面向對象實現技術。 參考文獻： 王麗.圖論在算法設計中的應用[D].陜西西安：西安電子科 技大學，2010：5-9. 計算機工程與應用，2015，51（13）：235-250. ， F.A solut ion ical pat ime- act ivity net work[J]. ers ，2010，37（9）：1557-1569. 李星梅，張倩，乞建勛，等.對具有時間轉換約束網絡模型的特征研究[J].中國管理科學，2013，28（3）：394-402. ，，et al.Time - relat wit ers[J]. ，2012， 219（1）：59-72. 重復性項目調度與網絡模型轉換方法研究[J].管理科學學報，2014，17（6）：49-59. 調度模型研究[J].揚州大學學報：自然科學版，2014，17（4）：51-55. 王宏，林丹，李敏強.一種求解多目標資源受限項目調度的 遺傳算法[J].計算機工程與應用，2008，44（7）：1-4. 版社，2010：62-92.[10] .陜西西安：西安交通大學出版社，2015：272-276. [11] 嚴蔚敏，吳偉民.數據結構（C 語言版）[M].北京：清華大學 出版社，2007：156-192. [12] 計算機時代，2008 （4）：11-12. [13] 徐長盛，謝立.關鍵路徑算法的面向對象解決[J].計算機應 研究，2005，22（4）：96-97.[14] LiuS網絡圖中關鍵路徑是最短的一條路徑，Wang M.An - ed met wit ics[J].Pro- duct ion ： Oper-， 2010，11（5）：434-442. [15] Peng W，Huang M.A crit ical chain met hod based ion [J].Int er- nat ional ，2013，52（13）：3940-3949. [16] 譚浩強.C++面向對象程序設計[M].北京：清華大學出版社， 2006：37-66.