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

2、優分配方案、總工期及各項工作的最早開工時間和松弛時間。關鍵詞：分配問題；PERT問題；A-PERT問題； Floyd算法；最早開工時間；松弛時間。An Algorithm of Network planBased on Dependent Task Assignment Guo QiangDepartment of Applied Mathematics, School of Science , Northwestern Polytechnical University, Xian 710072Abstract: How assigning the jobs with precedence a

3、nd 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 other jobs

4、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 when the

5、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 start time

6、and relaxation time of every job can be obtained.Keywords: assignment problem; PERT problem; A-PERT problem; Floyd algorithm; earliest starting time; relaxation time1、引言研究如何把具有緊前緊后關系的任務集分配給現有的人員（或設備），在保證完成任務集的總工期最短的前提下，使總用時最少，是一種充分利用現有的人力和物力，最大限度地提高工作效率的優化問題。這樣的優化問題，在生產調度、機械加工、以及工程計劃制定與管理等活動中，無疑有著重要

7、的應用價值。但是要解決這樣的問題，卻并不容易，文獻1證明了使總工期最短的問題是一個NP-hard問題，不存在多項式時間的算法，在問題規模較大的情況下，很難獲得精確最優解。因此，人們對這類問題的研究，普遍著眼于尋找近似最優解或稱滿意解的算法上，以及如何提高近似最優解的精度和計算效率。如，文獻2 給出了一種MCP近似算法，文獻3 給出了一種ETF近似算法，文獻4 給出了一種DLS近似算法，文獻5總結分析了文獻2和3，給出了一種BDCP近似算法，文獻6和7又在上述近似算法的基礎上，給出了新的近似算法。文獻8和文獻9 則給出了不同的遺傳算法。研究這類問題的近似算法的文獻還有很多，但是，卻很難找到研究這

8、類問題的精確最優解的文獻。另外，目前對這類問題的研究都集中在如何獲取最短的總工期的問題上，而沒有注意到使總工期最短的分配方案通常會有多種，而且，使總工期達到最短的不同分配方案的總用時往往不同，甚至有較大的差異，舉一個簡單例子：某項工程由三項工作構成，各工作間的緊前、緊后關系如圖1。 工作1 工作2 （圖1） 工作3已知三個人承擔這三項工作的用時情況見表1。 表1用時（周） 工作 人工作1工作2工作3甲838乙2711丙8913通過窮舉，可以得到所有分配方案下的總用時與總工期，見表2。 表2工作1工作2工作3總工期總用時方案1（用時）甲 8乙 7丙 131528方案2（用時）甲 8丙 9乙 11

9、1728方案3（用時）乙 2甲 3丙 131318方案4（用時） 乙 2 丙 9 甲 81119方案5（用時） 丙 8 甲 3 乙 111122方案6（用時） 丙 8 乙 7 甲 81523從表2中可看出，按第4、第5套方案進行分配，總工期最短，為11周，但是，第4套分配方案的總用時為19周，比第5套分配方案的總用時22周要少花費3周時間，因此，選擇第4套分配方案，不但能使總工期達到最短，而且可以使總用時相對較少。為此，本文提出了一種如何尋找相關任務的分配方案，使總工期達到最短的情況下，使總用時最少的問題，本文將這種問題稱為A-PERT問題。無疑，這是一個新的、有意義的現實問題。2、A-PER

10、T問題的特征及其數學模型A-PERT問題的完整描述如下：某項工程由項工作構成，各工作之間具有已知的緊前、緊后關系，現有個人可參與這項工程。規定每項工作只能由一個人承擔。已知第個人完成第項工作需用時。研究：要完成這項工程中的所有工作應如何進行分配，才能夠使總工期最短，并在此條件下，使用于所有工作上的時間之和最少，以及在這種要求下的總工期、各項工作的最早開工時間和松弛時間。A-PERT問題涉及到三種情況，統一的要求是每項工作只能由一個人承擔，不同的要求是，時，每個人至少承擔一項工作；時，每個人只承擔一項工作；時，每個人至多承擔一項工作。設 用表示按進行分配時，所需總工期。A-PERT問題的數學模型

