基于相關(guān)任務(wù)分配的網(wǎng)絡(luò)計劃的算法

1、1 基于相關(guān)任務(wù)分配的網(wǎng)絡(luò)計劃的算法郭 強(qiáng)西北工業(yè)大學(xué)理學(xué)院 應(yīng)用數(shù)學(xué)系西安 710072 摘要研究如何把具有緊前緊后關(guān)系的工作集分配給現(xiàn)有的人員（或設(shè)備），使完成工作集的總工期最短，并在此條件下， 使得用于所有工作上的時間之和最少。文中揭示了任意改變一項工作的用時或最早開工時間，將引起其他工作的最早開工時間的變化規(guī)律，并在此基礎(chǔ)上借鑒floyd 算法規(guī)則， 建立了一種獲取該問題最優(yōu)解的迭代算法。這種算法能保證總工期隨迭代過程遞減，在總工期達(dá)到最短時，能保證總工期不變， 而總用時隨迭代過程遞減。使用這種算法， 不用繪制pert 圖，只需輸入每個人承擔(dān)不同工作的用時，以及各工作間的緊前緊后關(guān)系，

2、即可算出最優(yōu)分配方案、總工期及各項工作的最早開工時間和松弛時間。關(guān)鍵詞： 分配問題； pert 問題； a-pert 問題；floyd 算法；最早開工時間；松弛時間。an algorithm of network plan based on dependent task assignmentguo qiang department of applied mathematics, school of science , northwestern polytechnical university, xian 710072abstract:how assigning the jobs with pr

3、ecedence and successor relationship to every person (or facility) so that the engineering period is the shortest, and in this premise the total time of completing all the jobs in the engineering is the least is studied in this paper. through reveal the changed law of the earliest start time of all o

4、ther jobs when the time of any job or its earliest start time is altered, an iterative algorithm is established to obtain the optimal solution in virtue of floyd algorithm. the algorithm can ensure that the engineering period is shortened with iteration and the total time is decreased with iteration

5、 when the engineering period is the shortest. the algorithm is convenient rather than drawing the pert figure, only the time of every person doing different jobs and the sequential order of all the jobs are inputted, the optimal assignment solution, the shortest engineering period and the earliest s

6、tart time and relaxation time of every job can be obtained. keywords: assignment problem; pert problem; a-pert problem; floyd algorithm; earliest starting time; relaxation time 1、引言研究如何把具有緊前緊后關(guān)系的任務(wù)集分配給現(xiàn)有的人員（或設(shè)備），在保證完成任務(wù)集的總工期最短的前提下，使總用時最少， 是一種充分利用現(xiàn)有的人力和物力，最大限度地提高工作效率的優(yōu)化問題。這樣的優(yōu)化問題，在生產(chǎn)調(diào)度、機(jī)械加工、以及工程計劃制定與

7、管理等活動中，無疑有著重要的應(yīng)用價值。但是要解決這樣的問題，卻并不容易，文獻(xiàn)1證明了使總工期最短的問題是一個np-hard 問題， 不存在多項式時間的算法，在問題規(guī)模較大的情況下，很難獲得精確最優(yōu)解。因此，人們對這類問題的研究，普遍著眼于尋找近似最2 優(yōu)解或稱滿意解的算法上，以及如何提高近似最優(yōu)解的精度和計算效率。如，文獻(xiàn)2 給出了一種 mcp 近似算法，文獻(xiàn)3 給出了一種etf 近似算法，文獻(xiàn)4 給出了一種dls 近似算法， 文獻(xiàn) 5 總結(jié)分析了文獻(xiàn)2 和3 ，給出了一種bdcp 近似算法， 文獻(xiàn) 6 和7 又在上述近似算法的基礎(chǔ)上，給出了新的近似算法。文獻(xiàn)8 和文獻(xiàn) 9 則給出了不同的遺傳

8、算法。研究這類問題的近似算法的文獻(xiàn)還有很多，但是，卻很難找到研究這類問題的精確最優(yōu)解的文獻(xiàn)。另外， 目前對這類問題的研究都集中在如何獲取最短的總工期的問題上，而沒有注意到使總工期最短的分配方案通常會有多種，而且，使總工期達(dá)到最短的不同分配方案的總用時往往不同，甚至有較大的差異，舉一個簡單例子：某項工程由三項工作構(gòu)成，各工作間的緊前、緊后關(guān)系如圖1。工作 1 工作 2 （圖 1）工作 3 已知三個人承擔(dān)這三項工作的用時情況見表1。表 1 用時（周）工作人工作 1 工作 2 工作 3 甲8 3 8 乙2 7 11 丙8 9 13 通過窮舉，可以得到所有分配方案下的總用時與總工期，見表2。表 2 工

