陶婷婷，宋豫川，王建成，郭偉飛

（重慶大學機械傳動國家重點實驗室，重慶400044）

0 引 言

生產(chǎn)調(diào)度是提高制造企業(yè)運作效率和服務(wù)質(zhì)量的關(guān)鍵環(huán)節(jié)，其中作業(yè)車間調(diào)度問題最為典型，而柔性作業(yè)車間調(diào)度問題[1]（flexible job shop scheduling，F(xiàn)JSP）是作業(yè)車間調(diào)度問題的拓展，在工序排序的問題中引入機器選擇問題，增加了問題的復雜程度，給其求解帶來更大的困難和挑戰(zhàn)。

FJSP 問題的求解方法可以分為兩大類，精確算法和近似算法。精確算法包括分支定界法、整數(shù)規(guī)劃法和拉格朗日松弛法等。Tamaki[2]建立了FJSP 的混合整數(shù)規(guī)劃模型，并采用枚舉法進行FJSP 問題的求解；Rochanaei[3]提出了兩種新型的混合整數(shù)線性規(guī)劃模型對FJSP 問題進行求解。精確算法雖然理論上能夠求得最優(yōu)解，但需要消耗大量時間，因此只適用于小規(guī)模FJSP 問題。近似算法包括啟發(fā)式算法和元啟發(fā)式算法。元啟發(fā)式算法因能在合理的時間內(nèi)求得各類不同規(guī)模FJSP 問題的優(yōu)良解而成為目前FJSP 問題求解的主流方法，其中以智能仿生算法為典型代表。進化算法是一類代表性的智能仿生算法，包括遺傳算法、進化策略和進化規(guī)則。陳成等[4]提出了一種遺傳——蟻群算法，它分別采用遺傳算法和蟻群算法解決機器分配和工序排序問題。Kacem 等[5]首先利用局部搜索方法求解機器分配問題，再利用基于分配模型的遺傳算法求解工序排序問題，最終實現(xiàn)對多目標FJSP 問題的求解。Tay 等[6]設(shè)計一種基于遺傳規(guī)劃的組合調(diào)度規(guī)則生成框架，利用生成的組合調(diào)度規(guī)則整體解決多目標FJSP問題。趙詩奎等[7]通過對不同解碼方式的分析，設(shè)計了一種基于空閑時間的鄰域搜索方法，并與遺傳算法相融入進而整體求解FJSP 問題。龐哈利等[8]從集成化的角度建立了FJSP 問題兩層混合整數(shù)規(guī)劃模型，并提出門檻接受、遺傳算法與啟發(fā)式規(guī)則相結(jié)合的混合求解算法。群體智能算法是另一類代表性的智能仿生算法，包括蟻群優(yōu)化算法、粒子群優(yōu)化算法和人工蜂群算法等。夏蔚軍等[9]提出一種混合微粒群優(yōu)化算法求解多目標FJSP 問題，微粒群優(yōu)化用于向各機器分配工序, 模擬退火用于排序各機器上的工序并對排序結(jié)果進行評價。張靜等[10]提出一種新的粒子位置更新方式，能實現(xiàn)粒子群算法直接在離散域執(zhí)行，并引入改進的模擬退火算法來增強算法的鄰域搜索能力，使之能更有效地從整體上求解批量FJSP 問題。仲于江等[11]提出一種將小生境技術(shù)和粒子群算法相結(jié)合整體求多目標的FJSP 優(yōu)化問題最優(yōu)解的優(yōu)化方法。王凌等[12]提出一種結(jié)合關(guān)鍵路徑的人工蜂群算法用于整體求解FJSP 問題。姜天華[13]將基本的灰狼優(yōu)化算法進行改進，并結(jié)合局部搜索形成混合灰狼優(yōu)化算法，整體求解包含綠色性指標的多目標的FJSP 問題。

綜上所述，目前求解FJSP 問題主要包含分步法和集成法。雖然分步法降低了問題求解的難度，然而它割裂了兩個子問題間的復雜耦合關(guān)系，因此往往導致算法的求解質(zhì)量不高，進而目前圍繞FJSP 問題求解方法的研究主要集中在集成法。

