劉電臺(tái)++趙衛(wèi)東

摘要：隨著雙代號(hào)工程網(wǎng)絡(luò)圖的影響日益廣泛，手工繪制難以滿足需求。該文通過分析雙代號(hào)網(wǎng)絡(luò)圖的特點(diǎn)，提出了虛工序確定算法，并能很好的刪除冗余虛工序，通過對(duì)傳統(tǒng)經(jīng)緯線布局方法的研究，提出了改進(jìn)的分層分級(jí)方法，較好地解決了布局問題。通過提供工序和工序之間邏輯關(guān)系的信息，便可自動(dòng)生成虛工序，自動(dòng)對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，并對(duì)節(jié)點(diǎn)進(jìn)行布局，該方法具有效率高、產(chǎn)生交叉點(diǎn)少和結(jié)構(gòu)簡(jiǎn)單等特點(diǎn)，能夠繪制出更加簡(jiǎn)單清晰而又美觀的工程網(wǎng)絡(luò)圖。

關(guān)鍵詞：雙代號(hào)工程網(wǎng)絡(luò)圖；節(jié)點(diǎn)；虛工序；緊前工序；緊后工序

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）17-0236-02

Abstract： As the impact of Activity-on-arrow Network increasingly widespread， hand-painted is difficult to meet the demand.By analyzing the characteristics of the Activity-on-arrow Network， this paperproposes a algorithm to determine the dummy activities. It can delete the redundant dummy activities very well. Through the research on the traditional method of the layout of the warp and weft lines， this paper presents an improved hierarchical classification method. It is better to solve the layout problem.By providing the information of the logical relation between the nodes and the nodes， the dummy activities can be automatically generated. It can automatically number the nodes， and places the layout of nodes. The method has the advantages of high efficiency， less intersection， simple structure and so on. It can draw a more simple， clear and beautiful Activity-on-arrow Network.

Key words： activity-on-arrow network；node；dummy activity；predecessor activities；successor activities

1背景

項(xiàng)目計(jì)劃管理是項(xiàng)目管理的重要組成部分，網(wǎng)絡(luò)計(jì)劃技術(shù)則是進(jìn)行項(xiàng)目計(jì)劃管理的最具有代表性的項(xiàng)目管理技術(shù)。它是20世紀(jì)50年代末發(fā)展起來的，依其起源有關(guān)鍵路徑法（CPM）與計(jì)劃評(píng)審法（PERT）之分。雙代號(hào)網(wǎng)絡(luò)圖是網(wǎng)絡(luò)計(jì)劃技術(shù)研究的重要工具之一，它能夠非常清晰直觀地表達(dá)項(xiàng)目工序之間的時(shí)間和邏輯關(guān)系。網(wǎng)絡(luò)計(jì)劃技術(shù)技術(shù)在產(chǎn)品開發(fā)、經(jīng)營管理、生產(chǎn)組織以及日常生活的方方面面都有廣泛的應(yīng)用[1]。預(yù)定計(jì)劃任務(wù)的進(jìn)度安排，以及每個(gè)環(huán)節(jié)之間的相互協(xié)調(diào)和制約關(guān)系，都可以用網(wǎng)絡(luò)圖表示，它方便項(xiàng)目管理人員進(jìn)行定量分析。通過網(wǎng)絡(luò)計(jì)劃的分析模型以及網(wǎng)絡(luò)圖中的工序和節(jié)點(diǎn)參數(shù)，計(jì)算各工序的時(shí)間參數(shù)，并在此基礎(chǔ)上對(duì)工期、成本和資源等進(jìn)行優(yōu)化，而繪制網(wǎng)絡(luò)圖則是網(wǎng)絡(luò)計(jì)劃技術(shù)的第一步，也是非常關(guān)鍵的一步。目前國內(nèi)外網(wǎng)絡(luò)圖自動(dòng)繪制的軟件比較多，但是大多數(shù)軟件均只能繪制單代號(hào)網(wǎng)絡(luò)圖以及甘特圖。長期以來國內(nèi)一般都使用雙代號(hào)網(wǎng)絡(luò)圖進(jìn)行網(wǎng)絡(luò)計(jì)劃技術(shù)的控制實(shí)施。然而在實(shí)際應(yīng)用中，直接可以得到的僅僅是工序之間的邏輯關(guān)系，只有根據(jù)工序之間的邏輯關(guān)系對(duì)現(xiàn)有的信息進(jìn)行轉(zhuǎn)換，才能得到所需的網(wǎng)絡(luò)圖草圖，這是非常繁瑣的過程。

