基于Lévy Flight的混合GA在柔性作業(yè)車(chē)間調(diào)度問(wèn)題中的性能分析

張正敏，管在林，岳 磊

(1.華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院，湖北 武漢 430074；2.廣州大學(xué) 機(jī)械與電氣工程學(xué)院，廣東 廣州 510006)

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(flexible job-shop scheduling problem, FJSP)是目前制造業(yè)中常見(jiàn)的簡(jiǎn)化生產(chǎn)模型，F(xiàn)JSP問(wèn)題已被證明為NP難問(wèn)題[1]，計(jì)算復(fù)雜度及時(shí)間開(kāi)銷(xiāo)隨著問(wèn)題規(guī)模的增大呈指數(shù)增長(zhǎng)，故使用精確算法較難快速解決問(wèn)題。相比之下，元啟發(fā)式算法基于其簡(jiǎn)單的算法結(jié)構(gòu)與高效的迭代機(jī)制，被廣泛用于各類(lèi)生產(chǎn)組合優(yōu)化問(wèn)題。常用的元啟發(fā)式算法包括遺傳算法(GA)、模擬退火算法(SA)、人工蜂群算法(ABC)、禁忌搜索算法(TS)等，不同的算法在魯棒性、全局/局部搜索能力等特征上具有不同的表現(xiàn)，因此不少學(xué)者將不同元啟發(fā)式算法進(jìn)行混合，形成各類(lèi)混合式啟發(fā)算法，以期望提高其綜合搜索能力。由于綜合了各自算法的搜索優(yōu)點(diǎn)，部分混合算法在調(diào)度問(wèn)題上取得了較好的結(jié)果。Karimi等[2]提出了一種新的混合模擬退火的帝國(guó)主義競(jìng)爭(zhēng)算法求解考慮運(yùn)輸時(shí)間的柔性作業(yè)車(chē)間調(diào)度問(wèn)題。Jolai[3]提出了一種新的混合啟發(fā)式算法，用于求解具有順序相關(guān)的安裝時(shí)間的無(wú)等待柔性流水車(chē)間調(diào)度問(wèn)題。趙詩(shī)奎[4]針對(duì)柔性作業(yè)車(chē)間調(diào)度問(wèn)題，以最小化最大完成時(shí)間為求解目標(biāo)，提出了一種混合雙層鄰域搜索和遺傳算法的混合算法。Wang等[5]提出了一種混合人工蜂群算法求解模糊柔性作業(yè)車(chē)間調(diào)度問(wèn)題并證明了算法的高效性。

遺傳算法(GA)框架穩(wěn)定，全局優(yōu)化能力強(qiáng)，故不少學(xué)者使用GA進(jìn)行求解組合優(yōu)化問(wèn)題。然而，GA的局部搜索能力較弱，因此部分學(xué)者將局部搜索能力較強(qiáng)的算法與GA混合，形成混合GA求解問(wèn)題[6-12]。Costa等[6]提出了一種融合遺傳算法和隨機(jī)抽樣搜索方法特征的混合啟發(fā)式算法，用于解決序列相關(guān)的流程車(chē)間成組調(diào)度問(wèn)題。Gu[7]提出了一種基于自適應(yīng)遺傳算法和改進(jìn)蟻群算法相結(jié)合的作業(yè)車(chē)間調(diào)度混合優(yōu)化算法并通過(guò)實(shí)驗(yàn)證明該算法針對(duì)大規(guī)模問(wèn)題具有更好的效果。Shahsavari等[8]在遺傳算法框架的基礎(chǔ)上，結(jié)合模擬退火算法的思想形成了新的混合遺傳算法，用于求解FJSP問(wèn)題。Ren等[9]提出了一種混合遺傳算法求解作業(yè)車(chē)間調(diào)度問(wèn)題。為了增加種群的多樣性，該混合算法中使用了一種基于適應(yīng)度值和濃度值的混合選擇算子。

本文提出了一種基于Lévy flight的混合GA算法。Lévy flight是自然界中很多鳥(niǎo)類(lèi)遵從的一種飛行方式[13]。Lévy flight作為一種隨機(jī)游走方式，其短跳躍的搜索方式與偶爾長(zhǎng)跳躍的搜索方式交叉執(zhí)行，如圖1所示。Lévy flight保證了算法能夠及時(shí)跳出局部最優(yōu)點(diǎn)，擴(kuò)大了粒子的搜索范圍，增加了個(gè)體多樣性并增強(qiáng)了算法搜索能力。