11、為：其中，為參變量。當時，；當時，。這是一個雙層0-1整數規劃，雖然可以用窮舉法求解，即，計算出所有不同分配方案下的總工期，通過比較，可以選出總工期最短時總用時最少的分配方案（最優解）。但是這樣的方法計算量太大，在時，要計算次PERT問題；在時，要計算n！次PERT問題；在時，要計算次PERT問題。所以，在A-PERT問題的規模較大時，這種方法顯然是不可行的。本文將針對情況，介紹一種借助Floyd算法規則求解A-PERT問題的精確算法，以此為基礎，有利于進一步研究和兩種情況下的A-PERT問題。3、A-PERT問題的算法理論從上述A-PERT問題的描述可以看出，在A-PERT問題所給條件下，如

12、果只求總用時最少的分配方案，則涉及的便是經典分配問題；如果給定了分配方案，再求總工期及各項工作的最早開工時間和松弛時間，則涉及的便是經典的計劃評審技術問題，又稱PERT問題。因此，求解A-PERT問題，可以借鑒文獻10中求解經典分配問題的方法：按照一定的規律，反復從一種分配方案變換到另一種總用時更少的分配方案，直到最終獲得總用時最少的分配方案。即，按照以下思路解決A-PERT問題：按照一定的規律，反復從一種分配方案變換到另一種總工期更短或總工期不增的情況下總用時更少的分配方案，直到最終獲得總工期最短的情況下總用時最少的分配方案。要實現這樣的目的，關鍵是找出上面提到的規律。另外，要使算法具有實用

13、的計算效率，應盡量降低迭代過程中出現的每一種分配方案下的總工期和總用時的計算量。研究表明，再借鑒文獻11中求解PERT問題的算法，便可以實現這一目的，達到這樣的要求。為此，先給出文獻10和文獻11中的相關理論。定理1 設為上述問題的一個可行分配方案（表示安排第個人承擔第項工作），（為第個人承擔第項工作的用時，為第個人承擔第項工作的用時，是用于記錄人員調整的方法。）。則通過下面兩步運算： 若，則；否則都不變。轉到。 求，當，時，轉到可獲得以下信息：（1）當時，意味著找到了一個可減少總用時的循環調整方案：記，在時，轉到，直到為止。（2）當的過程中，始終，意味著當前的分配方案已經是總用時最少的分配方

14、案。證 參見文獻10。定義1 已知一項工程由個具有緊前、緊后關系的工作構成，第項工作需用時。若第項工作無緊前工作時，則令第0項工作為其緊前工作；若第項工作無緊后工作時，則令第n+1項工作為其緊后工作，。設則稱矩陣為初始PERT矩陣，對應的網絡稱為復線PERT網絡。顯然，一個初始PERT矩陣對應著一個有向網絡，第項工作對應著第個節點（），節點到相鄰可達的節點的邊長為第項工作的用時。節點不相鄰可達節點時，令，是為了便于計算。定義2 若矩陣中的元素表示復線PERT網絡中節點到節點的最長路值，則稱該矩陣為最優PERT矩陣。定理2 設為初始PERT矩陣，則通過下列運算： 若，則；否則不變。轉到。若，則，

15、轉到；否則，輸出。得到的矩陣是最優PERT矩陣，且有下列結果：（1）第項工作的最早開工時間為；（2）第項工作的最早完工時間為；（3）完成該項工程所需總工期為；（4）第項工作的松弛時間為；（5）第項工作的最遲開工時間為；（6）第項工作的最遲完工時間為。證 參見文獻11。定理1給出了一種尋找總用時最少的分配方案的方法，定理2給出了一種在每一項工作的用時都確定的情況下，獲取總工期及各項工作最早開工時間和松弛時間的方法。當某一項工作的用時被改變，其它相關工作的最早開工時間是否會發生變化，如何變化，具有以下規律：定理3 設為最優PERT矩陣。若，則改變第項工作的用時，不會影響第項工作的最早開工時間。證

