1、改良的DFS算法實現(xiàn)資源約束條件下多工程的調(diào)度摘要：在競爭劇烈的當今社會，越來越多的企業(yè)面對多工程管理的問題。如何有效的調(diào)度各個工程，是企業(yè)所面臨的一個難題。本文從另一種算法DFS，Depth-First Search，深度優(yōu)先搜索著手來分析多工程的調(diào)度管理問題，并結合實例進行分析，從而驗證算法的有效性。論文關鍵詞：多工程,多工程管理,DFS一、引言當今，越來越多的企業(yè)或組織采用工程這一形式進行變革或創(chuàng)新，以面對日益劇烈的市場競爭。工程，作為21世紀的新寵;，簡單地說，就是在特定的時間、預算、資源限定內(nèi)，為實現(xiàn)某種目的而相互聯(lián)系的一次性工作任務。一般來說，工程具有如下的根本特點：1一次性一次性

2、是工程與其他重復性運行或操作工作最大的一個區(qū)別。工程有明確的起點和終點，沒有可以完全照搬的先例，也不會有完全相同的復制。工程的其他屬性都是從這一特點衍生出來的。2獨特性每個工程都是獨特的?；蛘咂涮峁┑漠a(chǎn)品或效勞有其自身的特點；或者其提供的產(chǎn)品或效勞雖然與其他工程類似，但是其時間和地點，內(nèi)部和外部的環(huán)境，自然和社會條件卻有別于其他工程，因此工程的過程總是獨一無二的，不可能存在完全相同的兩個工程。3目標確實定性工程必需要有確定的目標：(a)時間性目標，即在規(guī)定的時段內(nèi)或規(guī)定的時點之前完成；(b)成果性目標，即提供某種規(guī)定的產(chǎn)品或效勞；(c)約束性目標，即不超過規(guī)定的資源限制；(d)其他需滿足的要求

3、，包括必須滿足的要求和盡量滿足的要求；目標確實定性允許有一個變動的幅度，也就說目標是可以修改。不過一旦工程目標發(fā)生實質(zhì)性的變化，它就不再是原來的工程了，而將產(chǎn)生一個新的工程。4活動的整體性工程中的一切活動都是有聯(lián)系的，構成一個統(tǒng)一的整體。多余的活動是不必要的，缺少某些活動必將損害工程目標的實現(xiàn)。5組織的臨時性和開放性工程團隊在工程的全過程中，其人數(shù)，成員，職責總是在不斷變化的。某些成員是借調(diào)來的，工程終結時團隊要解散，人員要轉移。參與工程的組織往往有多個，甚至幾十個或更多，這些組織按矩陣型結構排列。他們通過協(xié)議或合同以及其他的社會關系組織到一起，在工程的不同時段不同程度的介入工程活動。可以說，

4、工程組織沒有嚴格的邊界，是臨時性的開放性的。這一點與一般企、事業(yè)單位和政府機構組織不一樣。6成果的不可挽回性工程的一次性屬性決定了工程不同于其他事情可以先試著做，如果作壞了還可以重來；也不同于產(chǎn)品的生產(chǎn)批量，合格率達99.99%就認為是很好的了。工程在一定條件下啟動，一旦失敗就永遠失去了重新進行原工程的時機。所以工程有很大的不確定性和風險性。二、多工程管理以上是我們理論意義上的工程，但在實際當中，企業(yè)面對的更多是單工程與多工程的問題。單工程的調(diào)度管理相比而言，比擬容易處理，運用傳統(tǒng)的一些技術，比方CPM，PERT，就可以很好的解決單個工程的管理。而多工程管理的問題比擬棘手，涉及到在有限資源的約

5、束下調(diào)度各個工程，以保證提高企業(yè)整體的效率。本文就是來著重闡述資源受限情況下的多工程調(diào)度問題。1.多工程管理的概念多工程管理是指在工程經(jīng)理和工程組織的共同努力下，綜合運用系統(tǒng)理論和方法對工程及其資源進行方案、組織、協(xié)調(diào)、控制，旨在實現(xiàn)工程的特定目標的管理方法體系。多工程管理是站在企業(yè)層面對現(xiàn)行組織中的所有工程進行篩選、評估、方案、執(zhí)行與控制的工程管理方式。與單工程管理不同，單工程管理是假定在資源充分得到保障的前提下進行的管理，而多工程管理是在企業(yè)存在多工程的前提下，如何合理的分配企業(yè)有限的資源，以到達企業(yè)整體的效率最高。2.實施多工程管理的優(yōu)點a)從企業(yè)戰(zhàn)略目標出發(fā)。多工程管理的實質(zhì)就是合理在

6、工程之間分配企業(yè)有限的資源，是從整體的角度來考慮，是以企業(yè)總的戰(zhàn)略目標為指導的！b)提高資源的利用率。資源在各個工程之間進行有效的分配，不會出現(xiàn)所謂的資源閑置的情況，極大地提高資源的利用率和優(yōu)化度！c)降低工程實施的風險。采用單工程的管理思維去管理多工程，很容易在工程的進度、資源的合理安排上產(chǎn)生風險，而多工程的管理思維卻可以很好的解決這個問題。d)加強組織內(nèi)部的溝通與交流。多工程的管理，更進一步的把職能部門和工程組聯(lián)系在一起，不僅各個工程之間的聯(lián)系加強，工程和其他非工程部門的聯(lián)系也進一步加強，這都是以企業(yè)總體目標的為導向的。三、DFS算法描述1.圖的定義圖graph是數(shù)據(jù)結構G=V，E，其中V