9、作 1 工作 2 工作 3 總工期總用時方案 1 （用時）甲8 乙7 丙13 15 28 方案 2 （用時）甲8 丙9 乙11 17 28 方案 3 （用時）乙2 甲3 丙13 13 18 方案 4 （用時）乙2 丙9 甲8 11 19 方案 5 （用時）丙8 甲3 乙11 11 22 方案 6 （用時）丙8 乙7 甲8 15 23 從表 2 中可看出，按第4、第 5 套方案進(jìn)行分配，總工期最短，為11 周，但是，第4套分配方案的總用時為19 周，比第 5 套分配方案的總用時22 周要少花費3 周時間，因此，選擇第 4 套分配方案，不但能使總工期達(dá)到最短，而且可以使總用時相對較少。為此， 本文

10、提出了一種如何尋找相關(guān)任務(wù)的分配方案，使總工期達(dá)到最短的情況下，使總用時最少的問題，本文將這種問題稱為a-pert 問題。無疑，這是一個新的、有意義的現(xiàn)實問題。2、 a-pert 問題的特征及其數(shù)學(xué)模型a-pert 問題的完整描述如下：某項工程由n項工作構(gòu)成，各工作之間具有已知的緊前、緊后關(guān)系，現(xiàn)有m個人可參與這項工程。規(guī)定每項工作只能由一個人承擔(dān)。已知第i個人完成第j項工作需用時),2,1;,2,1(njmicij。研究：要完成這項工程中的所有工作應(yīng)如何進(jìn)行分配，才能夠使總工期最短，并在此條件下， 使用于所有工作上的時間之和最少，以及在這種要求3 下的總工期、各項工作的最早開工時間和松弛時間

11、。a-pert 問題涉及到nmnmnm,三種情況，統(tǒng)一的要求是每項工作只能由一個人承擔(dān)，不同的要求是，nm時，每個人至少承擔(dān)一項工作；nm時，每個人只承擔(dān)一項工作；nm時，每個人至多承擔(dān)一項工作。設(shè)否則，項工作時人承擔(dān)第當(dāng)?shù)?,1jixij),2,1;,2,1(njmi用)(nmijijxcf表示按),2,1;,2, 1(njmixij進(jìn)行分配時，所需總工期。a-pert 問題的數(shù)學(xué)模型為：),2, 1;,2,1(,1,0),2,1(,1),2,1( ,)(min. .min1111njmixnjxmixxcftsxcijmiijnjijnmijijminjijij其中，,為參變量。當(dāng)nm時，

12、1,1mn；當(dāng)nm時，1,0。這是一個雙層0-1 整數(shù)規(guī)劃，雖然可以用窮舉法求解，即，計算出所有不同分配方案下的總工期，通過比較，可以選出總工期最短時總用時最少的分配方案（最優(yōu)解）。但是這樣的方法計算量太大，在nm時，要計算mncm!次 pert 問題；在nm時，要計算n！次 pert 問題；在nm時，要計算nmcn!次 pert 問題。所以，在a-pert 問題的規(guī)模較大時，這種方法顯然是不可行的。本文將針對nm情況，介紹一種借助floyd 算法規(guī)則求解a-pert 問題的精確算法，以此為基礎(chǔ)，有利于進(jìn)一步研究nm和nm兩種情況下的a-pert 問題。3、a-pert 問題的算法理論從上述

13、a-pert 問題的描述可以看出，在a-pert 問題所給條件下，如果只求總用時最少的分配方案，則涉及的便是經(jīng)典分配問題；如果給定了分配方案，再求總工期及各項工作的最早開工時間和松弛時間，則涉及的便是經(jīng)典的計劃評審技術(shù)問題，又稱pert 問題。因此， 求解 a-pert 問題， 可以借鑒文獻(xiàn) 10中求解經(jīng)典分配問題的方法：按照一定的規(guī)律，反復(fù)從一種分配方案變換到另一種總用時更少的分配方案，直到最終獲得總用時最少的分配方案。即，按照以下思路解決a-pert 問題：按照一定的規(guī)律，反復(fù)從一種分配方案變換到另一種總工期更短或總工期不增的情況下總用時更少的分配方案，直到最終獲得總工期最短的情況下總用時

14、最少的分配方案。要實現(xiàn)這樣的目的，關(guān)鍵是找出上面提到的規(guī)律。另外，要使算法具有實用的計算效率， 應(yīng)盡量降低迭代過程中出現(xiàn)的每一種分配方案下的總工期和總用時的計算量。研究表明，再借鑒文獻(xiàn) 11中求解 pert 問題的算法，便可以實現(xiàn)這一目的，達(dá)到這樣的要求。為此，4 先給出文獻(xiàn) 10和文獻(xiàn) 11中的相關(guān)理論。定理 1 設(shè)),2,1(,2, 1)(ninir為上述問題的一個可行分配方案（表示安排第i個人承擔(dān)第)(ir項工作），),2,1,(,)()(njijpccijiirijrij（)(iirc為第i個人承擔(dān)第)(ir項工作的用時，)(ijrc為第j個人承擔(dān)第)(ir項工作的用時，ijp是用于記

15、錄人員調(diào)整的方法。） 。則通過下面兩步運算：1若ijkjik，則ikijkjikijpp,；否則ijijijkjikp與)(都不變。),2,1,(nji轉(zhuǎn)到2。2求niii1min，當(dāng)0，nk時，1kk轉(zhuǎn)到1可獲得以下信息：（ 1） 當(dāng)0時，意味著找到了一個可減少總用時的循環(huán)調(diào)整方案：記uu，uu0)()(,)(,00urvrvrwpvuu在uv時，vuwur00,)(，轉(zhuǎn)到，直到uv為止。（ 2）當(dāng)nk,2,1的過程中，始終0，意味著當(dāng)前的分配方案已經(jīng)是總用時最少的分配方案。證 參見文獻(xiàn) 10 。定義1 已知一項工程由n個具有緊前、緊后關(guān)系的工作構(gòu)成，第i項工作需用時),2,1(niti。若

16、第ni,2, 1項工作無緊前工作時，則令第0 項工作為其緊前工作；若第nj,2, 1項工作無緊后工作時，則令第n+1 項工作為其緊后工作，010ntt。設(shè))1,1,0,(,0,njijiijtdiij否則，時。當(dāng)項工作的緊后工作時項工作是第當(dāng)?shù)趧t稱矩陣)2()2()(nnijd為初始 pert 矩陣 ，對應(yīng)的網(wǎng)絡(luò)稱為復(fù)線 pert 網(wǎng)絡(luò) 。顯然，一個初始pert 矩陣對應(yīng)著一個有向網(wǎng)絡(luò)，第i項工作對應(yīng)著第i個節(jié)點（1, 1,0ni） ， 節(jié)點i到相鄰可達(dá)的節(jié)點j的邊長為第i項工作的用時it。 節(jié)點i不相鄰可達(dá)節(jié)點j時，令ijd，)1, 1,0,(nji是為了便于計算。定義 2 若矩陣)2()2

