新型蛙跳算法求解總能耗約束FJSP

楊冬婧 雷德明

武漢理工大學自動化學院，武漢，430070

0 引言

柔性作業車間調度問題(flexible job shop scheduling problem,FJSP)是經典作業車間調度問題(job shop scheduling problem,JSP)的延伸，每個工件的每道工序都可以在給定機器集中的任一機器上進行加工，比JSP更接近實際生產，具有靈活性。FJSP是典型的NP-hard問題[1]，在汽車裝配、紡織、化工材料加工以及半導體制造等方面得到了廣泛的應用。自BRUKER等[2]首次研究FJSP以來，出現了大量的相關研究成果。目前，智能算法已廣泛應用于各類FJSP的求解，其中關于多目標FJSP，在KACEM等[3]提出基于遺傳算法(genetic algorithm,GA)和局部方法的混合算法之后，研究者大量應用GA[3-7]、粒子群算法[8-9]、人工蜂群算法[10]、禁忌搜索[11-12]、變鄰域搜索(varible neighborhood search,VNS)[13]、帝國競爭算法[14]和分布估計算法[15]等求解FJSP。近年來，低碳制造和低碳生產調度受到工業界和學術界的廣泛關注。關于低碳FJSP，LIU等[7]運用GA求解雙目標低碳FJSP。TANG等[16]考慮FJSP的能耗并運用遺傳模擬退火算法對問題進行求解。HE等[17]提出了一種節能優化算法，它通過機床選擇來減少機器加工能耗和操作序列調整來減少機器閑置時的能源浪費。PIROOZFARD等[18]提出了一種多目標遺傳算法(multi-objective genetic algorithm,MOGA)，同時最小化碳排放量和總拖期。蔣增強等[19]提出了基于血緣變異的改進非劣排序遺傳算法NSGA-Ⅱ[20]。唐立力[21]提出了一種改進型候鳥優化算法。YIN等[22]運用MOGA來求解具有產能、能源效率和噪聲減少等目標的FJSP。LEI 等[23-24]分別利用一種新型蛙跳算法(shuffled frog leaping algorithm,SFLA)和一種新的教學優化算法求解低碳FJSP。

如上所述，盡管低碳FJSP研究取得了一些進展，但其研究仍不夠深入。例如，對于總能耗約束FJSP，該問題中總能耗不是目標函數，總能耗只需不超過給定的閾值即可。由于總能耗約束經常無法得到滿足，故需要根據問題的特點采用新策略對問題求解。作為一種模擬青蛙活動的智能算法，SFLA已成功應用于車間布局[25]、裝配序列規劃[26]、電網規劃[27]、旅行商問題[28]和生產調度[29]等方面，但它在低碳FJSP方面的應用[29]還不充分。根據SFLA概念簡單、參數少、計算速度快且全局尋優能力強等特點和相關應用[30]，有必要探索SFLA在求解低碳FJSP方面的搜索優勢，為問題的解決提供新的途徑。對于所研究的總能耗約束FJSP，由于該問題的能耗約束經常無法得到滿足，為了有效地解決該問題，本文首先將問題轉化為兩目標FJSP，以簡化對能耗約束的處理；然后在模因組構建新策略、模因組搜索新過程以及模因組最好解的強化搜索基礎上，構建一種新型SFLA以直接優化兩目標FJSP；最后，選擇MOGA[18]和VNS[13]作為比較算法，通過大量仿真實驗，驗證新型SFLA的搜索性能和優勢。

1 問題的描述