工程網(wǎng)絡(luò)圖能夠準(zhǔn)確地反映出各項(xiàng)工序之間的相互依賴關(guān)系和相互制約關(guān)系，把項(xiàng)目中所有工序組成一個(gè)有機(jī)的整體。隨著社會(huì)信息化的高速發(fā)展，工程項(xiàng)目越來越復(fù)雜，手工繪制的網(wǎng)絡(luò)圖難以滿足需求，通過計(jì)算機(jī)繪制網(wǎng)絡(luò)圖也越來越受到人們的迫切關(guān)注。但是計(jì)算機(jī)繪圖正處于起步階段，難以充分滿足需求，表現(xiàn)出各種不足之處，例如計(jì)算機(jī)自動(dòng)生成的網(wǎng)絡(luò)圖虛工序冗余較多，沒有進(jìn)行一定的簡(jiǎn)化刪除，而且最終生成的網(wǎng)絡(luò)圖節(jié)點(diǎn)分布不均勻、交叉點(diǎn)多[2]。本文主要針對(duì)計(jì)算機(jī)繪圖的問題進(jìn)行了相關(guān)研究，首先對(duì)網(wǎng)絡(luò)圖的結(jié)構(gòu)進(jìn)行分析，統(tǒng)籌考慮網(wǎng)絡(luò)圖的局部和全局特征，提出了雙代號(hào)工程網(wǎng)絡(luò)圖虛工序確定算法，并通過相關(guān)判斷規(guī)則刪除部分冗余的虛工序，通過改進(jìn)的分級(jí)分層方法對(duì)節(jié)點(diǎn)進(jìn)行布局，繪制出更加清晰美觀合理的網(wǎng)絡(luò)圖。

2圖的存儲(chǔ)結(jié)構(gòu)

在雙代號(hào)網(wǎng)絡(luò)圖中，每個(gè)工序都是由兩個(gè)節(jié)點(diǎn)和一條箭線構(gòu)成。對(duì)于每條工序來說，由于邊的存在使起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)成為鄰接節(jié)點(diǎn)。與節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)成為節(jié)點(diǎn)的度。在雙代號(hào)網(wǎng)絡(luò)圖中，節(jié)點(diǎn)的度分為入度和出度。入度是指以該節(jié)點(diǎn)為終點(diǎn)的有向邊的條數(shù)，出度是指以該節(jié)點(diǎn)為起點(diǎn)的有向邊的條數(shù)。由圖的定義可知，雙代號(hào)網(wǎng)絡(luò)圖的信息由兩部分構(gòu)成，它們分別是圖中節(jié)點(diǎn)的信息和描述工序的邊的信息。圖的存儲(chǔ)結(jié)構(gòu)主要是邊的存儲(chǔ)，主要分為鄰接矩陣和鄰接表兩種。本文主要使用鄰接表的結(jié)構(gòu)，它具有存儲(chǔ)靈活的特點(diǎn)，并且非常節(jié)約空間[1]。

3虛工序確定算法

虛工序的確定是繪制網(wǎng)絡(luò)圖關(guān)鍵性的步驟，本文以確定虛工序以及節(jié)點(diǎn)間的邏輯關(guān)系為首要目標(biāo)，通過輸入的各工序和工序之間的邏輯關(guān)系，來確定各節(jié)點(diǎn)和節(jié)點(diǎn)之間的邏輯關(guān)系，最終實(shí)現(xiàn)工程網(wǎng)絡(luò)圖的生成。

雙代號(hào)網(wǎng)絡(luò)圖中的虛工序并不是一項(xiàng)實(shí)際的工作，它不消耗任何時(shí)間和資源，而只是在雙代號(hào)網(wǎng)絡(luò)圖的繪制中因工序間邏輯關(guān)系的需要而增加的[3]。虛工序是用來幫助正確表達(dá)各工序間關(guān)系，避免邏輯錯(cuò)誤。任意2個(gè)節(jié)點(diǎn)之間不能有2項(xiàng)或2項(xiàng)以上的工序，故必須要引入虛工序。在雙代號(hào)網(wǎng)絡(luò)圖中，虛工序的應(yīng)用是至關(guān)重要的，但不可濫用，必須要合理使用，否則會(huì)增加很多工作量和分析計(jì)算的負(fù)擔(dān)。