16、由最優PERT矩陣知，時，意味著第項工作不是第項工作的的后繼工作，所以，則改變第項工作的用時，不會影響第項工作的最早開工時間。定理4 設第項工作的最早開工時間為，用時為又設第s項工作是第k項工作的任意一個緊后工作，則當第k項工作的用時改變時，下列結論成立：（1）不存在時，第k項工作的緊后工作的最早開工時間變為，最早開工時間的改變量為。（2）存在時，第k項工作的緊后工作的最早開工時間變為，最早開工時間的改變量為。證 （1）不存在時，說明第k項工作是其緊后工作的唯一緊前工作，所以第k項工作完成后，第k項工作的緊后工作即可開工，而第k項工作的最早開工時間為，用時為，所以，第k項工作的緊后工作的最早開

17、工時間為。（2）存在時，說明第k項工作不是其緊后工作的唯一緊前工作，所以只有當第項工作的所有緊前工作都完成后，第項工作才能開工，而是第項工作的完工時間最晚的緊前工作的完工時間，所以，第k項工作的緊后工作的最早開工時間為。推論 在定理5的條件下，當第k項工作的最早開工時間改變時，下列結論成立：（1）不存在時，第k項工作的緊后工作的最早開工時間變為，最早開工時間的改變量為。（2）存在時，第k項工作的緊后工作的最早開工時間變為，最早開工時間的改變量為。證 與定理5完全類似，略。如果第項工作的最早開工時間改變時，我們引入則根據定理3和定理4及其推論可知，在第項工作的用時改變后，第項工作的所有前期工作的

18、最早開工時間不變，而所有后期工作的最早開工時間可通過下面運算獲得： 求 求， 若不存在，則；否則（存在）。 若，則，轉到；否則（）直接轉到。 若，則轉到；否則（），轉到。 若，則轉到；否則（）轉到。 若，則轉到；否則（）停。為便于論述，用表示第項工作用時改變后，由上述運算步驟得到的第項工作的最早開工時間，則按Floyd算法規則執行運算，可獲得以下運算規律：定理5 設為第人做第項工作的用時，為一個可行分配方案，是對應該分配方案的最優PERT矩陣。表示將第人承擔第項工作改為第人承擔第項工作后，造成第項工作的用時改變量，表示第項工作用時改變后，第s項工作的最早開工時間，表示第項工作用時改變后，總工期

19、的改變量，再引入人員調換記錄，則通過下面兩步運算： 若時，則，；否則，都不變。轉到。 求，當，時，轉到可獲得以下信息：（1）當時，意味著找到了一個可縮短總工期的循環調整方案：記，在時，轉到，直到為止。（2）當的過程中，始終，意味著當前的分配方案已經是總工期最短的分配方案。證 （1）因為，如果存在一個分配方案：安排第人做第項工作，第人做第項工作， ，第人做第項工作時的總工期比安排第人做第項工作時的總工期短，則是的一個全排列。為了便于論述，不妨設（其它情況證明類似），則用第人替換第1人，第人替換第2人，第人替換第人，總工期便會縮短。因此，以下必有一組按次序執行的運算式成立： 因為，這組按次序執行的

20、運算，都屬于定理中的、兩步運算的搜索范圍，只是執行的是能夠成立的一組，又因為運算前，所以執行、的結果是中必有一個小于0，所以，用記錄到的調整過程，按定理中的、進行調整，便得到一個總工期更短的分配方案。（2）對（1）的證明已揭示，只要存在比當前分配方案下的總工期更短的分配方案，定理中的、兩步運算一定能將其找出來。同時也表明，如果當前的分配方案已經使總工期達到最短了，則在的過程中，按定理中的、兩步運算，始終不會出現，所以，始終不變，故，即始終成立。定理6 設分配方案使總工期達到了最短，則通過下面兩步運算： 若，且，則，；否則，都不變。轉到。 求，當，時，轉到可獲得以下信息：（1）當時，意味著找到了