總能耗約束FJSP描述如下：存在n個工件的工件集J={J1,J2,…,Jn}和m臺機器的機器集M={M1,M2,…,Mm}，工件Ji具有hi道工序，工序oij為工件Ji的第j道工序，該工序可由相容機器集Sij中的任何一臺機器加工，Sij?M。每臺機器具有d種速度，速度集合V={v1,v2,…,vd}。每個工件在加工過程中，機器加工速度一旦確定就不能改變。機器Mk∈M具有兩種狀態：加工狀態和空閑狀態。當機器Mk不加工工件時，處于空閑狀態，該機器單位時間能耗為Ek；當機器Mk以速度vl加工時，加工模式下單位時間能耗為Ekl。每道工序oij在機器Mk上有一個給定的標準加工時間ηijk，當工序oij在機器Mk∈M上以速度vl加工時，相應的加工時間pijkl=ηijk/vl。關于pijkl與Ekl的關系，DING等[31]提出以下假設：加工速度變快，則加工時間變短，能耗增大。

存在一些與機器和工件相關的約束，包括：不同工件的工序之間沒有先后關系的約束；同一時刻一臺機器最多只加工一道工序；同一時刻一個工件最多只能在一臺機器上加工且加工過程不可中斷；準備時間和清理時間包含在加工時間內，等等。另外，考慮總能耗約束ETC≤QEC，其中，ETC為總能耗，QEC為總能耗閾值，有

(1)

其中，yijkl(t)為二進制量，如果在時刻t機器Mk∈Sij處于加工狀態，則yijkl(t)=1；否則，yijkl(t)=0。如果機器Mk在時刻t處于準備狀態，則zk(t)=1；否則，zk(t)=0。Cmax為最長完成時間。

總能耗約束FJSP包括調度子問題、機器分配子問題和速度選擇子問題，其中，速度選擇子問題是確定工件在所分配機器上的加工速度，其目的是在所有約束滿足的條件下，最小化如下目標函數：

(2)

其中，Ci、Di分別為工件Ji的完成時間和交貨期；目標函數f為總延遲時間。

上述機器和工件的相關約束，在解碼時都能得到滿足，而總能耗約束往往難以滿足，需要單獨處理總能耗約束。目前約束處理的方法很多[32]，其中最常見的方法包括多目標法[33]，該方法將單目標約束優化問題轉化為雙目標問題，其中一個目標為原問題的目標函數，另一個目標為約束違背程度。因此，采用多目標法處理總能耗約束問題，但新增的目標不是約束違背程度，而是直接將總能耗作為新的目標。

2 蛙跳算法描述

SFLA[34]中，青蛙的位置即問題的解x，虛擬青蛙的集合即為可能的解的集合，將這些青蛙均分為若干個小組，這些小組稱為模因組，對每個模因組執行搜索過程，當每個模因組達到指定的迭代次數后，將它們結合成新的種群，這個過程稱為種群重構。模因組搜索和種群重構循環進行直到終止條件得到滿足。

SFLA的步驟如下：①初始化以下參數：模因組個數s，種群規模N。②產生初始種群P。③對種群中的解按適應度值降序排序，將種群劃分為s個模因組。④對每一個模因組執行搜索過程。⑤對進化后的模因組執行種群重構。⑥如果終止條件得到滿足，則輸出最優解；否則轉到步驟③。

將種群劃分為s個模因組的過程如下：將第1只青蛙分入第1個模因組，第2只青蛙分入第2個模因組，第s只青蛙分入第s個模因組，第s+1只青蛙分入第1個模因組，依此類推。

(3)

式中，R為區間[0,1]上服從均勻分布的隨機數。

(4)

3 新型SFLA

對于總能耗約束FJSP，除能耗約束之外的其他約束(如同一時刻一臺機器最多只加工一道工序)在智能算法的解碼過程中都可以得到滿足，只有能耗約束經常無法得到滿足。針對這類約束優化問題，為了處理總能耗約束，將總能耗約束從原問題中剔除，同時增加第2個目標g=ETC，將原問題轉化為具有f、g的雙目標FJSP，然后應用新型SFLA對轉化后的FJSP進行求解，則在算法優化過程中，無需處理能耗約束，簡化了對能耗約束的處理。

3.1 編碼方式與初始化

