基于優先原則的啟發式算法在ZM項目中的應用

孟瑤琳，張建國

（1.西安長慶科技工程有限責任公司，陜西西安 710018；2.上海城投原水有限公司教育培訓中心，上海 200120）

基于優先原則的啟發式算法在ZM項目中的應用

孟瑤琳1，張建國2

（1.西安長慶科技工程有限責任公司，陜西西安 710018；2.上海城投原水有限公司教育培訓中心，上海 200120）

施工進度計劃的科學編制及合理安排是項目進度管理的重要內容，是影響項目工期目標實現的關鍵環節。通過關鍵路徑法得到ZM項目建設最短工期進度計劃，再從資源約束的角度，采用啟發式算法對項目進度計劃重新進行調整和編制，得出資源配置最優的工期。

項目進度；優先原則；啟發式算法；優化模型

1 項目數據提煉

ZM項目是某油氣管道工程的一座油氣合建一級站場。具備計量、分輸、清管及增壓等功能。項目合同工期18個月（560d）。按照項目的施工順序步驟，對項目進行工作結構分解。并對該項目涉及的各活動步驟，進行邏輯關系列表。具體如表1所示：

表1 ZM項目活動邏輯關系表

按上表所列邏輯關系順序，可以繪制ZM項目的單代號項目網絡圖。

對各活動的最短工期和最長工期進行估算，在估算活動的持續時間時，主要使用定額計算和專家調查等兩種方法，其中定額計算主要針對項目中總圖工程、單體建筑工程和綠化工程等三部分，而對于工藝管道工程、儲罐工程和安裝工程因可能涉及到新工藝、新方法或新材料，所以借助具有豐富施工經驗的專家給出活動持續的估算時間。具體如表2所示：

2 項目進度優化模型構建及求解

2.1 預估優化工期

Matlab是矩陣實驗室（Matrix Laboratory）的簡稱，本文采用了Matlab的遺傳算法工具箱。為了保證分項任務工期確定的準確性，在任務結構重新分解時將各項任務的工期調整為區間的形式，在真正優化開始之前，可以先采用標準遺傳算法對工期區間內的潛在最優工期求解，再通過基于優先原則的啟發式算法進行調整。

表2 ZM項目工期及資源需求表

本次研究中所用的標準遺傳算法采用雙精度浮點數編碼的方式，交叉概率為0.6，函數自變量數值為32，初始種群生成方式為隨機，變異方式為均勻變異，概率為0.03，具體的運算流程可以參考任少鋒[6]的實現方法采用Matlab軟件全局優化工具箱中的遺傳算法圖形操作界面進行參數設置，并執行算法。具體的潛在最短工期優化運算結果如下表3所示：

表3 項目潛在最短工期優化結果表

2.2 優先原則的確定

啟發式算法是指在一個隨機的群體尋優過程中，個體能夠利用自身或者全局的經驗來制定各自的搜索策略，是一種有目的或者有策略的方法。基于優先原則的啟發式算法主要由調度生成機制和優先規則兩部分構成，本文選用串行調度機制來生成調度計劃。本文分別選取最小總時差、最短任務工期和最大資源日均需求量等三個優先原則，并比較應用三種優先規則產生的結果，選取輸出結果中總工期最小的作為資源配置最優的項目進度計劃優化方案。具體的假設包括：

（1）項目各任務的工期在一個區間范圍內可變，且只能取整數；

（2）項目執行過程中只存在人工和機械資源約束；（3）資源的日均可用量是一個已知常量。

2.3 優化模型

因為建立此模型的目的是使項目在實施的過程中工期最小化，所以此模型以整個項目的總工期（T）最短為目標。

目標函數：

約束條件：

（1）任務工期約束，即各任務的工期必須在確定的范圍內變化：

式中：

N 為ZMYQ合建站項目所包含的活動數，N=32；

t（q）為任務 q 的計劃工期；

LB（q）為任務 q 的可能最短工期；

UB（q）為任務 q 的可能最長工期。

（2）各任務的邏輯關系不能違背，即各任務必須在其所有的緊前任務完成之后才能開始：

式中：

AS（q）為任務 q 的計劃開始時間；

AF（q）為任務 q 的計劃結束時間。

（3）每個工作日內，所有任務對資源的總需求量不能大于資源的可用量：

式中：

Ts 為可能工期的最大值，Ts=1 842；

i 為時間參數，其中 i=1，2，3，…，Ts；

ResA（i）為第 i 個工作日資源的總可用量，初始值為1050（工時）；

ResR（i）為第 i 個工作日資源的總需求量；