近些年來，受自然界中各種現(xiàn)象和生物行為的啟發(fā)，各種新型的智能仿生算法被提出，并被用來求解各種復雜組合優(yōu)化問題。飛蛾撲火優(yōu)化算法（moth-flame optimization，MFO）就是其中一種比較新型的智能仿生算法，它模擬了飛蛾夜間飛行時采用的橫向定位導航機制，該定位導航機制能維持飛蛾自身相對月亮的固定角度飛行，然而由于受人工和自然點光源的影響，加之與月亮和干擾光的距離不同，導致直線飛行失效，最終呈現(xiàn)近似螺旋的飛行路徑。基于上述特性，Seyedali Mirjalili 等[14]于2015年提出了基礎(chǔ)的MFO 算法。MFO 算法因具有并行優(yōu)化能力強、全局性優(yōu)且跳出局部極值的特點，而被廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測[15]、電力系統(tǒng)潮流計算[16]、網(wǎng)絡(luò)規(guī)劃[17]、圖像檢測[18]、經(jīng)濟調(diào)度[19]、神經(jīng)網(wǎng)絡(luò)訓練[20]等領(lǐng)域，然而目前仍未見其在生產(chǎn)調(diào)度領(lǐng)域的應(yīng)用。因此，本文嘗試對飛蛾撲火優(yōu)化算法進行改進，使其能適用于柔性作業(yè)車間調(diào)度問題，為此設(shè)計出兩段式編碼轉(zhuǎn)化機制、新穎的隨機更新算子及基于Levy 飛行軌跡的隨機游走策略，通過測試標準算例和對比其他算法求解結(jié)果，驗證本文算法的有效性與優(yōu)越性，同時為MFO 算法在類似問題上的應(yīng)用提供了參考。

1 柔性作業(yè)車間調(diào)度問題

1.1 問題描述

FJSP問題可描述為：有n個待加工工件和m個機器，每個工件的工序數(shù)為nini≥1（ ），每道工序可以在多臺機器上進行加工，且每個工序在每臺可加工的機器上的加工時間已知。FJSP需要解決兩個問題：機器選擇和工序排序。機器選擇是需要為每道工序確定其加工機器，工序排序是需要為在同一個機器上加工的工序確定其加工的先后順序。本文的優(yōu)化目標是最大完工時間最小。此外，它往往滿足以下假設(shè)條件：1）所有工件和機器在零時刻均處于就緒狀態(tài)；2）同一時刻一個機器最多只可加工一個工件；3）不允許搶占情況發(fā)生，即工件加工過程不可中斷；4）同一個工件的工序之間具有優(yōu)先級關(guān)系，而不同工件的工序之間相互獨立；5）各工件加工優(yōu)先級相同；6）忽略工序加工前機器所需的準備時間。

1.2 模型建立

為便于模型建立，定義各符號如下：Ci為工件i的完工時間；n為工件數(shù)量；m為機器數(shù)量；ni為工件i的工序數(shù)；Oij為工件i的第j道工序；Mij為工序Oij的加工機器集；mij為工序Oij的可加工機器數(shù)；xijk為工序Oij在機器k上進行加工；tijk為工序Oij在機器k上的加工時間；stijk為工序Oij在機器k上加工的開始時間；etijk為工序Oij在機器k上加工的結(jié)束時間；Cmax為整個加工過程的完工時間。

其中：式（1）為目標函數(shù)；式（2）為工藝約束；式（3）為機器約束，一個工序只能在一個機器上加工；式（4）也為機器約束，一個機器在同一個時刻最多只能加工一道工序；R為一充分大的正數(shù)。

2 基本飛蛾撲火優(yōu)化算法

基本MFO算法采用了基于火焰種群的位置更新機制?；鹧娣N群代表飛蛾種群的優(yōu)良個體，按照優(yōu)良個體的適應(yīng)度值大小排序生成，然后將火焰種群的位置向量作為參考更新飛蛾種群的位置，在更新過程中，飛蛾種群的個體與火焰種群的個體一一對應(yīng)進行位置的更新。由于對優(yōu)良個體的完全保留，火焰種群極易陷入局部最優(yōu)位置。為了平衡全局搜索和局部開發(fā)能力，MFO算法設(shè)定火焰種群的數(shù)量隨著迭代的進行線性減少，到最后只剩下最優(yōu)的個體。在飛蛾種群位置更新時，超過火焰種群數(shù)量的飛蛾個體圍繞最差的火焰?zhèn)€體進行位置更新。飛蛾位置更新的公式如下所示：

式中：t為當前迭代次數(shù)；Mi為飛蛾個體；Fj為火焰?zhèn)€體；S為飛蛾圍繞火焰的飛行機制；Di為飛蛾與火焰之間的絕對距離；a為[r,1]之間的隨機向量，其大小表示飛蛾接近火焰的程度（a=-1表示最接近，a=1表示最遠離）；r為收斂常數(shù)，在算法迭代過程中，r是從-1線性遞減到-2；b為螺旋方程參數(shù)。

