基于進化計算的項目工期與資源優化研究

段靈婧

貴州商學院 貴州貴陽 550014

據調查，大部分項目管理者在管理過程中，往往通過傳統的“經驗”預測完成一項項目所需的工期以及資源，由于每個項目具有其唯一性，這就導致在項目實施過程中會出現大量的變化，使得在管理過程中產生更多的不確定性，造成資源浪費或延長工期。項目資源管理是在保證滿足工程質量、工期等合同要求的前提下，通過計劃、組織、控制和協調等活動對項目實施過程中所使用的資源進行統籌安排，以實現預定的工期和成本目標，并盡可能降低成本的一種科學的管理活動[1]。所以，首先應該仔細研究工程項目的工期，科學合理地制訂出建設工期和進度計劃；其次要對項目中所需的各種資源進行統籌的安排，以做好資源的優化配置工作。本文利用進化算法對在資源有限的條件下，尋求最短工期和工期固定的情況下，如何使資源達到均衡消耗的目的予以研究。

一、NSGA-II

NSGA-II是對NSGA算法的改進，其引入了擁擠度和精英選擇策略，使得優化過程更加具有泛化性，以及具有更優的遺傳性，在解決多目標優化問題時被廣泛應用，其能夠實現項目工程在資源(人力、工期等)受限的條件下，進行全局搜索，實現資源均衡，最后得到最優方案。該算法一共包括了下面這些重要算子：快速非支配排序(FNDS)、擁擠度(CCM)、適應度(Fitness)、錦標賽選擇(TSM)、模擬二進制交叉(SBX)、多項式變異(PM)、精英選擇策略(ESS)等。由于在多目標優化時經常相互沖突，在進化過程中很難選擇更好的解決方案進入下一代，NSGA-II使用快速非支配排序方法(FNDS)和擁擠比較方法(CCM)為下一代選擇合適的個體。在產生新種群的交叉、變異和適應度進化操作之后，NSGA-II將原始種群和新產生的種群結合在一起。然后根據FNDS將組合的個體(解)劃分為一組非支配等級。假設種群規模按等級劃分，排名較低(較好)的個體將首先被選中進入下一代種群。即第一等級的個體直接進入下一代種群，然后第二等級的個體進入下一代種群，然后第三等級，依此類推，直到選擇N個個體。本文中，Fitness設置函數如下：

f1(Xi)=T

(1)

(2)

其中，f2(Xi)代表資源閑置量，總工期用T表示，rt表示第t天需要的資源。

二、R&C-NSGA-II

(一)R&C

CCM的過程可能會消耗大量的計算負擔，當M遠小于當前秩的個體數時，隨機選擇M個個體即可，這不僅可以避免CCM的計算負擔，而且還能實現種群多樣性。因此，本文采用了一種結合RSM和CCM的自適應選擇方法R&C，根據M與當前秩的個體數(|Fi|)的關系。如果M遠小于|Fi|，即M<λ·|Fi|，其中λ是控制選擇策略的參數，則R&C采用隨機方式從當前的前沿Fi中隨機選擇M個個體。否則，由CCM選擇M個個體。詳細過程如下算法3所示。

Algorithm 3 R&CInput:Fi,M,Pt+1Begin1.If M<λ·|Fi|2.從Fi中隨機選擇M個,置入Pt+1;3.Else4.從Fi中采用CCM的方法,選擇M個,置入Pt+1;5.End IfEnd

(二)R&C-NSGA-II

R&C-NSGA-II如下算法4所示。R&C有助于提高NSGA-II在解決MOPs方面的性能。

算法4中，t表示當前進化代，tmax表示最大進化代。Pt是第t代的父代種群，Qt是第t代的后代種群。F存儲由FNDS形成的所有不同等級，其中Fi表示第i個等級。在初始化中，隨機生成大小為N的父種群Pt，t初始設置為0。R&C-NSGA-II停止，直到達到tmax。其現代碼如下所示：

三、工期與資源的優化方式

(一)資源有限、工期最短

根據工期目標對工程項目進行任務分解，確定各工作之間的邏輯關系，編制網絡計劃及相應的資源計劃[2]。由于在實際情況下資源的供應受到條件的限制，導致某些工作不能在同一時段內同時進行，所以需要盡可能地調整進度計劃的計算工期，一般通過調整關鍵路徑上關鍵工作的持續時間，使其在滿足要求工期的前提下，達到工期最合理的目的[3]。

(二)工期固定、資源均衡

工期固定、資源均衡的優化過程就是調整計劃安排，在工期保持不變的條件下，使資源需用量盡可能均衡的過程。即盡可能在整個計劃實施中不出現短時期的高峰和低谷，通過調整這兩個時間段的資源用量，使每天的資源需用量接近于平均值，從而使得資源更加均衡的配置[4]。

四、實例驗證

已知某工程項目由7項工作構成，其各項數據如表1所示，該項目的雙代號網絡圖如圖1所示。

圖1 某工程項目的雙代號網絡圖

根據該工程項目的雙代號網絡圖，計算出總工期T為11周，其關鍵線路為①—②—④—⑤—⑥，關鍵工作為A—D—E—G。

表1 某工程項目的工期與資源用量

根據各項工作所需的資源繪制出初始資源用量圖，如圖2。

圖2 初始資源用量圖

設rt—在第t周的資源需用量；

rm—資源每周平均需用量。

rm=∑rt/T=(r1+r2+r3+…+rt)/T

由上可知，資源每周平均需用量rm=∑rt/T=(r1+r2+r3+…+r11)/T=1320/11=120，所以，假設經過優化后每周的資源用量控制在120以內，可以避免資源的浪費或因資源不足而造成工期的延長。

根據R&C-NSGA-Ⅱ優化方案，本文設置參數如下表2所示：

表2 R&C-NSGA-Ⅱ參數設置一覽表

通過R&C-NSGA-Ⅱ，可獲得pareto解8組，根據其解，取其中2組結果進行項目優化方案與初始方案比較，如圖3所示。

由圖3可知，第一種優化方案使資源高峰值150降低到了120，達到了工期和資源的均衡，使資源用量維持在120以內。

結論

在現代的項目管理中都會涉及項目管理活動和資源配置問題，任何的項目管理活動中都有兩個重要的績效管理目標，即項目的最短化和資源配置均衡化[5]。通常情況下，如果可以在資源短缺限制條件下得到合理的分配，所產生的經濟效益就會顯著增加，而資源的優化配置就是為了讓資源獲得更好利用，最終實現企業效益最大化[6]。