圖1 連續(xù)Lévy flight搜索過(guò)程Figure 1 The search process of continuous Lévy flight

借助Lévy flight策略，Yang等[13]提出了布谷鳥(niǎo)算法(CS)，CS最先用于解決連續(xù)優(yōu)化問(wèn)題，并被證實(shí)取得了較好的效果。本文在GA框架的基礎(chǔ)上，研究了一種新的離散化Lévy flight策略對(duì)種群進(jìn)行局部?jī)?yōu)化，進(jìn)一步利用Lévy-GA算法求解FJSP，并通過(guò)對(duì)比TLBO[14]、CS、GA等算法求解，結(jié)果證明Lévy flight用在GA等全局優(yōu)化性能較強(qiáng)的算法中時(shí)具有更好的效果。

1 問(wèn)題描述

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(FJSP)是制造系統(tǒng)中一種典型的生產(chǎn)方式。本文研究的包含同速并行機(jī)的部分柔性作業(yè)車(chē)間可描述為：N個(gè)工件在M個(gè)機(jī)臺(tái)上加工，每個(gè)工件包含若干按序排列的工序，工件n的工序總數(shù)為 Pn，工件n的工序p有對(duì)應(yīng)的加工機(jī)臺(tái)集 Mnp， Mnp內(nèi)的機(jī)臺(tái)對(duì)工件n的工序p的加工時(shí)間為tnp。每道工序需要安排在某一臺(tái)機(jī)器上進(jìn)行加工。Cnp表示工件n工序p的完工時(shí)間。

本文基于以下假設(shè)條件：

1) 工件加工順序、可加工機(jī)臺(tái)集及加工時(shí)間已知且固定；

2) 一個(gè)機(jī)臺(tái)同時(shí)只能加工一個(gè)工件，一個(gè)工件同時(shí)只能被一個(gè)機(jī)臺(tái)加工；

3) 不考慮切換時(shí)間、運(yùn)輸時(shí)間，不考慮生產(chǎn)系統(tǒng)突發(fā)情況；

4) 任一工序一旦開(kāi)始加工則不可中途停止。

以最大化完工時(shí)間最小為目標(biāo)的包含同速并行機(jī)的部分FJSP決策變量與數(shù)學(xué)模型分別如下。

其中 n、i(1≤n,i≤N)代 表工件， m(1≤m≤M)代表機(jī)臺(tái)， p、k(1≤p,k≤Pn)代表工件n的工序。式(1)表示目標(biāo)函數(shù)為最小化最大完成時(shí)間；約束(2)表示每個(gè)工件都需要按照工序順序生產(chǎn)，前工序完成時(shí)間需不大于后工序開(kāi)始時(shí)間；約束(3)表示同一機(jī)臺(tái)同一時(shí)間只能加工一個(gè)工件；約束(4)表示每個(gè)工件的每個(gè)工序只能選擇一個(gè)機(jī)臺(tái)進(jìn)行加工；約束( 5)表示工件完工時(shí)間均為正數(shù)。

2 基于離散Lévy flight策略的混合遺傳算法

本文設(shè)計(jì)的基于離散Lévy flight的混合遺傳算法具體流程框架如圖2所示。該改進(jìn)算法使用了基于工序編碼基因串的交叉策略與單點(diǎn)變異策略，對(duì)每一代的精英解使用了基于離散Lévy flight的隨機(jī)搜索策略，可改善遺傳算法局部搜索能力較弱的缺點(diǎn)，同時(shí)也在一定程度上增強(qiáng)了算法的全局搜索能力。

圖2 Lévy-GA流程圖Figure 2 Flow chart of Lévy-GA

2.1 編碼與適應(yīng)度計(jì)算