具體的基本MFO算法的步驟可參考文獻[14]。

3 改進離散型飛蛾撲火優(yōu)化算法

3.1 兩段式編碼

FJSP包含機器選擇和工序排序兩個問題，為了采用集成法的求解思路對問題進行求解，所以采用兩段式編碼方法。兩部分編碼的長度均為工序的總數(shù)目，假設(shè)工序總數(shù)目為l，則編碼的總長度為2l。假設(shè)編碼方案為P=｛p1,p2,…,pl,pl+1,pl+2,…,p2l｝，則pi的取值范圍為［-δ,δ］內(nèi)的實數(shù)值，一般δ取1。若有2個工件，3個機器，每個工件有3道工序，每道工序的可加工機器和加工時間如表1所示，表中數(shù)字表示工序在對應(yīng)機器上的加工時間，“-”表示工序不能在對應(yīng)機器上加工。則一條兩段式編碼的染色體如圖1所示。

表1 示例數(shù)據(jù)

圖1 示例編碼

3.2 編碼轉(zhuǎn)換機制

由于基本MFO算法最初設(shè)計是為了解決連續(xù)優(yōu)化問題而提出的，而FJSP問題為離散型的組合優(yōu)化問題，為了適應(yīng)FJSP問題的特性，還需要對上述兩段式編碼的染色體進行變換，建立起染色體連續(xù)空間與問題離散決策空間的映射關(guān)系。由于機器選擇和工序排序的約束及要求不同，故需要分別采取不同的轉(zhuǎn)換機制，同時，由于進化機制的原因，染色體部分位置的連續(xù)實數(shù)值可能會超出范圍，因此也需要設(shè)計相應(yīng)的調(diào)整機制。

3.2.1 機器選擇轉(zhuǎn)換方法

本文設(shè)計的機器選擇轉(zhuǎn)換方法具體操作步驟如下：1）按照公式（9）將每個位置的連續(xù)編碼轉(zhuǎn)化為對應(yīng)工序的機器集序號；2）將編（序）號映射為對應(yīng)的機器集中的機器號。根據(jù)上述轉(zhuǎn)換方法則可獲得所有工件的每道工序的加工機器，即工序的機器選擇方案：式中：m(i)為第i個位置的實數(shù)值編碼；z(i)為第i個位置對應(yīng)工序的可加工機器集中的機器數(shù)量；round為四舍五入函數(shù)，保證轉(zhuǎn)化后的每個序號均為正整數(shù)。

圖1中所示染色體對應(yīng)的機器選擇轉(zhuǎn)換過程如圖2所示。其中，機器編碼按照工件編號和工序的順序約束順序排列，第一個位置為工件1的第一道工序O11，第二個位置為O12，依次為O13、O21、O22、O23。準換后的編碼分別為1、1、0、0、1、0，則O11選擇加工機器集中的第二個機器，即機器2，O12選擇第二個機器，為機器3，O13選擇第一個機器，為機器1，O21選擇第一個機器，為機器1，O22選擇機器2，O23選擇機器1。

3.2.2 工序排序轉(zhuǎn)換方法

圖2 機器選擇編碼

本文設(shè)計的工序排序轉(zhuǎn)換方法具體操作步驟如下：1）將工序編碼中的每個元素從左到右按照順序分配一個固定ID；2）按照從大到小的順序?qū)⒏髟刂匦屡帕?，并將之前分配的ID放到其對應(yīng)元素的位置，形成一個新的排列；3）根據(jù)排列結(jié)果構(gòu)造出工序的排序方案。以圖1中的編碼為例，其工序編碼為0.34、0.26、-0.21、0.75、-0.54、0.88，則其每個位置對應(yīng)的ID為1、2、3、4、5、6，再按照LPV規(guī)則排序，得到新的排列為0.88、0.75、0.34、0.26、-0.21、-0.54，則其ID映射為6、4、1、2、3、5，由于工件1有3道工序，則ID在1～3的元素為工件1的工序，ID在4～6的元素為工件2的工序，形成的工序排序方案為2、2、1、1、1、2，轉(zhuǎn)化為調(diào) 度 方 案O21、O22、O11、O12、O13、O23。具體的轉(zhuǎn)換過程如圖3所示。

3.2.3 調(diào)整規(guī)則