21、一個可減少總用時的循環調整方案：記，在時，轉到，直到為止。（2）當的過程中，始終，意味著在保持總工期不變的前提下，當前的分配方案已經使總用時到了最少。證 類似于定理5的證明，略。4、A-PERT問題的程序算法上述A-PERT問題的算法理論揭示，求解A-PERT問題， 可以按下面模塊化的算法流程圖進行：給定初始分配方案：用定理2求該分配方案下的最優PERT矩陣按定理3、定理4及推論：yesnonoyes 用定理5按照記錄，調整分配方案：，同時更新每一項工作的最早開工時間： 判斷是否存在總工期更短的分配方案 用定理6判斷是否存在總工期不變但總用時減少的分配案輸出最優分配方案：及每項工作的最早開工時

22、間：，其中為總工期。求解A-PERT問題的精確最優解的具體算法步驟如下： 輸入已知數據：， 用最小元素法定初始分配方案：。 用定理2求最優PERT矩陣： 按照定理3和定理4，計算將第項工作改由第人承擔后，第項工作的最早開工時間：，對應的總工期的改變量：，記錄調整過程：，。 計算逐步增加改變工作承擔者的工作后，搜尋使總工期變短或總工期不變時使總用時變少的調整方案：。 若，則，轉到；否則轉到。 若且，則，轉到；否則直接轉到。 若，則轉到；否則（）轉到。 若，則轉到；否則（）轉到。 判斷是否存在縮短總工期的部分作業承擔者的循環調整：求若，則，轉到；否則（）轉到。 判斷是否存在減少總用時的部分作業承擔

23、者的循環調整：求 若，則，轉到；否則（）轉到。 調整分配方案：，。 若，則，轉到；否則（），轉到。 若，則轉到；否則，輸出到最優分配方案：；及各工作的最早開工時間：。注：（1）如果需要各項工作的松弛時間，可以根據最優分配方案下的各項工作用時，用定理2獲得。也可從開始，利用與倒著遞推出各項工作的松弛時間。（2）A-PERT問題算法必然在有限次迭代運算中獲得精確最優解，其理論依據為定理5和定理6。（3）A-PERT問題的算法，是以縮短總工期或總工期不能再縮短時減少總用時為前提，由一個可行分配方案轉換到另一個可行分配方案的迭代算法（對于n個人，n項工作的分配問題，稱一人做一項工作，每項工作只由一個人

24、做的分配方案為可行分配方案。）。由于，該問題的所有不同的可行分配方案共有n!種，所以，理論上在最壞情況下，可能要迭代運算n!次才能獲得最優分配方案。因此，按迭代次數統計，A-PERT問題算法的復雜度為，屬于指數算法。但是，算法的初始可行分配方案，是用最小元素法定出的，而且迭代運算是按總工期遞減或總工期不能縮短時按總用時遞減進行的，所以，運算中跳過了大量的不能使總工期縮短或總工期達到最短時，不能減少總用時的分配方案下相關計算。因此，如用單純形法求解線性規劃問題那樣，A-PERT問題算法雖然屬于指數算法，卻具有適用的計算效率、和穩定的數值結果，從我們計算過的一些算例也顯示，用本文給出的算法求解A-

25、PERT問題，實際迭代次數都遠遠少于次。如下面一個例子：例 已知某項工程含有8項工作，各工作之間的緊前緊后關系如表3所示 表3工 作緊前工作無無緊后工作無現有8個工作組，每個工作組完成各項工作的用時見表4 表4用時 工作工作組一12161421187119二6911191212107三142116121452313四1515272117191620五913192015161114六23182410871512七1520814176918八12161191015148要求每項工作只能由一個工作組承擔，每個工作組只能承擔一項工作。研究：如何進行工作分配，使完成該項工程的總工期最短的前提下，所有工作