17、()(nnijd中的元素) 1,1 ,0,(njidij表示復(fù)線pert 網(wǎng)絡(luò)中5 節(jié)點i到節(jié)點j的最長路值，則稱該矩陣為最優(yōu) pert 矩陣 。定理 2 設(shè))2()2()(nnijd為初始 pert 矩陣，則通過下列運算：10k2若ijkjikddd，則kjikijddd；否則ijijkjikdddd)(不變。)1,1 ,0,(nji轉(zhuǎn)到3。3若1nk，則1kk，轉(zhuǎn)到2；否則) 1(nk，輸出)2()2()(nnijd。得到的矩陣)2()2()(nnijd是最優(yōu) pert 矩陣，且有下列結(jié)果：（1）第j項工作的最早開工時間為),2, 1(njdoj；（2）第j項工作的最早完工時間為),2,1

18、(njtdjoj；（3）完成該項工程所需總工期為1,0 nd；（4）第j項工作的松弛時間為),2, 1(1,01,0njdddjnjjn；（5）第j項工作的最遲開工時間為),2,1(1,1,00njdddnjnjj；（6）第j項工作的最遲完工時間為),2,1(1,1,00njtddtdjnjnjjj。證 參見文獻(xiàn) 11。定理 1 給出了一種尋找總用時最少的分配方案的方法，定理 2 給出了一種在每一項工作的用時都確定的情況下，獲取總工期及各項工作最早開工時間和松弛時間的方法。當(dāng)某一項工作的用時被改變，其它相關(guān)工作的最早開工時間是否會發(fā)生變化，如何變化， 具有以下規(guī)律：定理 3 設(shè))1()1()(

19、nnijd為最優(yōu)pert 矩陣。若) 10(,0nidik，則改變第k項工作的用時，不會影響第i項工作的最早開工時間。證 由最優(yōu) pert 矩陣知，0ikd時，意味著第k項工作不是第i項工作的的后繼工作，所以，則改變第k項工作的用時，不會影響第i項工作的最早開工時間。定理 4 設(shè)第i項工作的最早開工時間為id0，用時為) 1,2, 1(niti) 1,2, 1 ,0,(,0, 1njiijoij否則項工作的緊后作業(yè)時項工作是第第又設(shè)第 s 項工作是第k 項工作的任意一個緊后工作)10(nk，6 sisiilnikiotd11,1max0則當(dāng)?shù)?k 項工作的用時改變k時，下列結(jié)論成立：（1）sl