FJSP需要確定工序的加工順序與每道工序?qū)?yīng)的加工機(jī)臺(tái)。本文采用的編碼由工序加工順序與對(duì)應(yīng)工序加工機(jī)臺(tái)兩部分組成。編碼示意圖見(jiàn)圖3。編碼由兩層組成，第1層為工序加工順序?qū)?yīng)的染色體編碼，“213131321”中的第1個(gè)“2”表示工件2的第1個(gè)工序，第1個(gè)“1”表示工件1的第1個(gè)工序，第2個(gè)“2”表示工件2的第2個(gè)工序，以此類(lèi)推，形成整個(gè)問(wèn)題的工序加工順序的可行解。染色體第2層為第1層對(duì)應(yīng)工序選擇的加工機(jī)臺(tái)，例如，第2個(gè)工件的第1個(gè)工序選擇M2機(jī)臺(tái)進(jìn)行加工，第1個(gè)工件的第1個(gè)工序選擇M2機(jī)臺(tái)進(jìn)行加工。每個(gè)染色體都對(duì)應(yīng)1個(gè)可行解，該可行解使用插入式貪婪解碼算法[15]進(jìn)行個(gè)體適應(yīng)度求解。個(gè)體適應(yīng)度代表當(dāng)前可行解的目標(biāo)函數(shù)，目標(biāo)函數(shù)越小，說(shuō)明個(gè)體適應(yīng)度越好。

圖3 染色體編碼方法Figure 3 The encoding method of the chromosome

2.2 交叉與變異操作

交叉與變異操作模仿了生物遺傳進(jìn)化的過(guò)程。交叉操作可使2個(gè)個(gè)體隨機(jī)交換部分基因，期望將有益的基因組合；變異操作可使個(gè)體隨機(jī)修改某些基因，期望產(chǎn)生適應(yīng)度更好的個(gè)體。本文采用基因串組合交叉策略如圖4所示。本文使用的交叉策略操作流程如下。將工件隨機(jī)分到集合J1或者J2，在父代1中將J1包含的工件對(duì)應(yīng)的工序及機(jī)臺(tái)位置直接繼承給子代1，將父代2中J2包含的工件對(duì)應(yīng)的工序及機(jī)臺(tái)按相對(duì)順序先后插入子代1的空余位置，形成完整的子代個(gè)體1。同理，在父代2中將J2包含的工件對(duì)應(yīng)的工序及機(jī)臺(tái)位置直接繼承給子代2，將父代1中J1包含的工件對(duì)應(yīng)的工序及機(jī)臺(tái)按相對(duì)順序先后插入子代2的空余位置，形成完整的子代個(gè)體2。

圖4 交叉策略示意圖Figure 4 The crossover of chromosome

本文采用基于工序基因串和基于機(jī)臺(tái)基因串的變異策略，如圖5所示?；诠ば蚧虼淖儺惒呗圆僮髁鞒虨殡S機(jī)生成小于基因串長(zhǎng)度的2個(gè)正數(shù)a、b，選擇位置a對(duì)應(yīng)的工序作為變異工序，將其挪至位置b?；跈C(jī)臺(tái)基因串的變異策略操作流程為隨機(jī)生成小于基因串長(zhǎng)度的正數(shù)c，將位置c對(duì)應(yīng)的機(jī)臺(tái)替換為該工序?qū)?yīng)可加工機(jī)臺(tái)集中的其他任意機(jī)臺(tái)。

圖5 變異策略示意圖Figure 5 The mutation of chromosome

2.3 離散Lévy flight策略

Lévy flight屬于一種隨機(jī)搜索策略，Lévy flight的步長(zhǎng)分布為滿(mǎn)足一個(gè)厚尾的穩(wěn)定分布，由Lévy flight產(chǎn)生的隨機(jī)步長(zhǎng)大概率為小步長(zhǎng)，但也有一定概率的大步長(zhǎng)游走。大的步長(zhǎng)易于搜索全局最優(yōu)，小的步長(zhǎng)有助于提高搜索精度。本文對(duì)經(jīng)過(guò)遺傳操作后產(chǎn)生的最優(yōu)個(gè)體經(jīng)過(guò)T次具有Lévy flight特征的隨機(jī)搜索，將隨機(jī)搜索后的t個(gè)個(gè)體適應(yīng)度函數(shù)與最優(yōu)個(gè)體進(jìn)行比較并擇優(yōu)替代。每次隨機(jī)搜索過(guò)程的步長(zhǎng)參考Lévy flight搜索策略進(jìn)行確定，連續(xù)Lévy flight搜索策略一般通過(guò)Mantegna算法確定步長(zhǎng)[16]。本文將Mantegna算法離散化以計(jì)算該問(wèn)題中每次隨機(jī)搜索的步長(zhǎng)S，形成了針對(duì)離散優(yōu)化問(wèn)題的Lévy flight隨機(jī)搜索策略。