26、組的用時之和最少，并求出這種要求下各項工作的最早開工時間、最遲開工時間、松弛時間。 解 由算法步驟和算法步驟分別得到初始分配方案和當前各項工作的最早開工時間，見表5。表5工作1工作2工作3工作4工作5工作6工作7工作8工作組25746318最早開工時間0061313342139此時，總工期為47，總用時為80。 通過算法步驟-由一個可行分配方案轉換到另一個總工期更短或總工期最短時總用時更少的可行分配方案，共進行11次轉換（這遠遠小于8！次），便得到最優分配方案及最優工程計劃下的各項工作的最早開工時間見表6。在此基礎上，還可得到最優分配方案下各項工作的松弛時間見表6。表6工作1工作2工作3工作4

27、工作5工作6工作7工作8工作組42786351最早開工時間001599231728松弛時間00050000此時，總工期為37，總用時為74。5、結束語在關鍵作業上增加人力、物力、技術的投入，可以減少關鍵作業的用時，并且，在一定程度上能達到縮短總工期，提高生產效率的目的12，但是，值得注意的是，使用這種方法必然要加重成本的投入，更何況并非所有關鍵作業都能減少用時。另外，不論減少多少關鍵作業的用時，總工期也不會短于PERT網絡的次最長路。因此，當PERT網絡的最長路與次最長路相差無幾時，通過減少關鍵作業的用時來縮短總工期，效果是微不足道的。例如，某個工程由9個作業項目構成，這9個作業項目間的緊前緊

28、后關系如圖2所示，每條邊上的數字，表示對應作業的用時。 46 3 7 （圖2） 8 12 10 9不難看出該工程的總工期為20，不論將關鍵作業（粗箭線對應的作業）的用時如何縮短，新的總工期都不會短于19。本文的研究的A-PERT問題，是一種不額外投入人力、物力和財力的情況下，充分利用現有資源，最大限度地提高生產效率優化問題。所給算法，不但能獲得使總工期最短的分配方案，而且能保證總工期最短的情況下，使總用時最少。這種算法有穩定的計算性能和適用的計算效率，可在企業特別是大型企業的生產任務分配與進度計劃制定中發揮重要的作用。另外，由于這種算法獲得的是精確最優解，所以，可以供各種近似算法進行近似最優解

29、的精確程度比較，這比目前許多文獻采用的近似最優解與近似最優解的優劣比較更客觀，更能說明問題。參考文獻1Garey M.R., Johnson Ds., Computers and Intractability-A Guide to the Theory of NP-Completeness, New York: Freeman W.H.and Co. 19792Wu M Y,Gajski D D,Hypertool.A programming aid formessage-passing systems.IEEE Trans Parallel and Distributed Systems.1

30、990,1(3):330-3433Hwang 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-2574Sih G C and Lee E A. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor arch

31、itectures. IEEE Trans Parallel and Distributed Systems. 1993,4(2):75-875石威、鄭緯民，相關任務圖的均衡動態關鍵路徑調度算法。計算機學報，2001，24（9）：991-997 SHI Wei ，ZHENG Wei-Min. The Balanced Dynamic Critical Path Scheduling Algorithm of Dependent Task Graphs. Chinese Journal of computers. 2001，24（9）：991-9976尚明生，相關任務圖的一種有效并行調度算法。計

32、算機工程，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，297蔣延耀、李慶華，DAG任務圖的一種調度算法。小型微型計算機系統，2003，24（10）：1796-1799 JIANG Ting-yao; LI Qing-hua. A Scheduling Algorithm for DAG Task Graphs.J