20、不存在時，第k 項工作的緊后工作11,1njojjkj的最早開工時間變?yōu)閗kktd0，最早開工時間的改變量為k。（2）sl存在時，第k 項工作的緊后工作11,1njojjkj的最早開工時間變?yōu)閗kkstdl0,max，最早開工時間的改變量為0,max0skkkltd。證 （1）sl不存在時，說明第k 項工作是其緊后工作11,1njojjkj的唯一緊前工作， 所以第 k 項工作完成后， 第 k 項工作的緊后工作即可開工，而第 k 項工作的最早開工時間為kd0，用時為kkt，所以，第k 項工作的緊后工作的最早開工時間為kkktd0。（2）sl存在時，說明第k 項工作不是其緊后工作11,1njojj

21、kj的唯一緊前工作， 所以只有當(dāng)?shù)?1,1njojjkj項工作的所有緊前工作都完成后，第j項工作才能開工， 而kkkstdl0,max是第j項工作的完工時間最晚的緊前工作的完工時間，所以，第k 項工作的緊后工作的最早開工時間為kkkstdl0,max。推論在定理 5 的條件下，當(dāng)?shù)趉 項工作的最早開工時間改變k時，下列結(jié)論成立：（1）sl不存在時，第k 項工作的緊后工作11,1njojjkj的最早開工時間變?yōu)閗kktd0，最早開工時間的改變量為k。（2）sl存在時，第k 項工作的緊后工作11,1njojjkj的最早開工時間變?yōu)閗kkstdl0,max，最早開工時間的改變量為0,max0skkk

22、ltd。證 與定理 5 完全類似，略。如果第i項工作的最早開工時間改變i時，我們引入否則，早開工時間未修改完時項工作的緊后工作的最第0,1juj則根據(jù)定理3 和定理 4 及其推論可知，在第k項工作的用時改變k后，第k項工作的所有7 前期工作的最早開工時間不變，而所有后期工作的最早開工時間可通過下面運算獲得：1kkktt2求snioiki11,1min3求sisiilnikiotd1,1max0，14若sl不存在，則kktdt0；否則（sl存在）skkltdt,max0。5若1ko，則1,0utd，轉(zhuǎn)到6；否則（0ko）直接轉(zhuǎn)到6。6若1n，則1轉(zhuǎn)到5；否則（1n）1,0ku， 轉(zhuǎn)到7。7若1u