通過用戶輸入所有的工序信息，然后由計(jì)算機(jī)自動(dòng)將工序和工序之間的邏輯關(guān)系轉(zhuǎn)換成節(jié)點(diǎn)和節(jié)點(diǎn)之間的邏輯關(guān)系，這樣可以大大降低用戶的工作強(qiáng)度。轉(zhuǎn)換的過程比較繁雜，涉及用來表述工序之間邏輯關(guān)系的虛工序的添加，合理添加虛工序決定了雙代號(hào)網(wǎng)絡(luò)圖是否正確與簡(jiǎn)潔，虛工序的添加應(yīng)該符合相應(yīng)的原則。下面將對(duì)各個(gè)工序，按照先后排列次序進(jìn)行信息轉(zhuǎn)換，進(jìn)而確定各工序的首尾節(jié)點(diǎn)號(hào)[4～6]。

1）首先要處理無緊前工序的工序，將所有無緊前工序的工序首節(jié)點(diǎn)均編號(hào)為1，尾節(jié)點(diǎn)依次增加進(jìn)行編號(hào)，用m保存當(dāng)前最大的節(jié)點(diǎn)編號(hào)，繼續(xù)處理其他工序。

2）若當(dāng)前工序只有惟一緊前工序，則當(dāng)前工序的首節(jié)點(diǎn)號(hào)與其唯一緊前工序的尾節(jié)點(diǎn)編號(hào)相同，其尾節(jié)點(diǎn)編號(hào)為m=m+1。

3）否則，其緊前工序兩兩進(jìn)行處理。首先判斷它們的首尾節(jié)點(diǎn)是否相同，如果首或尾節(jié)點(diǎn)相同，則不需要合并，如果都不同，接著判斷它們的緊后工序數(shù)是否相同，如果相同則進(jìn)一步判斷其緊后工序是否一致，如果一致則兩者尾節(jié)點(diǎn)編號(hào)與較大者相同，同時(shí)記錄被刪掉的編號(hào)，完成合并工作。

4）若當(dāng)前工序的所有緊前工序有惟一公共的尾節(jié)點(diǎn)，則其首尾節(jié)點(diǎn)號(hào)可以確定，首節(jié)點(diǎn)號(hào)與惟一公共的尾節(jié)點(diǎn)號(hào)相同，而尾節(jié)點(diǎn)號(hào)為m=m+1；否則需要進(jìn)一步的判斷。

5）查找是否存在緊后工序惟一的緊前工序，若存在，則添加虛工序。從其他緊前工序的所有尾節(jié)點(diǎn)都添加一個(gè)虛工序，并指向該緊前的尾節(jié)點(diǎn)。然后判斷首尾節(jié)點(diǎn)編號(hào)順序的合法性并做出相應(yīng)處理，當(dāng)前工序的首節(jié)點(diǎn)編號(hào)與該緊前工序的尾節(jié)點(diǎn)編號(hào)相同，尾節(jié)點(diǎn)編號(hào)為m=m+1。查看已存在的虛工序，判斷它們是否有相同首尾節(jié)點(diǎn)，以免重復(fù)。添加虛工序時(shí)，其首節(jié)點(diǎn)編號(hào)有可能大于尾節(jié)點(diǎn)編號(hào)，此時(shí)要將其尾節(jié)點(diǎn)編號(hào)變成m+1，并且記錄被刪掉的尾節(jié)點(diǎn)編號(hào)，比較之前先保留刪除節(jié)點(diǎn)編號(hào)作為比較值，找出所有以此比較值為尾節(jié)點(diǎn)編號(hào)的工序，并修改它們的尾節(jié)點(diǎn)編號(hào)，添加當(dāng)前工序，修改其他以此比較值為尾節(jié)點(diǎn)編號(hào)的虛工序的尾節(jié)點(diǎn)編號(hào)，添加一個(gè)虛工序。

6）若不存在緊后工序惟一的緊前工序，則添加虛工序。從當(dāng)前工序的所有緊前工序尾節(jié)點(diǎn)各引出一個(gè)虛工序，它們的尾節(jié)點(diǎn)編號(hào)相等均為m+1，當(dāng)前工序的首節(jié)點(diǎn)編號(hào)與虛工序的公共尾節(jié)點(diǎn)編號(hào)相同，尾節(jié)點(diǎn)編號(hào)為m+1。

