基于布谷鳥算法的壓縮機裝配調度項目優化方法

曹圣武，陳再良

(蘇州大學 機電工程學院，江蘇 蘇州 215000)

0 引言

隨著工業全球化的推行和日益加劇的市場競爭，多品種、小批量、定制化加工已經成為制造業發展的新趨勢，訂單式生產成為制造型企業的主要運作模式，訂單式項目管理應運而生。

生產項目調度本質上屬于資源受限項目調度問題(resource-constrained project scheduling problem，RCPSP)，即項目的各活動間需要滿足兩種約束關系，一是前后活動的邏輯約束，二是資源約束。RCPSP是近年來項目調度的熱點問題，眾多智能算法被引入到求解該問題中來，LI H等[1]改進了遺傳算法并重新設計編碼方案，提高了該算法求解RCPSP的性能； ZHENG X, WANG L[2]提出了一種MAOA智能算法，通過自主學習來強化搜索能力；DENG L等[3]引入混合蟻群算法，應用活動拆分來預測時間表，有效提高了調度質量；王凌和鄭環宇[4]將教學算法用于多目標資源受限項目，仿真結果驗證了算法的有效性。

1 問題描述

實際生產項目由n個活動構成V={1,…,n,n+1,n+2}，活動1和n+2是虛任務。項目各活動共用R種有限的可更新資源，并受到兩類約束，一是緊前約束，即活動i∈V必須在其所有緊前活動全部完工之后才能開始；二是資源約束，即任意時刻活動對第k種資源的需求量不得超過其上限Rk。已知活動i的執行時間為di(i=1,2,…,n+2)，對第k種資源的需求為rik，在滿足兩類約束的前提下調度各活動的開始時間S={S1,S2,…,Sn+2}，目標函數是項目工期Sn+2最短。數學模型如下：

minSn+2

(1)

s.t.Sj+dj≤Si，j∈P(i)

(2)

(3)

Si≥0，i=1,2,…,n+2

(4)

其中：P(i)是活動i的所有緊前任務；At是t時刻正在進行的所有活動；rik是t時刻活動i所需資源k的數量。

2 算法描述

2.1 布谷鳥算法基本原理

布谷鳥通過寄生育雛的方式將自己的蛋偷偷下在其他鳥類的巢穴中，甚至可以模仿宿主的蛋而不被發現。劍橋大學的YANG X S和DEB S[5]從布谷鳥這種繁殖行為中得到啟示，提出布谷鳥算法(cuckoo search，CS)。該算法具有涉及參數少、全局尋優能力強、隨機搜索路徑優等特點，首先設定如下3種理想狀態：

1) 每只布谷鳥每次下1個蛋，并將其放入隨機選擇的巢中；

2) 具有優質蛋的最佳巢會被帶到下一代；

3) 可用的寄主巢數量是固定的，且寄主以Pa∈(0,1)的概率發現布谷鳥放的蛋。

該算法還可以通過萊維飛行(Lévy flight)來增強全局搜索能力，搜索路徑和更新位置公式如下：

(5)

(6)

(7)

2.2 算法改進

布谷鳥算法在運算后期會產生搜索性能下降、搜索速度變慢的現象[6]。因此針對算法重要影響參數——步長控制因子加入自適應策略，提出一種自適應的布谷鳥算法(ICS)。根據提出的自適應策略，在運算的前期，步長控制因子取較大值以增強萊維飛行的跳躍能力，提升全局搜索性能[7]；當種群的最佳個體靠近當代最優解時，自適應策略使控制因子取較小值以收縮步長變動幅度，使其能夠更快收斂到全局最優解或次優解。自適應步長公式如下：

(8)

自適應的更新位置公式就變成：

(9)

3 自適應布谷鳥算法生產項目調度

3.1 編碼方案

采用基于優先權的實數編碼，生成串型調度方案。一條鏈代表生成的調度方案，基因為整數，如X=[0,1,2,…,n+1]，其中0和n+1是虛任務；另一條鏈代表任務的優先權，基因是隨機分配的實數。表1為優先權分配示意圖。

表1 隨機優先權列表

3.2 調度流程

Step1：初始化參數，隨機產生n個鳥巢；

Step2：計算初始種群適應度；

Step3：保留上代最優值，利用式(5)和式(6)更新出一組新解并計算適應度；

Step4：新解與上代解進行比較，用較優新解替換舊解；

Step5：利用式(7)丟棄部分解并產生新解；

Step6：部分較優解保留到下一代；

Step7：是否滿足終止條件，若滿足則停止迭代輸出最優解，若不滿足轉Step3。

4 實驗與分析

4.1 項目描述

S企業是一家專業從事中大型壓縮機制造的跨國企業，以該企業一典型壓縮機裝配項目為例。該項目原計劃工期160天，涉及項目工程師3人、采購工程師2人、機械工程師4人、裝配工程師4人。簡化的項目BOM和活動資源需求如表2，要求在滿足活動約束和人員限制的情況下找到工期最短的調度方案。

表2 壓縮機裝配項目信息

續表2

4.2 調度方案

使用Matlab_R2018B版本編寫算法程序，參考文獻[8]的參數尋優方法，經多次運算的結果表明，自適應式步長影響因子上、下界取0.01和0.9時算法性能較好。初始種群數設定25，最大迭代數設定為50，發現概率設定為0.25。

該算法計算出的最短工期為141天，比原計劃的完工時間提前了19天，工期縮短率為11.87%，驗證了算法在處理生產項目調度問題的有效性。圖1為運算過程中最短工期與平均工期收斂圖，可以看到工期隨迭代數穩步降低，在第16代時收斂到最優值；圖2為最短工期與平均工期偏差，在第4代到37代間種群較為活躍，38代后趨于穩定；圖3為人力資源利用率圖，以資源利用率超過80%為風險點，該調度方案下資源利用率平衡且未超風險點；圖4是人員配置甘特圖，直觀、清晰地呈現了各工程師在項目全期的工作安排；表3給出了具體的項目調度順序和各活動的開始-完成時間；表4將自適應布谷鳥算法與布谷鳥算法相比較，結果驗證了自適應布谷鳥算法具有更高的運算精度和收斂速度。

圖1 最短工期與平均工期收斂圖

圖2 最短工期與平均工期偏差

圖3 人力資源利用率

表3 優化調度方案

圖4 人員配置甘特圖

表4 布谷鳥算法與自適應布谷鳥算法比較

可以看到在當前的人力配置下，該方案已經達到了最優化，但是在項目的某些時段還存在著大量的人力浪費。項目經理可以通過觀察人員配置甘特圖來提前對具體的工程師做資源補償安排，比如在項目第72天～129天的這個時間段把采購工程師調配到其他項目中；在項目前20天和第38～89天這兩個時間段也可把裝配工程師調到其他項目中。

5 結語

本文提出了一種新的基于自適應步長因子的布谷鳥算法(ICS)。以S公司生產調度項目實例為基礎，驗證了該算法在處理此類問題的有效性。還將改進算法與原算法對比，驗證了改進算法擁有更好的精度和收斂速度。此外，通過觀測軟件自動生成的資源利用率圖和資源配置甘特圖，項目經理能夠準確地監控資源配置情況，動態調整人員安排。ICS算法需求參數少，適用性強，經過簡單的參數調整，就可以運用到其他制造型企業的實際生產調度中，為項目經理制訂項目計劃提供參考。