23、，則k轉(zhuǎn)到2；否則（0u）轉(zhuǎn)到8。8若n，則1轉(zhuǎn)到7；否則（n）停。為便于論述，用0dk表示第k項工作用時改變k后，由上述運算步驟18得到的第項工作的最早開工時間，則按floyd 算法規(guī)則執(zhí)行運算，可獲得以下運算規(guī)律：定理 5 設(shè)ijc為第i人做第j項工作的用時),2, 1,(nji，),2,1()(niir為一個可行分配方案，)2()2()(nnijd是對應(yīng)該分配方案的最優(yōu)pert 矩陣。)()(iirijrijcc表示將第i人承擔(dān)第)(ir項工作改為第j人承擔(dān)第)(ir項工作后，造成第)(ir項工作的用時改變量),2, 1,(nji，sijijdst0)(表示第)(ir項工作用時改變ij后

24、，第 s 項工作的最早開工時間)1,2, 1;, 2, 1,(nsnji，1, 0)1(nijijdntl表示第)(ir項工作用時改變ij后，總工期的改變量),2, 1,(nji，再引入人員調(diào)換記錄),2, 1,(njijpij，則通過下面兩步運算：1若) 1() 1(ntntijkjik時，則) 1, 2, 1()()(nsststkjikij1, 0) 1(nijijdntl，ikijpp；否則)1, 2, 1()(nsstij，ijl，ijp都不變。),2,1,(nji轉(zhuǎn)到2。2求nilii1min，當(dāng)0，nk時，1kk轉(zhuǎn)到1可獲得以下信息：（ 1） 當(dāng)0時， 意味著找到了一個可縮短總工

25、期的循環(huán)調(diào)整方案：記uul，uu08 )()(,)(,00urvrvrwpvuu在uv時，vuwur00,)(，轉(zhuǎn)到，直到uv為止。（ 2）當(dāng)nk,2,1的過程中，始終0，意味著當(dāng)前的分配方案已經(jīng)是總工期最短的分配方案。證 （1）因為，如果存在一個分配方案：安排第1i人做第)1(r項工作， 第2i人做第)2(r項工作， ， 第ni人做第)(nr項工作時的總工期比安排第i人做第)(ir),2,1(ni項工作時的總工期短，則niii,21是n,2, 1的一個全排列。為了便于論述，不妨設(shè)（其它情況證明類似）niiiiiin,1,1,3,21121，則用第1i人替換第1 人，第2i人替換第2 人，第i

26、人替換第人，總工期便會縮短。因此，以下必有一組按次序執(zhí)行的運算式成立：12112112111121121,21 ,21 ,11,21,21 ,21 ,11,2, 11 ,11, 11, 11 , 11, 1)1()1(,)1()1()1()1(,)1()1() 1()1(,)1() 1(ppntntntntppntntntntppntntntnt，所以因為，所以因為，所以因為2322322322223223,12,12, 12, 12, 12, 11212122121)1()1(,)1()1()1()1(,)1() 1()1()1(,) 1()1(ppntntntntppntntntntppn

27、tntntnt，所以因為，所以因為，所以因為9 111112,3,3, 22,3, 3, 3,22, 31, 2,2, 11,2,2,2,11,2)1()1(,)1()1()1()1(,)1()1()1()1(,)1() 1(ppntntntntppntntntntppntntntnt，所以因為，所以因為，所以因為因為，這組按次序執(zhí)行的運算，都屬于定理中的1、2兩步運算的搜索范圍，只是執(zhí)行的是能夠成立的一組，又因為運算前),2, 1() 1(1,01,0niddntnniiii，所以執(zhí)行1、2的結(jié)果是),2, 1() 1(1, 0nidntlniiii中必有一個小于0，所以，01minnili

28、i，用),2, 1,(njipij記錄到的調(diào)整過程，按定理中的、進(jìn)行調(diào)整，便得到一個總工期更短的分配方案。（2）對（ 1）的證明已揭示，只要存在比當(dāng)前分配方案下的總工期更短的分配方案，定理中的1、2兩步運算一定能將其找出來。同時也表明，如果當(dāng)前的分配方案已經(jīng)使總工期達(dá)到最短了，則在nk,2,1的過程中，按定理中的1、2兩步運算，始終不會出現(xiàn)),2, 1()1(ninttiikiik， 所以，0iil始終不變， 故01minnilii，即0始終成立。定理 6 設(shè)分配方案),2,1()(niir使總工期達(dá)到了最短，)()(iirijrijcc，),2, 1,(njiijij，則通過下面兩步運算：1

29、若) 1() 1(ntntijkjik，且ijkjik，則) 1,2, 1()()(nsststkjikij，kjikij，ikijpp；否則) 1,2, 1()(nsstij，ij，ijp都不變。),2,1,(nji轉(zhuǎn)到2。2求niii1min，當(dāng)0，nk時，1kk轉(zhuǎn)到1可獲得以下信息：（ 1） 當(dāng)0時， 意味著找到了一個可減少總用時的循環(huán)調(diào)整方案：記uul，uu0)()(,)(,00urvrvrwpvuu在uv時，vuwur00,)(，轉(zhuǎn)到，直到uv為止。10 給定初始分配方案：),2,1()(niir用定理 2 求該分配方案下的最優(yōu)pert 矩陣)2()2()(nnijdijijiiri

30、jrijcc,)()(按定理 3、定理 4 及推論：時時0,0,)()(0)(0sirssirsijijddddst1,0) 1(nijijdntl)1,2, 1;,2, 1,(nsnjiyes no no yes （ 2）當(dāng)nk,2,1的過程中，始終0，意味著在保持總工期不變的前提下，當(dāng)前的分配方案已經(jīng)使總用時到了最少。證 類似于定理5 的證明，略。4、a-pert 問題的程序算法上述 a-pert 問題的算法理論揭示，求解a-pert 問題，可以按下面模塊化的算法流程圖進(jìn)行：用定理 5 判斷是否存在總工期更短的分配方案用定理 6 判斷是否存在總工期不變但總用時減少的分配案按照),2, 1,