按照MFO算法中飛蛾個體的螺旋飛行機制，兩段式編碼染色體位置元素更新后可能出現(xiàn)位置的值超出范圍，因此，需要設(shè)計相應(yīng)的調(diào)整規(guī)則。本文采用的調(diào)整規(guī)則為：

圖3 工序排序編碼

3.3 主動式解碼

目前針對作業(yè)車間調(diào)度問題的解碼方式主要有兩種，分別為半主動解碼和主動解碼。業(yè)已證明，以最大完工時間為優(yōu)化目標時，最優(yōu)解必在主動調(diào)度集中[21]。本文采用一種基于貪婪解碼[22]的主動解碼方法。它首先根據(jù)通過機器選擇轉(zhuǎn)化機制獲得的工序機器選擇方案來確定每道工序的加工機器及相應(yīng)的加工時間，然后按照通過工序排序轉(zhuǎn)化機制獲得的工序排序方案確定工序加工順序，依次進行解碼，在不推遲其他已安排工序開工時間的條件下，將工序插入到對應(yīng)機器上最早可行的時刻加工[23]。

3.4 種群初始化

在FJSP問題中，機器的選擇對于個體的質(zhì)量非常重要，若在生成初始解的考慮選擇加工時間較短或者使機床負荷比較均衡的策略，則可以提高初始解的質(zhì)量，進而提高算法的求解效率。因此，在隨機生成50%個體的基礎(chǔ)上，本文引入兩種初始解生成方案：局部選擇和全局選擇。其中，局部選擇是指為每道工序選擇加工時間最短的機器，30%個體由此方式產(chǎn)生；全局選擇是指隨機選擇工序，使得工序選擇完成后，根據(jù)工序選擇對應(yīng)機床，使得每個機床的加工時間波動最小，其整體負荷盡量均衡，剩下的20%個體由全局選擇生成。

3.5 隨機更新算子

在基本的MFO中，飛蛾種群作為搜索的主體，在更新過程中，與火焰種群數(shù)量相當?shù)娘w蛾個體按照順序圍繞著飛蛾個體進行一一更新，超出火焰種群數(shù)量的飛蛾個體圍繞著最差的火焰?zhèn)€體進行螺旋飛行，這樣導致在后期由于火焰?zhèn)€體數(shù)量的減少，最差的火焰與最優(yōu)的火焰?zhèn)€體相差較小，使得整個飛蛾種群喪失多樣性，算法易陷入局部最優(yōu)解。因此，本文設(shè)計了一種隨機更新算子。它將實現(xiàn)在整個飛蛾種群圍繞火焰種群更新的過程中，將原來的順序更新變?yōu)殡S機選擇更新，即按照順序選擇飛蛾個體圍繞隨機選擇的火焰?zhèn)€體進行螺旋飛行，實現(xiàn)對飛蛾位置的更新，達到跳出局部最優(yōu)解的目的。

3.6 Levy飛行策略

Levy飛行策略是一種由法國數(shù)學家Paul Pierre Levy提出的重尾分布的隨機游走策略，它模仿動物在搜尋食物過程中的一種具有Markov鏈特征的隨機行走方式，在行走路徑的形成過程中，下一步的移動方向基于當前的狀態(tài)和狀態(tài)轉(zhuǎn)移概率。大量的研究已證明許多動物和昆蟲都具有這種典型的Levy飛行特征，能夠顯著地提高種群的多樣性，提高算法的全局搜索能力。Levy大多用于連續(xù)優(yōu)化問題中，還未見有在FJSP問題上的應(yīng)用。因此，本文嘗試將Levy策略引入到IDMFO中，探究此策略在FJSP問題中的適用性。

根據(jù)上文的介紹可知，隨著火焰種群線性減少，在迭代后期，火焰數(shù)量也隨著減少，種群存在容易喪失多樣性而陷入局部最優(yōu)解的風險，所以考慮引入Levy飛行策略來增強算法的尋優(yōu)能力。

