曹圣武，陳再良

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

0 引言

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

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

1 問題描述

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

minSn+2

(1)

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

(2)

(3)

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

(4)

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

2 算法描述

2.1 布谷鳥算法基本原理

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

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

2) 具有優(yōu)質(zhì)蛋的最佳巢會被帶到下一代；

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

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

(5)

(6)

(7)

2.2 算法改進

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

(8)

自適應(yīng)的更新位置公式就變成：

(9)

3 自適應(yīng)布谷鳥算法生產(chǎn)項目調(diào)度

3.1 編碼方案

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

表1 隨機優(yōu)先權(quán)列表

3.2 調(diào)度流程

Step1：初始化參數(shù)，隨機產(chǎn)生n個鳥巢；

Step2：計算初始種群適應(yīng)度；

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

Step4：新解與上代解進行比較，用較優(yōu)新解替換舊解；

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

Step6：部分較優(yōu)解保留到下一代；

Step7：是否滿足終止條件，若滿足則停止迭代輸出最優(yōu)解，若不滿足轉(zhuǎn)Step3。

4 實驗與分析

4.1 項目描述

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

表2 壓縮機裝配項目信息

續(xù)表2

4.2 調(diào)度方案

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

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

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

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

圖3 人力資源利用率

表3 優(yōu)化調(diào)度方案

圖4 人員配置甘特圖

表4 布谷鳥算法與自適應(yīng)布谷鳥算法比較

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

5 結(jié)語

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