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

楊冬婧 雷德明

武漢理工大學(xué)自動(dòng)化學(xué)院，武漢，430070

0 引言

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

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

1 問題的描述

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

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

(1)

其中，yijkl(t)為二進(jìn)制量，如果在時(shí)刻t機(jī)器Mk∈Sij處于加工狀態(tài)，則yijkl(t)=1；否則，yijkl(t)=0。如果機(jī)器Mk在時(shí)刻t處于準(zhǔn)備狀態(tài)，則zk(t)=1；否則，zk(t)=0。Cmax為最長(zhǎng)完成時(shí)間。

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

(2)

其中，Ci、Di分別為工件Ji的完成時(shí)間和交貨期；目標(biāo)函數(shù)f為總延遲時(shí)間。

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

2 蛙跳算法描述

SFLA[34]中，青蛙的位置即問題的解x，虛擬青蛙的集合即為可能的解的集合，將這些青蛙均分為若干個(gè)小組，這些小組稱為模因組，對(duì)每個(gè)模因組執(zhí)行搜索過程，當(dāng)每個(gè)模因組達(dá)到指定的迭代次數(shù)后，將它們結(jié)合成新的種群，這個(gè)過程稱為種群重構(gòu)。模因組搜索和種群重構(gòu)循環(huán)進(jìn)行直到終止條件得到滿足。

SFLA的步驟如下：①初始化以下參數(shù)：模因組個(gè)數(shù)s，種群規(guī)模N。②產(chǎn)生初始種群P。③對(duì)種群中的解按適應(yīng)度值降序排序，將種群劃分為s個(gè)模因組。④對(duì)每一個(gè)模因組執(zhí)行搜索過程。⑤對(duì)進(jìn)化后的模因組執(zhí)行種群重構(gòu)。⑥如果終止條件得到滿足，則輸出最優(yōu)解；否則轉(zhuǎn)到步驟③。

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

(3)

式中，R為區(qū)間[0,1]上服從均勻分布的隨機(jī)數(shù)。

(4)

3 新型SFLA

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

3.1 編碼方式與初始化

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

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

3.2 模因組的構(gòu)建

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

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

3.3 模因組搜索

模因組搜索是SFLA產(chǎn)生新解的主要方式，通常以組內(nèi)的最差解xw為優(yōu)化對(duì)象，也有文獻(xiàn)以組內(nèi)的最好解xb為搜索對(duì)象[35]，現(xiàn)選擇一種新的優(yōu)化對(duì)象。

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

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

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

3.4 局部搜索

若經(jīng)過較多迭代次數(shù)的模因組搜索，組內(nèi)的最好解始終無法得到改善，則將導(dǎo)致組內(nèi)其他解與最好解的相似度增大，種群多樣性下降，算法可能陷入局部最優(yōu)，為此，對(duì)每個(gè)模因組的最好解執(zhí)行局部強(qiáng)化搜索。

最好解質(zhì)量較高，對(duì)其進(jìn)行局部搜索產(chǎn)生更高質(zhì)量解的可能性較大，這樣可以利用最好解引導(dǎo)算法的搜索，避免算法陷入局部最優(yōu)。

3.5 算法描述

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

新型SFLA對(duì)由原問題轉(zhuǎn)化后的兩目標(biāo)FJSP進(jìn)行求解，而不是直接優(yōu)化原問題，這樣簡(jiǎn)化甚至避免了對(duì)總能耗約束的處理，另外，新算法采用新的策略構(gòu)建模因組，選擇新的優(yōu)化對(duì)象和新方式進(jìn)行模因組搜索，并加強(qiáng)對(duì)模因組的最好解的強(qiáng)化搜索，以上策略能有效地實(shí)現(xiàn)探索和利用之間的良好平衡，有助于算法獲得高質(zhì)量的解。

4 計(jì)算實(shí)驗(yàn)

(5)

其中，δ的值見表1。

表1 δ的設(shè)置

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

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

每個(gè)實(shí)例隨機(jī)運(yùn)行3種算法各10次，3種算法的運(yùn)算結(jié)果見表2，3種算法的運(yùn)算時(shí)間對(duì)比見表3， 3種算法的收斂曲線對(duì)比見圖1。其中，關(guān)于總延遲時(shí)間，若外部檔案或者M(jìn)OGA的種群的非劣解都不可行，則選擇違背約束程度最小的解的總延遲時(shí)間；否則，在可行的非劣解中選擇總延遲時(shí)間最短的解。

表2 三種算法計(jì)算結(jié)果

表3 三種算法的運(yùn)算時(shí)間

圖1 三種算法關(guān)于實(shí)例mtxx和setb4xx的收斂曲線Fig.1 Convergence curves of three algorithms on mtxx and setb4xx

如表2所示，SFLA獲得了16個(gè)實(shí)例的最好解，MOGA僅獲得5個(gè)實(shí)例的最好解；另外，新型SFLA關(guān)于15個(gè)實(shí)例獲得了優(yōu)于MOGA的平均解，僅在最差解方面，新型SFLA優(yōu)勢(shì)不明顯，關(guān)于實(shí)例11產(chǎn)生的最差解優(yōu)于MOGA。新型SFLA的結(jié)果幾乎全部?jī)?yōu)于VNS。如表3所示，新型SFLA與另兩種算法的運(yùn)算時(shí)間相近。SFLA的性能優(yōu)于另外兩種算法的主要原因在于該算法兼顧了全局搜索和局部搜索的協(xié)調(diào)和平衡，增強(qiáng)了算法性能，因此，新型SFLA是解決總能耗約束FJSP具有較強(qiáng)競(jìng)爭(zhēng)力的算法。

5 結(jié)論

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