調度串中,θi∈{1,2,…,n},1≤ri≤hθi,二元組(θi,ri)對應工序oθiri，這樣整個串對應一個有序工序表[oθ1r1,oθ2r2,…,oθiri,…oθhrh]。機器分配串中，基因ρij∈Sij表示用于加工工序oij的相容機器。第3個串中，uij為ρij加工oij時的速度。上述編碼方法能保證除總能耗約束ETC≤QEC之外的其他約束總是成立，但無法保證能耗約束總是成立。

隨機生成初始種群，確定算法參數：種群規模、模因組個數、最大迭代次數，令ρi=1,?i=1,2,…,N。

3.2 模因組的構建

非劣排序根據Pareto支配對種群內的所有解進行比較。Pareto支配是多目標優化的基本概念，假設優化問題的目標總數為G且都是最小化目標，如果解x和y滿足?i∈{1,2,…,G},fi(x)≤fi(y)且?i∈{1,2,…,G},fi(x)

與現有模因組構建方法[29,35]不同，上述過程首先為模因組分配一個最好解和最差解，然后順序分配剩余的解。由于轉化后的問題為雙目標FJSP，上述構建過程可以讓組成各模因組的解具有相近的收斂程度，有助于各模因組在搜索過程中同步改進，從而提高搜索效率。

3.3 模因組搜索

模因組搜索是SFLA產生新解的主要方式，通常以組內的最差解xw為優化對象，也有文獻以組內的最好解xb為搜索對象[35]，現選擇一種新的優化對象。

步驟⑤中的全局搜索過程如下：產生隨機數R，如果R<0.7，則利用兩個解的調度串交叉產生新解；如果0.7≤R<0.85，則執行機器分配串的交叉操作；如果R≥0.85，則通過速度選擇串交叉獲得新解。步驟⑥的全局搜索過程如下：產生隨機數R，如果R<0.8，則對y與x的調度串進行交叉，否則對兩個解的機器分配串執行交叉。上述2個步驟中，0.7、0.8、0.85三個數根據實驗確定，交叉操作作用在兩個解x和xb(y)之間，3種交叉操作的具體描述見文獻[29]，和文獻[29]一樣，每次交叉只產生一個解，在交叉過程中，xb(y)保持不變。

采用4種鄰域結構產生新解。根據調度子問題復雜性更高的特點，給出了兩種鄰域結構。鄰域結構insert用于改變解x的調度串[(θ1,r1),(θ2,r2),…,(θi,ri),…,(θh,rh)]，首先隨機確定一個元素(θj,rj)和一個位置k≠j，并將元素(θj,rj)插入新位置；然后重新確定所有ri以得到新的調度串。鄰域結構swap通過互換一些二元組和為每個θi重新確定新的ri來產生新解。鄰域結構change用于改變部分被選中工序的機器分配。change的詳細步驟如下：首先從機器分配串中隨機選擇ρij，它對應工序oij，確定可以加工該工序的所有機器集合Θ，從集合Θ中隨機選擇一臺與ρij不同的機器替代ρij。鄰域結構speed用于改變部分被選中機器的加工速度，其具體過程如下：首先從速度選擇串中隨機選擇uij，它對應工序oij和加工機器ρij，從ρij的加工速度集合V中隨機選擇一檔與uij不同的速度替代uij。令N1、N2、N3分別表示insert、change和speed,Ni(x)為執行Ni所產生的x的鄰域解集。

外部檔案Ω的更新過程如下：將新解加入集合Ω之后，對于集合內的所有解，根據目標f、g進行Pareto比較，保留非劣解，剔除受支配解。

3.4 局部搜索

若經過較多迭代次數的模因組搜索，組內的最好解始終無法得到改善，則將導致組內其他解與最好解的相似度增大，種群多樣性下降，算法可能陷入局部最優，為此，對每個模因組的最好解執行局部強化搜索。

最好解質量較高，對其進行局部搜索產生更高質量解的可能性較大，這樣可以利用最好解引導算法的搜索，避免算法陷入局部最優。

3.5 算法描述