33、ournal of Chinese Computer Systems. 2003，24（10）：1796-17998 Kwok Yu-Kwong, Ishfaq Ahumad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. Journal of Parallel and Distributed Computing, 1997,47(1): 58-779鐘求喜、謝濤、陳火旺，任務分配與調度的共進化方法。計算機學報，2001,24(3): 30

34、8314 ZHONG Qiu-xi, XIE Tao, CHEN Huo-wang. Task Allocation & Scheduling by Computational Model of Coevolution. Chinese Journal of computers. 2001,24(3): 30831410郭強，分配問題的一種新的迭代算法。系統工程與電子技術，2004,26(12): 1915-1916,1949 GUO Qiang. New iterative algorithm for an assignment problem. Systems Engineerin

35、g and Electronics. 2004,26(12): 1915-1916,194911郭強，PERT問題的新算法。數學的實踐與認識，2003,33(2): 48-51 GUO Qiang. A New Algorithm of PERT. Mathematics in Practice and theory. 2003,33(2): 48-5112尹建偉、韓偉力、陳剛、董金祥，項目工期調整的公平負擔算法。計算機輔助設計與圖形學學報，2002,14(3): 270-274 YIN Jian-wei,HAN Wei-li,CHEN Gang,DONG Jin-xiang. Fair Al

36、gorithm of Goal-Driven Time Limit Modification for a Project. Journal of Computer-Aided design & Computer Graphics. 2002,14(3): 270-274 作者簡介：郭 強，男，漢族，1961年4月出生，理學碩士，副教授。主要研究方向：最優化理論與算法，運籌與網絡規劃。 Guo Qiang, born in 1961, associate professor, Master of Science. His research interests include the th

37、eory and algorithm of optimization, operational research and mathematics programming in network.E-mail: guoqiang研究背景 基于相關任務分配的網絡計劃問題屬于運籌學領域，是分配問題和計劃評審技術問題的綜合與推廣，其一般性描述為： 某工程由項具有緊前、緊后關系的工作構成，現要安排個人去完成這項工作。規定每項工作只能由一個人承擔，每個人至少承擔一項工作。已知第個人完成第項工作業需用時。要研究的問題是：如何進行人與工作之間的分配，使得完成該項工程的總工期最短，并在此條件下，使得用于所有工作的

38、用時之和最少，并給出這種要求下，各項工作的最早開工時間和松弛時間。這樣的問題在現代企業，特別是現代大型企業的生產計劃制定和管理中有著重要的運用。目前國內外對這種問題，都是在的情況下，研究如何尋找使總工期最短的分配方案。由于這是一個NP-hard問題，因此，現有的研究成果，采用的都是近似算法，而且也沒有涉及到使總工期最短的前提下，再使總用時最少的問題。與此不同是，本文針對的情況，給出了使總工期達到最短的前提下，又使總用時最少的精確算法。雖然，這種算法不是多項式時間算法，但是，這種算法始終是按總工期長度遞減的方向進行迭代運算的，一旦總工期達到最短時，便能在總工期保持不變的情況下，始終按總用時最少的

39、方向進行迭代運算。因此，該算法有適用的計算效率和穩定的計算性能。對于的情況下，如何尋找上述問題的精確算法，這一問題我們還未解決。但是，我們已研究出了的情況下，項工作無緊前緊后關系時，獲取使總工期最短，及在此前提下，使總用時最少的精確算法，其將另文給出。BackgroundThe problem of network plan based on the assignment of dependent tasks is the integration and generalization of assignment problem and PERT problem (Program Evaluat

40、ion and Review Technique) ，and belong to operational research field. The problem generally is described as follow: the engineering consists of tasks with precedence and successor relationship. Each task can only be taken by one person, and every person must take at least one task when persons are as

41、signed to complete those tasks. Let is the time that th person takes to complete th task. The objective of the research is how assigning those jobs to every person so that the engineering period is the shortest, and in this premise the total time of completing all those jobs is the least. Finally the algorithm must give the earliest start time and relaxation time for each task. Such problem has important app