完成工程項(xiàng)目的最佳方案設(shè)計(jì)

張 琪

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

完成工程項(xiàng)目的最佳方案設(shè)計(jì)

張 琪

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

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

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

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

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

算法：施工流程的算法設(shè)計(jì)：對(duì)應(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)，因?yàn)榇嬖谥h(huán)就意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件。若出現(xiàn)這樣的問(wèn)題，工程便無(wú)法進(jìn)行。因此，對(duì)給定的AOV-網(wǎng)應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測(cè)的辦法是對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄小負(fù)渑判颍艟W(wǎng)中所有的頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV-網(wǎng)中必不存在環(huán)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

頂點(diǎn) ve vl 活動(dòng) 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)鍵活動(dòng)為：a2，a5，a9，a13，a14 和a15， 它構(gòu)成一條關(guān)鍵路徑為：（v1，v3，v5，v8，v9，v10，v11）。 （注：有時(shí)候關(guān)鍵路徑不惟一）

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

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

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

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

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

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

O29

A

1005-1554（2010）02-0016-02

2009-12-25

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