7、G是G中的結點的有限非空集合，結點的偶對稱為邊edge，EG是G中邊的有限集合。圖的的結點稱為頂點vertices。有向圖，假設圖G中的每條邊都是有方向的，那么稱G為有向圖(Digraph)。在有向圖中，一條有向邊是由兩個頂點組成的有序對，有序對通常用尖括號表示。有向邊也稱為弧(Arc)，邊的始點稱為弧尾(Tail)，終點稱為弧頭(Head)。2.深度優(yōu)先搜索(Depth-First Search，DFS)假設給定圖G的初態(tài)是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發(fā)點(源點)，那么深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點v，并將其標記為已訪問過；然后依次從v出發(fā)搜索v的每個鄰接點w。假

8、設w未曾訪問過，那么以w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。假設此時圖中仍有未訪問的頂點，那么另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。圖的深度優(yōu)先遍歷類似于樹的前序遍歷。采用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優(yōu)先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優(yōu)先遍歷。3.改良的DFS算法過程首先建立兩個數(shù)組序列，記為Ai，j=1，2，3n，T表示任兩個接點之間的遍歷時間，T12表示接點1和2之間的遍歷時

9、間，Bn=1，2，3n，表示接點下面開始進行檢索，并填充至B中。設x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發(fā)的未檢測過的邊(x，y)。假設發(fā)現(xiàn)頂點y已訪問過，那么重新選擇另一條從x出發(fā)的未檢測過的邊，否那么沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時，假設x不是源點，那么回溯到在x之前被訪問過的頂點；否那么圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，

10、遍歷過程結束。由于一個圖的遍歷結果不止一種，我們要討論：當一個接點僅有一個鄰接接點時，添加至B中，當一個接點假定為M下一個遍歷的接點都是多個時，我們選取與M接點時間最長的下一個接點假定為N，我們將接點N添加至B中。這是因為到并行工作的進度取決于工時最長的活動，要注意，嚴格按照順序依次添加。添加完畢，形成一個完整的B數(shù)組序列，將數(shù)組B中接點依次按兩兩組合的形式添加至A中i和j的位置，形成完整A數(shù)組。最后將A中所有的時間相加得出一個遍歷所有接點的滿意時間。四、實例分析為了驗證算法的有效性，本文采用文獻【4】的模具生產(chǎn)實例進行檢驗，此實例包含3個具有相同網(wǎng)絡結構的工程，其網(wǎng)絡結構圖如圖1所示。圖1網(wǎng)

11、絡結構圖每個工程含有16個任務，所有的16個任務共享13中資源，在不同的工程中任務的工期是有所不同的。雖然企業(yè)中多工程是并存的，但我們總是可以給這些工程設置一定的優(yōu)先級，即權重。我們假設w1=0.5，w2=0.3，w3=0.2可以計算出工程1的總工期是：P11 +P12 +P16 +P17 +P18 +P112 +P113 +P114 +P115 +P116=4+3+5+4+2+3+3+2+3+4=33天，同理可以知道工程2的工期：P21 +P22 +P26 +P27 +P28 +P212 +P213 +P214 +P215 +P216+7=5+6+6+6+3+4+2+4+3+4+7=43+7

12、=50天，對式中的7說明：由于工程1的任務1和2共享一種資源，所以工程2的開始時間就是P11 +P12=3+4=7天。工程3的工期：P31 +P32 +P36 +P37 +P38 +P312 +P313 +P314 +P315 +P316+18=4+6+6+3+2+3+4+2+4+4+18=38+18=56天，對式中的18說明：由于工程1和2它們各自的任務1和2共享一種資源，所以工程3的開始時間就是P11 +P12 +P21 +P22=3+4+5+6=18天。本文的求解過程完全可以通過計算機編程來實現(xiàn)，能夠提高過程的效率。與其他一些調(diào)度算法相比，工期有明顯的縮短。通過國內(nèi)的一些算法我們可以清楚

13、的比擬出來，這些算法文獻3都給出了結論，如表2。表2： 算法 工程1 工程2 工程3 SASP 33 50 58 MAXTWK 47 43 56 多優(yōu)先規(guī)那么算法 42 54 58 當然了，關于多工程的調(diào)度問題國內(nèi)外許多學者提出了很多不同的實現(xiàn)方法，各個方法都各有優(yōu)缺點，本算法特別適用于工程的網(wǎng)絡結構圖能轉化為圖的這種結構形式，以便通過DFS算法實現(xiàn)。五、結論本文借鑒了許多關于多工程管理在資源受限情況的調(diào)度問題，和其他的算法相比實質(zhì)根本上一致，只不過是采用了一種新的算法，即DFS算法，當然了，本算法也用缺乏之處，就是資源使用的獨占性，一旦工程交叉起來進行，不同的工程，不同的任務的優(yōu)先級都不一致，這種情形下，情況可能會更加復雜，需要更進一步的研究與探討！六參考文獻【1】吳之明，盧有杰.工程管理引論M.北京：清華大學出版社，2001.12.【2】陳慧南.數(shù)據(jù)結構-C語言描述M.陜西:西安弟子科技大學出版社,2003.8.【5】嚴蔚敏,吳偉民.數(shù)據(jù)結構M.北京：清華大學出版社，2007.12.【7】徐孝凱，魏榮.數(shù)據(jù)結構M,北京：機械工業(yè)出版社，1996朱洪等譯，S巴斯.計算機算法：設計和分析引論M.上海：復旦大學出版社，1985Endley L G. Towards