7）最后，需要?dú)w并所有的最終節(jié)點(diǎn)，將它們合并成一個(gè)節(jié)點(diǎn)。查找所有無緊后工序數(shù)組中尾節(jié)點(diǎn)編號(hào)最大的工序，令其尾節(jié)點(diǎn)為最終節(jié)點(diǎn)；依次遍歷其他無緊后工序，判斷是否需要添加虛工序，若當(dāng)前工序與以前處理過的工序中的某一個(gè)具有相同的首節(jié)點(diǎn)，則需要添加虛工序。虛工序的首節(jié)點(diǎn)編號(hào)與當(dāng)前工序的尾節(jié)點(diǎn)編號(hào)相同，尾節(jié)點(diǎn)編號(hào)為最終節(jié)點(diǎn)，否則，刪除當(dāng)前工序的尾節(jié)點(diǎn)編號(hào)，并且替換成最終節(jié)點(diǎn)編號(hào)，最終可以實(shí)現(xiàn)合并。

8）最后需要對(duì)節(jié)點(diǎn)的編號(hào)進(jìn)行整理。首先對(duì)刪除節(jié)點(diǎn)編號(hào)數(shù)組進(jìn)行排序，然后利用排序后的刪除節(jié)點(diǎn)編號(hào)數(shù)組依次對(duì)每組雙代號(hào)數(shù)據(jù)進(jìn)行整理。

4節(jié)點(diǎn)布局方法

確定好所有節(jié)點(diǎn)和節(jié)點(diǎn)之間的邏輯關(guān)系后，然后進(jìn)行節(jié)點(diǎn)布局，它也是網(wǎng)絡(luò)圖自動(dòng)繪制的關(guān)鍵性步驟。節(jié)點(diǎn)布局決定了網(wǎng)絡(luò)圖的交叉點(diǎn)的多少以及網(wǎng)絡(luò)圖是否清晰直觀。當(dāng)前比較流行的方法是經(jīng)緯線布局方法，使用經(jīng)緯坐標(biāo)（X，Y）來確定節(jié)點(diǎn)的位置，并根據(jù)網(wǎng)絡(luò)圖的比例來確定經(jīng)線X的寬度和緯線Y的高度。經(jīng)線X坐標(biāo)從0開始，向右橫向逐漸增大；緯線Y坐標(biāo)從0開始，縱向?qū)ΨQ擴(kuò)展，與坐標(biāo)系的y軸相似。盡量將關(guān)鍵路徑放在0緯線上，其他節(jié)點(diǎn)在0緯線兩邊對(duì)稱分開，使網(wǎng)絡(luò)圖布點(diǎn)對(duì)稱均衡。目前國內(nèi)大多數(shù)關(guān)于經(jīng)緯線坐標(biāo)的實(shí)現(xiàn)都是通過分級(jí)分層的方法，首先將所有節(jié)點(diǎn)進(jìn)行拓?fù)渑判騺韺?shí)現(xiàn)分級(jí)，然后再對(duì)每級(jí)中的節(jié)點(diǎn)進(jìn)行分層，節(jié)點(diǎn)層次的確定都是要以其緊前節(jié)點(diǎn)的層次為依據(jù)[7～8]。級(jí)數(shù)不同，層次可能相同；級(jí)數(shù)相同，層次必不同。

初始節(jié)點(diǎn)的級(jí)數(shù)為 1級(jí)，從初始節(jié)點(diǎn)到某一節(jié)點(diǎn)的所有路徑中經(jīng)過節(jié)點(diǎn)最多的路徑，其節(jié)點(diǎn)數(shù)就是該節(jié)點(diǎn)的級(jí)數(shù)，通過拓?fù)渑判虻玫剿泄?jié)點(diǎn)的級(jí)數(shù)，節(jié)點(diǎn)的級(jí)數(shù)與其經(jīng)線坐標(biāo)X相對(duì)應(yīng)[9]。但是在某些情況下，這種基于拓?fù)渑判虻姆旨?jí)方法可能會(huì)有一定的缺陷，如果確定經(jīng)線坐標(biāo)X時(shí)考慮到節(jié)點(diǎn)最早開始時(shí)間，那么某些節(jié)點(diǎn)可能會(huì)重疊在一起，對(duì)網(wǎng)絡(luò)圖的繪制造成一定的影響。因?yàn)槿绻紤]到節(jié)點(diǎn)的最早開始時(shí)間，級(jí)數(shù)不同的兩個(gè)節(jié)點(diǎn)它們的經(jīng)線坐標(biāo)X可能會(huì)相同，而級(jí)數(shù)不同時(shí)，層次又可能相同，即緯線坐標(biāo)Y也可能相同，所以這兩個(gè)節(jié)點(diǎn)可能會(huì)重疊。

