改進的DFS算法實現(xiàn)資源約束條件下多項目的調(diào)度

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

2、程與其他重復(fù)性運行或操作工作最大的一個區(qū)別。工程有明確的起點和終點，沒有可以完全照搬的先例，也不會有完全相同的復(fù)制。工程的其他屬性都是從這一特點衍生出來的。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)系的，構(gòu)成一個統(tǒng)一的整體。多余的活動是不必要的，缺少某些活動必將損害工程目標的實現(xiàn)。5組織的臨時性和開放性工程團隊在工程的全過程中，其人數(shù)，成員，職責(zé)總是在不斷變化的。某些成員是借調(diào)來的，工程終結(jié)時團隊要解散，人員要轉(zhuǎn)移。參與工程的組織往往有多個，甚至幾十個或更多，這些組織按矩陣型結(jié)構(gòu)排列。他們通過協(xié)議或合同以及其他的社會關(guān)系組織到一起，在工程的不同時段不同程度的介入工程活動?？梢哉f，工程

4、組織沒有嚴格的邊界，是臨時性的開放性的。這一點與一般企、事業(yè)單位和政府機構(gòu)組織不一樣。6成果的不可挽回性工程的一次性屬性決定了工程不同于其他事情可以先試著做，如果作壞了還可以重來；也不同于產(chǎn)品的生產(chǎn)批量，合格率達99.99%就認為是很好的了。工程在一定條件下啟動，一旦失敗就永遠失去了重新進行原工程的時機。所以工程有很大的不確定性和風(fēng)險性。二、多工程管理以上是我們理論意義上的工程，但在實際當中，企業(yè)面對的更多是單工程與多工程的問題。單工程的調(diào)度管理相比而言，比擬容易處理，運用傳統(tǒng)的一些技術(shù)，比方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)略目標為指導(dǎo)的！b)提高資源的利用率。資源在各個工程之間進行有效的分配，不會出現(xiàn)所謂的資源閑置的情況，極大地提高資源的利用率和優(yōu)化度！c)降低工程實施的風(fēng)險。采用單工程的管理思維去管理多工程，很容易在工程的進度、資源的合理安排上產(chǎn)生風(fēng)險，而多工程的管理思維卻可以很好的解決這個問題。d)加強組織內(nèi)部的溝通與交流。多工程的管理，更進一步的把職能部門和工程組聯(lián)系在一起，不僅各個工程之間的聯(lián)系加強，工程和其他非工程部門的聯(lián)系也進一步加強，這都是以企業(yè)總體目標的為導(dǎo)向的。三、DFS算法描述1.圖的定義圖graph是數(shù)據(jù)結(jié)構(gòu)G=V，E，其中VG是

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

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

9、+2+3+4=33天，同理可以知道工程2的工期：P+P+P+P+P+P+P+P+P+P+7=5+6+6+6+3+4+2+4+3+4+7=43+7=50天，對式中的7說明：由于工程1的任務(wù)1和2共享一種資源，所以工程2的開始時間就是P+P=3+4=7天。工程3的工期：P+P+P+P+P+P+P+P+P+P+18=4+6+6+3+2+3+4+2+4+4+18=38+18=56天，對式中的18說明：由于工程1和2它們各自的任務(wù)1和2共享一種資源，所以工程3的開始時間就是P+P+P+P=3+4+5+6=18天。本文的求解過程完全可以通過計算機編程來實現(xiàn)，能夠提高過程的效率。與其他一些調(diào)度算法相比，工期

10、有明顯的縮短。通過國內(nèi)的一些算法我們可以清楚的比擬出來，這些算法文獻3都給出了結(jié)論，如表2。表2： 算法 工程1 工程2 工程3 SASP 33 50 58 MAXTWK 47 43 56 多優(yōu)先規(guī)那么算法 42 54 58 當然了，關(guān)于多工程的調(diào)度問題國內(nèi)外許多學(xué)者提出了很多不同的實現(xiàn)方法，各個方法都各有優(yōu)缺點，本算法特別適用于工程的網(wǎng)絡(luò)結(jié)構(gòu)圖能轉(zhuǎn)化為圖的這種結(jié)構(gòu)形式，以便通過DFS算法實現(xiàn)。五、結(jié)論本文借鑒了許多關(guān)于多工程管理在資源受限情況的調(diào)度問題，和其他的算法相比實質(zhì)根本上一致，只不過是采用了一種新的算法，即DFS算法，當然了，本算法也用缺乏之處，就是資源使用的獨占性，一旦工程交叉起來

11、進行，不同的工程，不同的任務(wù)的優(yōu)先級都不一致，這種情形下，情況可能會更加復(fù)雜，需要更進一步的研究與探討！參考文獻1 吳之明,盧有杰. 工程管理引論. 北京: 清華大學(xué)出版社,2001.12.2 陳慧南.數(shù)據(jù)結(jié)構(gòu)-C語言描述.陜西:西安弟子科技大學(xué)出版社,2003.8.3 壽涌毅. 資源約束下多工程調(diào)度的迭代算法 . 浙江大學(xué)學(xué)報(工學(xué)版), 2004, 38(8): 1095-1099.4 廖仁,陳慶新,毛寧.資源約束下多工程調(diào)度的啟發(fā)式算法 .管理工程學(xué)報, 2002, 16(S): 100-103.6 方煒, 歐立雄. 多工程環(huán)境下新產(chǎn)品研發(fā)工程資源分配問題研究. 管理工程學(xué)報, 2005, 19(S): 6-10.7 徐孝凱,魏榮.數(shù)據(jù)結(jié)構(gòu), 北京:機械工業(yè)出版社,19968 朱洪等譯,S巴斯.計算機算法:設(shè)計和分析引論.上海:復(fù)旦大學(xué)出版社,19859 Endley L G. Towards the Development of a Complete Multi-pr