為簡(jiǎn)化算法框架，本文使用的鄰域游走策略與變異策略相同，每次鄰域游走的單位為1，步長(zhǎng)S代表鄰域游走次數(shù)。如果S=2，則代表對(duì)應(yīng)個(gè)體進(jìn)行兩次鄰域游走。步長(zhǎng)S的計(jì)算公式為

其中，β為[1, 2]中的一個(gè)參數(shù)，本文取β =1.5； w根據(jù)問(wèn)題規(guī)模而變動(dòng)，一般取步長(zhǎng)影響因子 α =80； u和 v 服從正態(tài)分布： u ～N(1,1)， v～N(1,4)。

本文所提出的針對(duì)離散優(yōu)化問(wèn)題的Lévy flight隨機(jī)搜索策略偽代碼如下。

算法1離散Lévy flight策略

1: For j=1:Psize*0.2 %對(duì)前20%的精英個(gè)體進(jìn)行隨機(jī)搜索與優(yōu)化，記為pj

2: For i=1:T %對(duì)每個(gè)個(gè)體執(zhí)行隨機(jī)搜索T次，記為pi

3: S =u/|v|^( 1/β)*w； %生成隨機(jī)搜索步長(zhǎng)

5: For j=1 to S do %執(zhí)行隨機(jī)搜索

7: insert pj(:,a) after pj(:,b); %執(zhí)行工序調(diào)整

9: pj(2,c)=randi(Mnp,1); %執(zhí)行機(jī)臺(tái)選擇調(diào)整

10: End

11: best_pi(i); %計(jì)算pi適應(yīng)度

12: End

13: best=min(best_pi,pj)；%從隨機(jī)搜索個(gè)體與原個(gè)體pj中尋優(yōu)

14: End

Lévy flight隨機(jī)搜索策略應(yīng)用在GA中的核心優(yōu)點(diǎn)體現(xiàn)在：1) 該搜索策略與GA框架的適配性很高，通過(guò)簡(jiǎn)單的操作彌補(bǔ)GA局部搜索能力較弱的缺陷，僅通過(guò)一個(gè)參數(shù)(步長(zhǎng)S)就能控制局部與全局搜索；2) 該混合算法保持種群多樣性的能力極強(qiáng)。當(dāng)種群中出現(xiàn)大量重復(fù)個(gè)體時(shí)，Lévy flight隨機(jī)搜索策略能對(duì)這些個(gè)體分別進(jìn)行鄰域搜索和小概率全局搜索，保證種群多樣性。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本節(jié)通過(guò)比較其他算法求解FJSP的結(jié)果來(lái)驗(yàn)證Lévy-GA的性能。CS、TLBO和GA是目前比較流行的搜索算法，被認(rèn)為是鄰域搜索和種群搜索中高效且經(jīng)典的方法，已被用于解決許多組合優(yōu)化問(wèn)題，因此本文將以上3種算法作為對(duì)比算法。除此之外，為了客觀評(píng)估離散Lévy flight策略的通用性，本文將該策略用于TLBO中，形成了Lévy-TLBO混合算法，所有實(shí)驗(yàn)案例均分別使用CS、TLBO、Lévy-TLBO、GA和Lévy-GA進(jìn)行求解并比較求解結(jié)果。本文所使用的算法均采用Matlab R2017a軟件進(jìn)行編碼，實(shí)驗(yàn)環(huán)境為Intel?CoreTM2 Quad 1.6 GHz CPU和8G RAM個(gè)人計(jì)算機(jī)。

3.1 案例設(shè)計(jì)與參數(shù)設(shè)置