31、(njipij記錄，調(diào)整分配方案：),2, 1()(niir，同時更新每一項工作的最早開工時間：) 1,2, 1(0nsds輸出最優(yōu)分配方案：),2, 1()(niir及每項工作的最早開工時間：) 1,2, 1(0nsds，其中1,0 nd為總工期。11 求解 a-pert 問題的精確最優(yōu)解的具體算法步驟如下：1輸入已知數(shù)據(jù)：),2,1(,(njicij，) 1,2 , 1 , 0,(,0,1njiijoij否則項作業(yè)的緊后作業(yè)時項作業(yè)是第第2用最小元素法定初始分配方案：),2, 1()(niir。3用定理 2 求最優(yōu) pert 矩陣：)2()2()(nnijd4),2, 1,(,)()(nj

32、iccijijiirijrij5按照定理 3 和定理 4，計算將第)(ir項工作改由第j人承擔(dān)后，第s項工作的最早開工時間：時。時，0,0,)()(0)(0sirssirsijijddddst，)1, 2, 1;,2, 1,(nsnji對應(yīng)的總工期的改變量：1,0)1(nijijdntl，), 2, 1,(nji記錄調(diào)整過程：jpij，),2,1,(nji。6計算逐步增加改變工作承擔(dān)者的工作后，搜尋使總工期變短或總工期不變時使總用時變少的調(diào)整方案：1,1,1kji。7若) 1() 1(ntntijkjik，則)1,2,1( ,)()(nsststkjikij1, 0) 1(nijijdntl，

33、kjikij，ikijpp，轉(zhuǎn)到9；否則轉(zhuǎn)到8。8若) 1() 1(ntntijkjik且ijkjik，則)1,2, 1( ,)()(nsststkjikij，ikijkjikijpp,，轉(zhuǎn)到9；否則直接轉(zhuǎn)到9。9若nj，則1jj轉(zhuǎn)到7；否則（nj）轉(zhuǎn)到10。10若ni，則1,1jii轉(zhuǎn)到7；否則（ni）轉(zhuǎn)到11。12 11判斷是否存在縮短總工期的部分作業(yè)承擔(dān)者的循環(huán)調(diào)整：求nilii1min若0，則uuniliuii0,1,min，轉(zhuǎn)到13；否則（0）轉(zhuǎn)到12。12判斷是否存在減少總用時的部分作業(yè)承擔(dān)者的循環(huán)調(diào)整：求niii1min若0，則uuniiuii0,1,min，轉(zhuǎn)到13；否則（0）

34、轉(zhuǎn)到15。13調(diào)整分配方案：)()(,)(,00urvrvrwpvuu，) 1,2, 1()(0nsstduvs。14若uv，則vuwur00,)(，轉(zhuǎn)到13；否則（uv） ，轉(zhuǎn)到4。15若nk，則1,1,1jikk轉(zhuǎn)到7；否則)(nk，輸出到最優(yōu)分配方案：),2,1()(niir；及各工作的最早開工時間：),2,1()(0nidir。注： （1）如果需要各項工作的松弛時間),2,1()(niir，可以根據(jù)最優(yōu)分配方案),2,1()(niir下的各項工作用時)(iirc),2,1(ni，用定理 2 獲得。也可從1,0 nd開 始 ， 利 用)(iirc與),2,1()(0nidir倒 著 遞

35、推 出 各 項 工 作 的 松 弛 時 間),2,1()(niir。（2）a-pert 問題算法必然在有限次迭代運算中獲得精確最優(yōu)解，其理論依據(jù)為定理5和定理 6。（3）a-pert 問題的算法，是以縮短總工期或總工期不能再縮短時減少總用時為前提，由一個可行分配方案轉(zhuǎn)換到另一個可行分配方案的迭代算法（對于n 個人， n 項工作的分配問題，稱一人做一項工作，每項工作只由一個人做的分配方案為可行分配方案。 ） 。由于， 該問題的所有不同的可行分配方案共有n!種，所以，理論上在最壞情況下，可能要迭代運算n!次才能獲得最優(yōu)分配方案。因此，按迭代次數(shù)統(tǒng)計，a-pert 問題算法的復(fù)雜度為) !(no，屬

36、于指數(shù)算法。 但是，算法的初始可行分配方案，是用最小元素法定出的，而且迭代運算是按總工期遞減或總工期不能縮短時按總用時遞減進(jìn)行的，所以，運算中跳過了大量的不能使13 總工期縮短或總工期達(dá)到最短時，不能減少總用時的分配方案下相關(guān)計算。因此， 如用單純形法求解線性規(guī)劃問題那樣，a-pert 問題算法雖然屬于指數(shù)算法，卻具有適用的計算效率、和穩(wěn)定的數(shù)值結(jié)果， 從我們計算過的一些算例也顯示，用本文給出的算法求解a-pert 問題，實際迭代次數(shù)都遠(yuǎn)遠(yuǎn)少于!n次。如下面一個例子：例 已知某項工程含有8 項工作，各工作之間的緊前緊后關(guān)系如表3所示表 3 工 作緊前工作無無緊后工作無現(xiàn)有 8 個工作組，每個工

37、作組完成各項工作的用時見表4 表 4 用時工作工作組一12 16 14 21 18 7 11 9 二6 9 11 19 12 12 10 7 三14 21 16 12 14 5 23 13 四15 15 27 21 17 19 16 20 五9 13 19 20 15 16 11 14 六23 18 24 10 8 7 15 12 七15 20 8 14 17 6 9 18 八12 16 11 9 10 15 14 8 要求每項工作只能由一個工作組承擔(dān)，每個工作組只能承擔(dān)一項工作。研究： 如何進(jìn)行工作分配， 使完成該項工程的總工期最短的前提下，所有工作組的用時之和最少，并求出這種要求下各項工作

38、的最早開工時間、最遲開工時間、松弛時間。解 由算法步驟2和算法步驟3分別得到初始分配方案和當(dāng)前各項工作的最早開工時間，見表5。表 5 工作 1 工作 2 工作 3 工作 4 工作 5 工作 6 工作 7 工作 8 工作組2 5 7 4 6 3 1 8 最早開工時間0 0 6 13 13 34 21 39 此時，總工期為47，總用時為80。通過算法步驟4-15由一個可行分配方案轉(zhuǎn)換到另一個總工期更短或總工期最短時總用時更少的可行分配方案，共進(jìn)行11 次轉(zhuǎn)換（這遠(yuǎn)遠(yuǎn)小于8！次） ，便得到最優(yōu)分配方案及最優(yōu)工程計劃下的各項工作的最早開工時間見表6。在此基礎(chǔ)上，還可得到最優(yōu)分配方案下各項工作的松弛時間

39、見表6。表 6 工作 1 工作 2 工作 3 工作 4 工作 5 工作 6 工作 7 工作 8 工作組4 2 7 8 6 3 5 1 最早開工時間0 0 15 9 9 23 17 28 松弛時間0 0 0 5 0 0 0 0 此時，總工期為37，總用時為74。14 5、結(jié)束語在關(guān)鍵作業(yè)上增加人力、物力、技術(shù)的投入，可以減少關(guān)鍵作業(yè)的用時，并且，在一定程度上能達(dá)到縮短總工期，提高生產(chǎn)效率的目的12，但是，值得注意的是，使用這種方法必然要加重成本的投入，更何況并非所有關(guān)鍵作業(yè)都能減少用時。另外， 不論減少多少關(guān)鍵作業(yè)的用時，總工期也不會短于pert 網(wǎng)絡(luò)的次最長路。因此，當(dāng)pert 網(wǎng)絡(luò)的最長路與

40、次最長路相差無幾時，通過減少關(guān)鍵作業(yè)的用時來縮短總工期，效果是微不足道的。例如，某個工程由9 個作業(yè)項目構(gòu)成，這 9 個作業(yè)項目間的緊前緊后關(guān)系如圖2 所示，每條邊上的數(shù)字，表示對應(yīng)作業(yè)的用時。4 6 3 7 （圖 2）8 12 10 9 不難看出該工程的總工期為20，不論將關(guān)鍵作業(yè)（粗箭線對應(yīng)的作業(yè)）的用時如何縮短，新的總工期都不會短于19。本文的研究的a-pert問題，是一種不額外投入人力、物力和財力的情況下，充分利用現(xiàn)有資源， 最大限度地提高生產(chǎn)效率優(yōu)化問題。所給算法， 不但能獲得使總工期最短的分配方案， 而且能保證總工期最短的情況下，使總用時最少。 這種算法有穩(wěn)定的計算性能和適用的計算

41、效率，可在企業(yè)特別是大型企業(yè)的生產(chǎn)任務(wù)分配與進(jìn)度計劃制定中發(fā)揮重要的作用。另外， 由于這種算法獲得的是精確最優(yōu)解，所以， 可以供各種近似算法進(jìn)行近似最優(yōu)解的精確程度比較， 這比目前許多文獻(xiàn)采用的近似最優(yōu)解與近似最優(yōu)解的優(yōu)劣比較更客觀，更能說明問題。參考文獻(xiàn)1garey m.r., johnson ds., computers and intractability-a guide to the theory of np-completeness, new york: freeman w.h.and co. 1979 2wu m y,gajski d d,hypertool.a programmi

42、ng aid formessage-passing systems.ieee trans parallel and distributed systems.1990,1(3):330-343 3hwang j j, chow y c, anger f d,lee c y. scheduling precedence graphs in systems with interprocessor communication times. siam journal on computing.1989, 18(2):244-257 4sih g c and lee e a. a compile-time

43、 scheduling heuristic for interconnection- constrained heterogeneous processor architectures. ieee trans parallel and distributed systems. 1993,4(2):75-87 5 石威、鄭緯民，相關(guān)任務(wù)圖的均衡動態(tài)關(guān)鍵路徑調(diào)度算法。計算機(jī)學(xué)報，2001，24（9） ：991-997 shi wei ，zheng wei-min.the balanced dynamic critical path scheduling algorithm of dependent

44、 task graphs. chinese journal of computers. 2001，24（9） ：991-997 6 尚明生，相關(guān)任務(wù)圖的一種有效并行調(diào)度算法。計算機(jī)工程，2005,31(14): 18-20，29 shang ming-sheng. efficient algorithm for scheduling dependent task graphs on multi-processor system. computer engineering. 2005,31(14): 18-20，29 15 7 蔣延耀、李慶華，dag任務(wù)圖的一種調(diào)度算法。小型微型計算機(jī)系統(tǒng)，20

45、03，24（10） ：1796-1799 jiang ting-yao; li qing-hua.a scheduling algorithm for dag task graphs.journal of chinese computer systems. 2003，24（10） ：1796-1799 8 kwok yu-kwong, ishfaq ahumad, efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. journal of para

46、llel and distributed computing, 1997,47(1): 58-77 9 鐘求喜、謝濤、陳火旺，任務(wù)分配與調(diào)度的共進(jìn)化方法。計算機(jī)學(xué)報，2001,24(3): 308314 zhong qiu-xi, xie tao, chen huo-wang. task allocation & scheduling by computational model of coevolution. chinese journal of computers. 2001,24(3): 308314 10 郭 強(qiáng) ， 分 配 問 題 的 一 種 新 的 迭 代 算 法 。 系

47、統(tǒng) 工 程 與 電 子 技 術(shù) ， 2004,26(12): 1915-1916,1949 guo qiang. new iterative algorithm for an assignment problem. systems engineering and electronics. 2004,26(12): 1915-1916,1949 11 郭強(qiáng)， pert問題的新算法。數(shù)學(xué)的實踐與認(rèn)識，2003,33(2): 48-51 guo qiang. a new algorithm of pert. mathematics in practice and theory. 2003,33(2)

48、: 48-51 12 尹建偉、韓偉力、陳剛、董金祥，項目工期調(diào)整的公平負(fù)擔(dān)算法。計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報， 2002,14(3): 270-274 yin jian-wei,han wei-li,chen gang,dong jin-xiang. fair algorithm of goal-driven time limit modification for a project. journal of computer-aided design & computer graphics. 2002,14(3): 270-274 作者簡介 ：郭強(qiáng)，男，漢族，1961 年 4 月出生，理

49、學(xué)碩士，副教授。主要研究方向：最優(yōu)化理論與算法，運籌與網(wǎng)絡(luò)規(guī)劃。guo qiang, born in 1961, associate professor, master of science. his research interests include the theory and algorithm of optimization, operational research and mathematics programming in network. e-mail: 16 研究背景基于相關(guān)任務(wù)分配的網(wǎng)絡(luò)計劃問題屬于運籌學(xué)領(lǐng)域，是分配問題和計劃評審技術(shù)問題的綜合與推廣，其一般性描述為：某工

50、程由n項具有緊前、緊后關(guān)系的工作構(gòu)成，現(xiàn)要安排)(nm個人去完成這n項工作。規(guī)定每項工作只能由一個人承擔(dān)，每個人至少承擔(dān)一項工作。已知第i個人完成第j項工作業(yè)需用時), 2, 1;,2,1(njmicij。要研究的問題是：如何進(jìn)行人與工作之間的分配， 使得完成該項工程的總工期最短，并在此條件下， 使得用于所有工作的用時之和最少，并給出這種要求下，各項工作的最早開工時間和松弛時間。這樣的問題在現(xiàn)代企業(yè)，特別是現(xiàn)代大型企業(yè)的生產(chǎn)計劃制定和管理中有著重要的運用。目前國內(nèi)外對這種問題，都是在nm的情況下， 研究如何尋找使總工期最短的分配方案。由于這是一個np-hard 問題，因此，現(xiàn)有的研究成果，采用

51、的都是近似算法，而且也沒有涉及到使總工期最短的前提下，再使總用時最少的問題。與此不同是， 本文針對nm的情況， 給出了使總工期達(dá)到最短的前提下，又使總用時最少的精確算法。雖然，這種算法不是多項式時間算法，但是， 這種算法始終是按總工期長度遞減的方向進(jìn)行迭代運算的，一旦總工期達(dá)到最短時，便能在總工期保持不變的情況下，始終按總用時最少的方向進(jìn)行迭代運算。因此，該算法有適用的計算效率和穩(wěn)定的計算性能。對于nm的情況下，如何尋找上述問題的精確算法，這一問題我們還未解決。但是，我們已研究出了nm的情況下，n項工作無緊前緊后關(guān)系時，獲取使總工期最短，及在此前提下，使總用時最少的精確算法，其將另文給出。ba

52、ckground the problem of network plan based on the assignment of dependent tasks is the integration and generalization of assignment problem and pert problem (program evaluation and review technique) ，and belong to operational research field. the problem generally is described as follow: the engineering consists of ntasks with precedence and successor relationship. each task can only be taken by one person, and every person must take at least one task when )(nm persons are assigned to complete those ntasks. let ijcis the time that ith p