張 琪

(承德醫(yī)學(xué)院 生物醫(yī)學(xué)工程系計算機(jī)教研室，河北 承德 067000)

完成工程項目的最佳方案設(shè)計

張 琪

(承德醫(yī)學(xué)院 生物醫(yī)學(xué)工程系計算機(jī)教研室，河北 承德 067000)

在生產(chǎn)活動中，幾乎所有的工程項目都可以分為若干個稱作活動的子工程，而這些活動之間通常受著一定條件的約束。例如其中某些活動的開始必須在另一些活動完成之后。如何設(shè)計一個方案，使得工程項目在最佳時間內(nèi)完成。這里我們要解決兩個問題。一是設(shè)計一個科學(xué)可行的施工流程圖。二是計算出完成整項工程至少需要多少時間和那些活動是影響工程進(jìn)度的關(guān)鍵？解決這些問題的核心是應(yīng)用圖論中的有向無環(huán)圖的結(jié)構(gòu)建立數(shù)學(xué)模型，應(yīng)用有向無環(huán)圖理論和方法描述設(shè)計算法。本論文我們給出自然語言算法。

有向無環(huán)圖；拓?fù)渑判?；?quán)值；關(guān)鍵路徑；AOV-網(wǎng)；AOE-網(wǎng)；事件；活動

設(shè)計施工流程的數(shù)學(xué)模型可以抽象為：用頂點(diǎn)表示活動（子工程），用?。ㄓ邢蜻叄┍硎净顒娱g的優(yōu)先關(guān)系的有向圖——AOV-網(wǎng)（Activity On Vertex Network）。

第二個問題的數(shù)學(xué)模型可以抽象為：頂點(diǎn)表示事件（表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始），弧表示活動，權(quán)表示活動持續(xù)時間的帶權(quán)有向無環(huán)圖——AOE-網(wǎng)（Activity On Edge）。

算法：施工流程的算法設(shè)計：對應(yīng)于有向圖AOV-網(wǎng)，若從頂點(diǎn)i到頂點(diǎn)j有一條有向路徑（i是j的先決條件），則i是j的前驅(qū)，若是網(wǎng)中的一條弧，則i是j的直接前驅(qū)，j是i的直接后繼。在網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)，因為存在著環(huán)就意味著某項活動應(yīng)以自己為先決條件。若出現(xiàn)這樣的問題，工程便無法進(jìn)行。因此，對給定的AOV-網(wǎng)應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測的辦法是對有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄小負(fù)渑判?，若網(wǎng)中所有的頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV-網(wǎng)中必不存在環(huán)。

如何進(jìn)行拓?fù)渑判蚰?？解決的方法是：（自然語言算法）（1）在有向圖中選一個沒有前驅(qū)的頂點(diǎn)且輸出之。（2）從圖中刪去該頂點(diǎn)和所有以它為尾的弧。

重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，或當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止，前一種情況工程的流程設(shè)計是科學(xué)可行的。后一種情況有向圖中存在環(huán)，這種設(shè)計工程便無法進(jìn)行。

解決 “完成整項工程至少需要多少時間和那些活動是影響工程進(jìn)度的關(guān)鍵”？問題的算法設(shè)計：

首先是對于帶權(quán)的有向圖經(jīng)過拓?fù)渑判蚝蟠_定是AOE-網(wǎng)（有向無環(huán)），然后利用深度優(yōu)先遍歷進(jìn)行逆拓?fù)渑判颉Ｔ贏OE-網(wǎng)中，有些活動可以并行的進(jìn)行，所以完成工程的最短時間是從開始點(diǎn)到完成點(diǎn)的最長路徑的長度 （路徑長度是指路徑上各活動持續(xù)時間之和，不是路徑上弧的數(shù)目）。路徑長度最長的路徑叫做關(guān)鍵路徑（Critical Path）。設(shè)AOE-網(wǎng)中有 v1，,v2，v3，……，vn 個事件，a1，a2，a3，……，am項活動。假設(shè)開始點(diǎn)是v1，從v1到vi的最長路徑叫做事件vi的最早發(fā)生時間。這個時間決定了所有以vi為尾的弧所表示的活動的最早開始時間。我們用e(i)表示ai的最早開始時間。l(i)表示ai最遲開始時間，這是在不推遲整個工程完成的前提下，活動ai最遲必須開始的時間。兩者之差l(i)-e(i)意味著完成活動ai的時間余量。我們把l(i)=e(i)叫做關(guān)鍵活動。關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，提前完成非關(guān)鍵活動并不能加快工程進(jìn)度。因此，分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的工效，縮短整個工期。

由以上分析可知，辨別關(guān)鍵活動就是要找e(i)=l(i)的活動。為了求得AOE-網(wǎng)中活動ai的最早開始時間e(i)和ai最遲開始時間l(i)，首先應(yīng)求得事件的最早發(fā)生時間ve(j)和最遲發(fā)生時間vl(j)。如果活動ai由弧表示，其持續(xù)時間記為 dut()，則有如下關(guān)系：