為驗(yàn)證算法的優(yōu)化性能是否穩(wěn)定，優(yōu)化效果是否顯著，設(shè)計(jì)不同規(guī)模與特征的測(cè)試問(wèn)題集，使用CS、TLBO和GA等典型算法與Lévy-GA的求解結(jié)果進(jìn)行比較，以驗(yàn)證Lévy-GA的有效性。在柔性作業(yè)類(lèi)型的車(chē)間中，工件數(shù)量、工件工序數(shù)量及可加工機(jī)臺(tái)集都是影響調(diào)度問(wèn)題特性與規(guī)模的重要變量。本節(jié)實(shí)驗(yàn)對(duì)以上3個(gè)變量設(shè)置了不同規(guī)模的變量取值區(qū)間，可生成3×3×3=27個(gè)不同規(guī)模與特性的調(diào)度問(wèn)題。例如，A_A_A代表n_Pn_ Mnp的數(shù)據(jù)取值區(qū)間分別為[4,9]，[2,5]，[1,4]，為各規(guī)模問(wèn)題分別隨機(jī)生成2例滿(mǎn)足以下區(qū)間約束的生產(chǎn)數(shù)據(jù)案例，如表1所示，表中區(qū)間約束均為均勻分布。

表1 測(cè)試問(wèn)題集實(shí)驗(yàn)數(shù)據(jù)區(qū)間Table 1 The relation data intervals of examples

本文提出的Lévy-GA算法，影響算法性能的參數(shù)主要有種群數(shù)量Psize、交叉概率pc、變異概率pm及Lévy flight搜索步長(zhǎng)的步長(zhǎng)影響因子α。針對(duì)以上關(guān)鍵參數(shù)，從27個(gè)規(guī)模的隨機(jī)案例中各抽取一組作為參數(shù)整定的測(cè)試數(shù)據(jù)集，采用實(shí)驗(yàn)設(shè)計(jì)方法(design od experiment, DOE)進(jìn)行實(shí)驗(yàn)分析，并研究參數(shù)對(duì)算法性能的影響，從而確定算法的最優(yōu)參數(shù)設(shè)置。為保證實(shí)驗(yàn)的公平性，對(duì)其他經(jīng)典對(duì)比算法的參數(shù)設(shè)置也進(jìn)行了相同實(shí)驗(yàn)，并形成最優(yōu)參數(shù)。表2分別給出了所有對(duì)比算法的最優(yōu)參數(shù)配置，其中Lévy-TLBO的自學(xué)因子參數(shù)使用離散Lévy flight策略中的隨機(jī)搜索步長(zhǎng)表示。

表2 各對(duì)比算法最優(yōu)參數(shù)配置Table 2 The best parameter value for each algorithm

3.2 測(cè)試結(jié)果與優(yōu)勝率

為了驗(yàn)證Lévy-GA的有效性，將其同CS、TLBO和GA等典型元啟發(fā)式算法及Lévy-TLBO混合算法進(jìn)行了對(duì)比。5種算法在27×2 = 54個(gè)算例上分別運(yùn)行20次。記錄各個(gè)算法在不同案例上使用相同的運(yùn)行時(shí)間經(jīng)過(guò)20次獨(dú)立運(yùn)行后所得目標(biāo)值的最優(yōu)值、平均值，并統(tǒng)計(jì)Lévy-GA相對(duì)于其他4種對(duì)比算法的改進(jìn)幅度，最優(yōu)結(jié)果使用粗體突出顯示。表3中的最后一行總結(jié)了本文所提出算法相較于其他算法的優(yōu)勝比率。

3.3 性能分析

3.3.1 性能分析與比較

1) 求解質(zhì)量。

與4種對(duì)比算法相比，Lévy-GA算法在所有算例中都可以得到最佳的目標(biāo)最優(yōu)值和平均值，如表3與表4所示。在處理小規(guī)模案例時(shí)(如“A_A_X”“B_A_X”等)，CS與其他算法的差距已經(jīng)開(kāi)始顯現(xiàn)，但GA與所提出算法的最優(yōu)解差距往往較小。針對(duì)個(gè)別算例(“A_A_A_2”)，所有對(duì)比算法均可達(dá)到最優(yōu)值。當(dāng)問(wèn)題規(guī)模增大后(如“C_X_X”“X_C_X”等)，可以明顯看出Lévy-GA得到的最優(yōu)解與均解質(zhì)量遠(yuǎn)優(yōu)于其他對(duì)比算法。表4中的統(tǒng)計(jì)也可證明所提出的算法在求解大規(guī)模問(wèn)題上的優(yōu)勢(shì)。這是由于遺傳算法在加入離散Lévy flight搜索策略后，算法可在保證全局搜索的基礎(chǔ)上，加強(qiáng)精英個(gè)體局部搜索的能力，使整個(gè)種群持續(xù)進(jìn)化的能力更強(qiáng)。