其中：Mti為當代的飛蛾個體；Mt+1i為Levy飛行后的新的飛蛾個體；Fbest為最優(yōu)的火焰?zhèn)€體；c為[0,1]內(nèi)的隨機數(shù)；F為標準的伽馬函數(shù)；βi∈(0,2］。

3.7 IDMFO算法步驟

步驟1：設(shè)置算法參數(shù)，根據(jù)種群初始化方法生成初始種群。步驟2：評價種群的適應(yīng)度值，選出火焰種群。步驟3：根據(jù)式（5）～式（8）更新飛蛾種群的位置向量、火焰種群的數(shù)量及螺旋參數(shù)。步驟4：根據(jù)式（11）～式（14）產(chǎn)生新的飛蛾種群。步驟5：評價新的種群，更新火焰種群。步驟6：判斷算法是否滿足終止條件，若是，則轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟3。步驟7：終止算法并輸出結(jié)果。整個IDMFO算法的流程如圖4所示。

圖4 IDMFO算法流程圖

4 實驗分析

實驗運行環(huán)境為Intel Core i3-8100 CPU 3.6 GHz，RAM 8.00 GB，Windows10，64 位 操 作 系 統(tǒng) 和Pycharm 2018.2.4。為了測試算法的性能，采用FJSP國際標準算例中Kacem8×8，10×10，15×10算例[23]和Brandimare[25]算例Mk01-10進行試驗，各算法對每個算例獨立運行求解10次，獲得解的情況如表2所示，其中MFO表示基本MFO算法，MFO1表示結(jié)合種群初始化方法的MFO算法，MFO2為結(jié)合種群初始化方法和隨機更新算子的MFO算法，IDMFO為本文改進離散MFO算法，加粗結(jié)果表示上述4種算法求得問題的最優(yōu)解。上述算法中相關(guān)參數(shù)取值如下：種群規(guī)模為100，最大迭代次數(shù)為300，螺旋參數(shù)為1，收斂常數(shù)為-1。

表2 算法求解結(jié)果

從表2中數(shù)據(jù)可以看出，IDMFO在所有算例上均取得最佳的結(jié)果，最優(yōu)解的平均值也明顯優(yōu)于其他的幾種MFO算法，在算法運行時間上，與其他算法相比無太大的差別。因此，本實驗驗證了本文所提算法能在保證時間效率的同時，又能夠提高算法的全局搜索能力，有效避免陷入局部最優(yōu)解。此外，相比于未采用Levy策略的MFO算法，融入Levy策略的MFO算法明顯具有更強的求解能力，驗證了引入Levy策略確實能夠起到增強算法全局搜索能力的效果，擴展了Levy策略的應(yīng)用領(lǐng)域。

為了進一步證明本文算法的求解效果，與文獻［26］～［28］中算法的求解結(jié)果進行對比，如表3所示，其中加粗結(jié)果表示所有算法求得問題的最優(yōu)解。

表3 算例求解結(jié)果的對比

從表3數(shù)據(jù)中可以看出，在上述13個標準算例中，IDMFO算法分別能在Kacem02、Mk01、Mk03、Mk04、Mk07、Mk08和MK10的7個算例上都獲得了最優(yōu)解，尤其是在Mk04、Mk07和Mk10上能獲得唯一的最優(yōu)解，其中求得Mk07的最優(yōu)結(jié)果甘特圖如圖5所示。相較而言，文獻［26］、［27］和［28］中算法獲得最優(yōu)解算例的個數(shù)分別為3、5和5，因此，本文算法在求解柔性作業(yè)車間調(diào)度問題的有效性與優(yōu)越性得以進一步驗證。

圖5 IDMFO求解Mk07的最優(yōu)結(jié)果甘特圖

5 結(jié) 論

本文將飛蛾撲火優(yōu)化算法用于柔性作業(yè)車間調(diào)度問題中，針對該問題的離散特性，設(shè)計出一種兩段式編碼轉(zhuǎn)化機制，建立了染色體連續(xù)空間與問題離散決策空間的映射關(guān)系；同時，采用隨機、局部選擇和全局選擇相結(jié)合的初始化方法來提高初始解的質(zhì)量及種群的多樣性；在算法運行過程中，設(shè)計了隨機更新算子和Levy隨機游走策略來加強算法的全局搜索能力，使其跳出局部最優(yōu)解。最后，采用標準算例進行仿真試驗，并與其他文獻中算法求解結(jié)果進行對比，有力地驗證了本文所提算法的有效性與優(yōu)越性。

在后續(xù)的研究過程中，可以將IDMFO算法與其他局部搜索算法結(jié)合形成混合算法，或者與其他群體智能優(yōu)化算法結(jié)合形成協(xié)同進化機制，進一步提高算法搜索能力。此外，可以將多目標優(yōu)化方法與IDMFO算法進行有效結(jié)合形成多目標飛蛾撲火優(yōu)化算法，求解更加復雜的多目標組合優(yōu)化問題。