改進算法的詳細步驟如下：①初始化參數：模因組個數s，種群規模為N。②產生初始種群P。③對種群內的所有解進行非劣排序，確定每個解x受其支配的其他解的數量η。④將種群分為s個模因組。④對每一個模因組執行搜索過程。⑥對模因組內的最好解執行搜索過程。⑦對進化后的模因組執行種群重組。⑧如果滿足終止條件，輸出外部檔案；否則轉到步驟③。⑨剔除Ω中的非可行解，輸出目標f最小的可行解。終止條件為最大目標估計次數max_it。

新型SFLA對由原問題轉化后的兩目標FJSP進行求解，而不是直接優化原問題，這樣簡化甚至避免了對總能耗約束的處理，另外，新算法采用新的策略構建模因組，選擇新的優化對象和新方式進行模因組搜索，并加強對模因組的最好解的強化搜索，以上策略能有效地實現探索和利用之間的良好平衡，有助于算法獲得高質量的解。

4 計算實驗

(5)

其中，δ的值見表1。

表1 δ的設置

選用VNS算法[13]和MOGA[18]作為對比算法，這兩種算法很容易應用于雙目標低碳FJSP的求解。用文獻[13]所設計的VNS算法來解決具有加權目標的FJSP，加入speed、外部檔案更新策略和新舊解替換條件后，VNS算法可用于求解雙目標FJSP。PIROOZFARD等[18]應用MOGA解決雙目標低碳FJSP，將速度選擇串交叉和speed作為變異加入后，該算法能夠直接用來解決雙目標FJSP。

通過大量計算實驗，獲得新型算法參數設置如下：N=40,s=5,max_it=105。MOGA[18]的參數設置如下：種群規模為100，交叉概率為0.7，變異概率為0.4，選擇概率為0.45，終止條件也為max_it。關于VNS算法[13]，nmax=350由文獻[13]給出，max_it與新型SFLA相同。對每個實例，隨機運行10次，每次當目標函數估計次數達到30 000時，根據外部檔案Ω中解的最大g值確定閾值QEC。

每個實例隨機運行3種算法各10次，3種算法的運算結果見表2，3種算法的運算時間對比見表3， 3種算法的收斂曲線對比見圖1。其中，關于總延遲時間，若外部檔案或者MOGA的種群的非劣解都不可行，則選擇違背約束程度最小的解的總延遲時間；否則，在可行的非劣解中選擇總延遲時間最短的解。

表2 三種算法計算結果

表3 三種算法的運算時間

圖1 三種算法關于實例mtxx和setb4xx的收斂曲線Fig.1 Convergence curves of three algorithms on mtxx and setb4xx

如表2所示，SFLA獲得了16個實例的最好解，MOGA僅獲得5個實例的最好解；另外，新型SFLA關于15個實例獲得了優于MOGA的平均解，僅在最差解方面，新型SFLA優勢不明顯，關于實例11產生的最差解優于MOGA。新型SFLA的結果幾乎全部優于VNS。如表3所示，新型SFLA與另兩種算法的運算時間相近。SFLA的性能優于另外兩種算法的主要原因在于該算法兼顧了全局搜索和局部搜索的協調和平衡，增強了算法性能，因此，新型SFLA是解決總能耗約束FJSP具有較強競爭力的算法。

5 結論

盡管FJSP已得到較充分的研究,但總能耗約束FJSP的研究相對較少,隨著綠色制造和低碳制造的應用不斷深入,需要進一步研究低碳FJSP。本文提出了一種新型SFLA，在總能耗不超過給定的閾值條件下最小化總延遲時間。將原問題轉化為包括總能耗的兩目標FJSP后，利用新型SFLA優化轉化后的雙目標FJSP。計算結果表明，新型SFLA具有較強的搜索性能和優勢。未來將繼續深入研究具有總能耗或峰值能耗約束的調度問題，并進一步研究帝國競爭算法在低碳生產調度方面的應用；另外，分布式調度也是未來研究的主題之一。