求ve(j)和vl(j)需分兩步進(jìn)行：

1.從ve(1)=0開始向前遞推 ve(j)=Max{ve(i)+dut()}； 公式①

∈T，j=2，…，n 其中 T是所有以第 j個頂點(diǎn)為頭的弧的集合。

2.從vl(n)=ve(n)起向后遞推 vl(i)=Max{vl(j)-dut()}； 公式②

∈S，i=n-1，n-1，…，1 其中 S 是所有以第i個頂點(diǎn)為尾的弧的集合。

這兩個遞推公式的計算必須分別是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。也就是說，ve(j-1)必須是在vj所有前驅(qū)的最早發(fā)生時間求得之后才能確定，而vl(j-1)必須是在vj所有后繼的最遲發(fā)生時間求得之后才能確定。

由此得到如下所述求關(guān)鍵路徑的算法：

（1）根據(jù)問題的e項子工程，確定e條弧ai=（i=1，2，……，e），找出 v1，v2，v3，……，vn 個事件，建立AOE-網(wǎng)（帶權(quán)的有向無環(huán)圖）；

（2）從源點(diǎn)v1出發(fā)，令ve[1]=0，按拓?fù)溆行蚯笃涓黜旤c(diǎn)的最早發(fā)生時間 ve[i]（2≤i≤n）。

（3）從匯點(diǎn) vn 出發(fā)，令 vl[n]=ve[n]，按逆拓?fù)溆行蚯笃溆喔鼽c(diǎn)的最遲發(fā)生時間vl[i]（n-1≥i≥1）；

（4）根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足e(s)=l(s)，則為關(guān)鍵活動。

舉例：如圖1是一個的有15項活動，弧a1=，a2=，…，a15=分別表示活動， 11 個事件 v1，v2，v3， ……，v11 的 AOE-網(wǎng)，每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。如v1表示整個工程的開始，v11表示整個工程結(jié)束，v5表示a3和a4已經(jīng)完成，a8和a9可以開始。與每個活動相聯(lián)系的數(shù)是執(zhí)行該活動所用的時間。比如，活動a1需要3天，a2需要4天等。

按照公式①和公式②對圖1所示AOE-網(wǎng)中頂點(diǎn)發(fā)生時間和活動開始時間進(jìn)行計算。得表如下

頂點(diǎn) ve vl 活動 e l l-e V1 0 0 a1 0 3 3 V2 3 6 a2 0 0 0 V3 4 4 a3 3 13 10 V4 5 15 a4 3 6 3 V5 7 7 a5 4 4 0 V6 9 19 a6 4 14 10 V7 15 21 a7 5 15 10 V8 11 11 a8 7 13 6 V9 21 21 a9 7 7 0 V10 22 22 a10 9 19 10 V11 28 28 a11 15 21 6 a12 11 18 7 a13 11 11 0 a14 21 21 0 a15 22 22 0

我們求得關(guān)鍵活動為：a2，a5，a9，a13，a14 和a15， 它構(gòu)成一條關(guān)鍵路徑為：（v1，v3，v5，v8，v9，v10，v11）。 （注：有時候關(guān)鍵路徑不惟一）

關(guān)鍵路徑上的所有活動都是關(guān)鍵活動，而提前完成非關(guān)鍵活動并不能加快工程進(jìn)度。因此爭取提高關(guān)鍵活動的工效，才能縮短整個工期。

用AOE-網(wǎng)來估算某些工程完成的時間是非常有用的。但是，由于網(wǎng)中各項活動是互相牽涉的，因此，影響關(guān)鍵活動的因素也是多方面的，任何一項活動持續(xù)時間的改變都會影響關(guān)鍵路徑的改變。所以，關(guān)鍵活動的速度提高是有限的。只有在不改變關(guān)鍵路徑的情況下，提高關(guān)鍵活動的速度才有效。另一方面，若網(wǎng)中有幾條關(guān)鍵路徑，單是提高一條關(guān)鍵路徑上的關(guān)鍵活動的速度并不能導(dǎo)致整個工程縮短工期，必須提高同時在幾個關(guān)鍵路徑上的活動速度。

[1]譚浩強(qiáng).C語言程序設(shè)計.清華大學(xué)出版社,2002

[2]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社,2001

[3]張禾瑞.高等代數(shù).高等教育出版社,1990

[4]王朝陽,于蘭芳等.離散數(shù)學(xué).中國礦業(yè)大學(xué)出版社,2001

O29

A

1005-1554（2010）02-0016-02

2009-12-25

張琪（1983-），男，河北承德人,承德醫(yī)學(xué)院生物醫(yī)學(xué)工程系計算機(jī)教研室教師。