表3 測(cè)試問(wèn)題集實(shí)驗(yàn)結(jié)果與比較Table 3 Results and comparisons of 54 test problems

表4 不同規(guī)模案例優(yōu)勝比率Table 4 Superior rate of tests with different scales

2) 收斂性。

離散Lévy flight搜索策略只針對(duì)部分精英個(gè)體進(jìn)行隨機(jī)搜索，雖然搜索過(guò)程并不繁瑣，但仍然使Lévy-GA的迭代速度相較于GA僅下降了約20%。盡管如此，由于隨機(jī)搜索過(guò)程的高效性，相較于其他對(duì)比算法，Lévy-GA依然保證了相對(duì)優(yōu)越的收斂速度，能夠有效應(yīng)用于FJSP及其他組合優(yōu)化問(wèn)題中。為更直觀展現(xiàn)與比較5種算法的收斂效果，本節(jié)利用收斂曲線(xiàn)對(duì)不同算法在相同運(yùn)行時(shí)間下的收斂速度進(jìn)行評(píng)價(jià)，同時(shí)展示算法逼近最優(yōu)解的過(guò)程。選擇“B_C_A_2”“C_C_A_2”“A_A_B_2”“B_A_B_1”這4個(gè)算例并作出算法CS、TLBO、Lévy-TLBO、GA和Lévy-GA的收斂曲線(xiàn)。由圖6可知，在相同運(yùn)行時(shí)間內(nèi)，Lévy-GA均能以較快的速度收斂且獲得最優(yōu)的目標(biāo)函數(shù)值。因此，可直觀看出Lévy-GA算法的收斂速度與收斂結(jié)果均優(yōu)于其他4種對(duì)比算法。

圖6 不同算例收斂曲線(xiàn)比較圖Figure 6 Convergence curves comparison of different tests

3) 穩(wěn)定性分析。

表3記錄每個(gè)算法求解不同算例得到的最優(yōu)值與運(yùn)行20次獲得的均值。當(dāng)均值越靠近最優(yōu)值，則代表算法穩(wěn)定性越好，即(c指案例編號(hào))越小越好。計(jì)算各個(gè)算法求解的所有案例的均值 μc并定義穩(wěn)定性參數(shù)為當(dāng)穩(wěn)定性參數(shù) ω越小，代表該算法運(yùn)行結(jié)果越穩(wěn)定，如表5所示。從表5中可知，CS、GA與Lévy-TLBO穩(wěn)定性相當(dāng)且均強(qiáng)于TLBO，Lévy-GA的穩(wěn)定性強(qiáng)于其他對(duì)比算法。這是由于GA本身具有強(qiáng)大的全局搜索能力，在加入Lévy flight策略后，算法的局部搜索和全局搜索能力同時(shí)得到了增強(qiáng)，故相較于其他算法其搜索性能更加穩(wěn)定，算法魯棒性也更強(qiáng)。

表5 算法的穩(wěn)定性參數(shù)Table 5 The stability parameters of algorithms

另一方面，通過(guò)表3可進(jìn)一步發(fā)現(xiàn)，Lévy flight策略并非在所有算法中均能取得較好的效果。Lévy flight策略在遺傳算法中使用時(shí)，保證了遺傳框架全局搜索能力并增強(qiáng)了局部與全局搜索能力，從而幫助精英種群更快尋優(yōu)。而將其使用在TLBO這種本身就具備個(gè)體局部尋優(yōu)策略的算法中時(shí)，擾亂了算法原本的進(jìn)化過(guò)程，不能取得顯著的搜索效果，反而降低算法的迭代速度(迭代速度下降約40)，對(duì)算法收斂效果帶來(lái)消極影響。

圖7與圖8分別為L(zhǎng)évy-GA算法求解算例C_B_C_1(n=16,m=10)輸出的最佳調(diào)度甘特圖、最優(yōu)解與群體均值進(jìn)化曲線(xiàn)。從進(jìn)化曲線(xiàn)中可看出，所提出算法針對(duì)較大規(guī)模的調(diào)度問(wèn)題具有較快的收斂速度，群體進(jìn)化能力強(qiáng)且進(jìn)化過(guò)程穩(wěn)定，能夠快速獲得全局最優(yōu)解。