傳統(tǒng)的分級(jí)方法中節(jié)點(diǎn)的級(jí)數(shù)和經(jīng)線坐標(biāo)X是一一對(duì)應(yīng)的，因?yàn)榇_定經(jīng)線坐標(biāo)X時(shí)增加了節(jié)點(diǎn)最早開始時(shí)間因素，所以分級(jí)方法也要有對(duì)應(yīng)的改變。本文針對(duì)傳統(tǒng)分級(jí)方法存在的問題，提出了改進(jìn)的節(jié)點(diǎn)分級(jí)方法，并且統(tǒng)籌考慮了節(jié)點(diǎn)的經(jīng)線坐標(biāo)X。核心思想就是經(jīng)線坐標(biāo)X相近的節(jié)點(diǎn)，盡量要使它們的級(jí)數(shù)相近或相同。節(jié)點(diǎn)的級(jí)數(shù)要根據(jù)其經(jīng)線坐標(biāo)X進(jìn)行適當(dāng)?shù)恼{(diào)整，要保證某級(jí)所有節(jié)點(diǎn)的最早開始時(shí)間都要比其前一級(jí)級(jí)的任意節(jié)點(diǎn)的最早開始時(shí)間大。

5結(jié)束語

隨著雙代號(hào)工程網(wǎng)絡(luò)圖在工程項(xiàng)目中的廣泛應(yīng)用，項(xiàng)目越來越復(fù)雜，工序越來越多，手工繪制網(wǎng)絡(luò)圖具有一定的難度，且無法滿足當(dāng)前的需求。本文通過研究當(dāng)前雙代號(hào)工程網(wǎng)絡(luò)圖計(jì)算機(jī)自動(dòng)繪制中存在的許多問題，以繪制清晰和美觀的網(wǎng)絡(luò)圖為研究目標(biāo)，提出了一種較好的虛工序確定算法，并可以刪除冗余的虛工序，通過對(duì)傳統(tǒng)的經(jīng)緯線布局法進(jìn)行相關(guān)研究，提出了改進(jìn)的分級(jí)分層方法，較好地解決了節(jié)點(diǎn)重疊的問題。最后繪制出清晰美觀的網(wǎng)絡(luò)圖，為更加簡(jiǎn)單清晰直觀的展現(xiàn)項(xiàng)目進(jìn)度計(jì)劃的工程網(wǎng)絡(luò)圖繪制奠定了堅(jiān)實(shí)的理論和技術(shù)基礎(chǔ)。

參考文獻(xiàn)：

[1] 李四福. 大型工程PERT智能繪圖與工程優(yōu)化研究[D]. 北京： 中國地質(zhì)大學(xué)，2014.

[2] 崔夢(mèng)天，張榮虎，程國忠. 大規(guī)模軟件項(xiàng)目管理系統(tǒng)中PERT網(wǎng)絡(luò)圖的優(yōu)化問題研究[J]. 西南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2012（4）：638-641.

[3] 蘇志雄，魏漢英. 規(guī)范化工程網(wǎng)絡(luò)圖的理論和方法[J]. 中國管理科學(xué)，2015，S1：359-363.

[4] 鄒海，邱慧麗. 雙代號(hào)網(wǎng)絡(luò)圖繪制算法的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)與現(xiàn)代化，2013，07：176-179.

[5] 何永翔. 動(dòng)態(tài)環(huán)境下pert網(wǎng)絡(luò)圖的布局優(yōu)化研究[D]. 北京： 中國地質(zhì)大學(xué)，2010.

[6] 伍振華. 基于雙代號(hào)網(wǎng)絡(luò)圖的網(wǎng)絡(luò)計(jì)劃技術(shù)研究[D]. 武漢： 華中科技大學(xué)，2008.

[7] 宋瑩. 基于GA的通風(fēng)網(wǎng)絡(luò)圖優(yōu)化繪制算法研究[D]. 阜新： 遼寧工程技術(shù)大學(xué)，2013.

[8] 韓超. 基于不確定性的工程項(xiàng)目網(wǎng)絡(luò)計(jì)劃優(yōu)化研究[D]. 南京： 南京林業(yè)大學(xué)，2012.

[9] 邱慧麗. 礦井建設(shè)工程網(wǎng)絡(luò)計(jì)劃技術(shù)研究[D]. 合肥： 安徽大學(xué)，2013.