Set（i）為第 i 個工作日，所有進行中的任務的集合；Res（q）為完成任務 q 所需要的資源總量；res（q）為任務 q 工期內的資源日均需求量。

2.4 具體運算流程

第1步：定義函數和初始化運算流程，其中基礎函數包括各任務的工期t（q），任務所需投入的資源總量Res（q），任務的日均資源需求量ResR（i），P{N}為各任務的直接緊前任務集，B{N}為各任務的直接緊后任務集，ResA（i）代表項目工期內的日均資源可用量等，任務在可安排任務集中的狀態（0為不可安排，1為可安排）。

第2步：考察D（N）中為1的元素，將其列標放入數組Lb中，根據優先規則確定本次予以調度的項目任務，當優先原則為最小總時差時，考察TF中以數組Lb中數值為列標的元素，確定其最小值，將其列標賦給變量N；當優先原則為最小任務工期時，考察t中以數組Lb中數值為列標的元素，確定其最大值，將其列標賦給變量N；當優先原則為最大資源日需求量時，考察res中以數組Lb中數值為列標的元素，確定其最大值，將其列標賦給變量N。如確定數組Lb中最大/小值有多個元素相等，則取其中列標值小的賦給變量N，即本次要進行安排的是任務N。

第3步：將滿足邏輯關系約束和資源約束的任務最早開始時間確定為計劃開始時間AS（N），再根據項目各任務工期計算得到各任務的計劃結束時間AF（N）=AS（N）+t（N）。

第4步：已安排的任務N移出可安排任務集，并依據任務邏輯關系分析其緊前或緊后任務是否均已經安排完畢，如確定則將其安排至可安排任務集中，供下一步備選。

第5步：重復進行步驟第2、3、4的操作，直到所有的任務均完成調度，算法結束。

第6步：根據已得到的各任務計劃結束時間，確定項目總工期 T1=MaxAF（q）。

第7步：按照以上步驟，分別用三種優先規則確定項目總工期T1，T2，T3，得到最優結果即 T→Min（T1，T2，T3）。

具體的編程通過運用 Matlab 軟件計算機編程語言加以實現，得到針對項目各任務工期范圍內的一組確定的任務工期值，來進行項目調度，生成項目進度計劃方案，進而得到資源配置優化條件下的項目最小總工期，具體優化程序見論文后面的附錄中。

3 模型運算結果

將上文中得到的預估最優任務工期結果作為已知的數據，輸入編制的啟發式算法程序中，具體的計算結果如下表4所示：

表4 模型運算結果

通過上表的計算結果可以明確，T=Min（AF2）=613d，即在資源限制條件下，以最短任務工期為優先條件的總項目工期為最短總工期613d。

4 總結

可以看出，在無資源約束的條件下，即假定該項目所有資源均滿足使用要求的前提下，該項目的合同簽訂工期為18個月（560d）。而根據項目運行的實際情況，在考慮了資源的限制條件后，利用啟發式算法，可以得出該項目的最優解工期為T2=613d，雖然相比合同工期延期53d，但是避免了人工和機械設備的占用沖突，提前緩解了項目實施中可能遭遇的資源問題，降低了項目運行風險，使有效資源利用率得到最大保障。

[1] 李建平.現代項目進度管理[M].北京：機械工業出版社，2008.

[2] Kerzner H.Project Management：A Systems Approach to Planning，Scheduling and Controlling[M].John Wiley & Sons Inc.，2009.

[3] 劉伊生.工程項目進度計劃與控制[M].北京：中國建筑工業出版社，2008.

[4] 盧向南.項目計劃與控制[M].北京：機械工業出版社，2009.

[5] 何正文，劉人境，徐渝.基于隨機活動工期的資源約束項目魯棒性調度優化[J].系統工程理論與實踐，2013，（3）：650-659.

[6] 任少峰.基于模糊關鍵鏈的港鐵列車項目進度計劃優化設計[D].長春：吉林大學，2014.

Application of Heuristic Algorithm Based on Priority Principle in ZM Project

Meng Yao-lin，Zhang Jian-guo

The scientific preparation and reasonable arrangement of construction schedule is an important content of project schedule management，and is the key link affecting the realization of the project schedule target.The critical path method to get the shortest time ZM project construction schedule，from the resource constraint perspective，using heuristic algorithm to re adjust and prepare the project schedule，the optimal allocation of resources in the construction period.

project schedule；priority principle；heuristic algorithm；optimization model

O342

B

1003-6490（2017）12-0242-02

2017-10-09

孟瑤琳（1985—），女，陜西西安人，工程師，主要從事場地總圖設計研究工作。