圖7 算例C_B_C_1最佳調(diào)度甘特圖Figure 7 Gantt chart of the result for test C_B_C_1

圖8 算例C_B_C_1最優(yōu)解與群體均值進(jìn)化曲線(xiàn)Figure 8 Optimization curve and mean curve of test C_B_C_1

3.3.2 適配案例分析

為驗(yàn)證算法的適配案例，使用控制變量法分析每個(gè)變量不同規(guī)模的案例的求解性能，結(jié)果如表6所示?！癤_A_X”表示工件數(shù)量為水平A的18個(gè)案例，每一行對(duì)應(yīng)的數(shù)據(jù)表示Lévy-GA相對(duì)于4個(gè)對(duì)比算法在該水平所有案例上改進(jìn)比例的均值。通過(guò)分析表6發(fā)現(xiàn)，在所有類(lèi)型案例下，Lévy-GA的求解結(jié)果均不同程度強(qiáng)于4種對(duì)比算法。其中，通過(guò)縱向?qū)Ρ劝咐?lèi)型“A_X_X”“B_X_X”和“C_X_X”的改進(jìn)結(jié)果可知，當(dāng)保持其他變量不變，工件數(shù)量 n增加時(shí)，Lévy-GA的優(yōu)化效果越來(lái)越好。同理，當(dāng)工件工序長(zhǎng)度 Pn發(fā)生變化時(shí)，其他變量保持不變時(shí)，Lévy-GA的優(yōu)化效果也是逐漸增強(qiáng)。當(dāng)可選機(jī)臺(tái)集規(guī)模 Mnp發(fā)生變化時(shí)，Lévy-GA的優(yōu)化效果依然強(qiáng)于其他對(duì)比算法，但在與TLBO、GA和Lévy-TLBO進(jìn)行比較時(shí)，并未發(fā)現(xiàn)優(yōu)化效果持續(xù)增強(qiáng)的趨勢(shì)。因此，通過(guò)對(duì)不同案例類(lèi)型、規(guī)模及算法相應(yīng)求解效果的比較與分析得出，Lévy-GA相較于4個(gè)對(duì)比算法來(lái)說(shuō)，更適合求解大規(guī)模FJSP，特別是包含大規(guī)模工件或長(zhǎng)工藝路徑的FJSP。

表6 Lévy-GA相較于對(duì)比算法改進(jìn)率Table 6 Improvement rate of Lévy-GA %

4 結(jié)論

柔性作業(yè)車(chē)間調(diào)度問(wèn)題是比較經(jīng)典的一類(lèi)組合優(yōu)化問(wèn)題，也是典型的NP難問(wèn)題，本文研究了具有同速并行機(jī)的部分柔性作業(yè)車(chē)間調(diào)度問(wèn)題，提出一種離散Lévy flight策略的混合遺傳算法進(jìn)行求解。該混合算法通過(guò)使用離散Lévy flight搜索策略對(duì)每代精英種群進(jìn)行變步長(zhǎng)搜索，可提高算法的局部搜索能力，增強(qiáng)種群多樣性。

為驗(yàn)證算法性能，本文設(shè)計(jì)27組不同規(guī)模的測(cè)試問(wèn)題集，每個(gè)問(wèn)題集中各包含2組算例。將CS、GA和TLBO等經(jīng)典算法作為對(duì)比算法，對(duì)不同規(guī)模的54個(gè)FJSP算例進(jìn)行實(shí)驗(yàn)并分析實(shí)驗(yàn)結(jié)果。結(jié)果顯示，Lévy-GA在求解大規(guī)模問(wèn)題時(shí)得到的最優(yōu)解遠(yuǎn)遠(yuǎn)優(yōu)于其他對(duì)比算法。通過(guò)對(duì)算法性能進(jìn)行分析比較，發(fā)現(xiàn)Lévy-GA在求解質(zhì)量、收斂效果與穩(wěn)定性上強(qiáng)于其他算法；使用控制變量法分析不同規(guī)模下的工件數(shù)量、工件工序數(shù)量及可加工機(jī)臺(tái)集案例，證實(shí)了Lévy-GA更適合求解大規(guī)模FJSP，特別是包含大規(guī)模工件或長(zhǎng)工藝路徑的FJSP。