李雪花，高全力，趙 輝，楊 昊，金 帥，徐國(guó)梁

(1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048;2.山東如意毛紡服裝集團(tuán)股份有限公司，山東 濟(jì)寧 272000;3.山東如意恒成產(chǎn)研新材料科技有限公司，山東 濟(jì)寧 272000)

0 引 言

柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job-Shop Scheduling Problem，F(xiàn)JSP)是離散制造業(yè)、流程工業(yè)等實(shí)際生產(chǎn)中的核心問(wèn)題。FJSP問(wèn)題是JSP(Job-shop Scheduling Problem)問(wèn)題的擴(kuò)展，包括復(fù)雜的約束條件，包括對(duì)每個(gè)工序加工時(shí)間，工序的加工順序，以及加工設(shè)備的約束。因此，F(xiàn)JSP是一個(gè)典型的NP難問(wèn)題。解決FJSP問(wèn)題的常見方法是群智能算法，一些最常用的算法包括遺傳算法、粒子群算法、魚群算法等。

遺傳算法(Genetic Algorithm，GA)是一種通過(guò)模擬自然進(jìn)化機(jī)制來(lái)搜尋最優(yōu)解的全局優(yōu)化算法[1]，全局搜索能力強(qiáng)，具有可擴(kuò)展性，容易與其他算法結(jié)合，但其局部搜索能力較差，容易“早熟”收斂，且對(duì)初始種群的選擇有一定的依賴性[2]。近些年來(lái)一些學(xué)者通過(guò)融合遺傳算法與其他算法來(lái)改善其魯棒性，實(shí)現(xiàn)性能提升。陶澤等融合了遺傳算法和模擬退火算法，從而提高了種群的收斂速度并防止種群陷入局部最優(yōu)[3]。LI等提出一種將禁忌搜索算法與遺傳算法有效結(jié)合的禁忌混合遺傳算法，增強(qiáng)了遺傳算法局部搜索能力，但計(jì)算成本較高[4]。楊振泰等提出了一種結(jié)合powell搜索法的遺傳算法，改善了GA算法在迭代過(guò)程中產(chǎn)生比可行解的情況[5]。賈培豪等融合鯨魚算法和遺傳算法，改進(jìn)傳統(tǒng)遺傳算法后期的局部搜索能力，提高算法求解質(zhì)量[6]。綜上所述,標(biāo)準(zhǔn)的遺傳算法融合其他算法是求解FJSP問(wèn)題的趨勢(shì)所在。該文提出一種混合遺傳算法，在遺傳算法的基礎(chǔ)上，在初始種群生成時(shí)采用混沌理論產(chǎn)生分布均勻的隨機(jī)數(shù)提高初始種群在解空間分布的均勻性，且根據(jù)FJSP問(wèn)題特性改進(jìn)交叉、變異規(guī)則,將表現(xiàn)優(yōu)異的個(gè)體加入優(yōu)良種子庫(kù)進(jìn)行保護(hù)。并采用混合蛙跳算法對(duì)優(yōu)良種子庫(kù)進(jìn)行局部搜索尋優(yōu),將得到的更優(yōu)解與下輪個(gè)體交叉迭代,提高局部搜索能力，改善傳統(tǒng)遺傳算法“早熟”問(wèn)題。通過(guò)對(duì)mk01～mk10標(biāo)準(zhǔn)算例進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證了該算法的有效性與可行性。

1 FJSP概述

1.1 問(wèn)題描述

FJSP問(wèn)題一般包含n個(gè)工件，Job={J1,J2,…,Jn}，每個(gè)工件都有一道或多道加工工序，某一工序可以在機(jī)器集M中，M={M1,M2,…,Mn}，任意選擇一臺(tái)進(jìn)行生產(chǎn)加工,其加工時(shí)間與選擇的機(jī)器相關(guān)。處理FJSP問(wèn)題時(shí)需要考慮工序的加工順序、加工機(jī)器和最大完工時(shí)間。該文以“最小化最大完工時(shí)間”作為優(yōu)化目標(biāo)。

1.2 數(shù)學(xué)模型

為了便于解釋FJSP的數(shù)學(xué)模型,相關(guān)參數(shù)(見表1)如下：

優(yōu)化目標(biāo)：

(1)

約束條件：

(1)每道工序的加工時(shí)間約束：

Si,j+pi,j,k≤Ei,j

(2)

asi,j≥Ei,j-1

(3)

Ej,nj≤Cmax

(4)

(2)同一工件的相鄰兩道工序的加工時(shí)間約束:

Ei,j≤Si,j+1j+1≤ni

(5)

(Si,j+pi,j,.k)bi,j,p,q≤Sp,q,i≠p或j≠q

(6)

(3)某工件的某工序選擇的加工機(jī)器約束:

(7)

表1 FJSP相關(guān)參數(shù)符號(hào)定義

2 混合蛙跳算法

SFLA(Shuffled Frog Leaping Algorithm)[7]是根據(jù)青蛙種群在石塊上覓食時(shí)的分布變化而提出的算法。青蛙所在的池塘中有若干石塊，青蛙們會(huì)按照特定規(guī)則被分配到石塊相應(yīng)位置上。每個(gè)青蛙的位置代表了問(wèn)題的一個(gè)可行解。在每一代中，每個(gè)石塊上處于最差位置的青蛙會(huì)跳動(dòng)，該青蛙首先會(huì)朝向位于同一石塊上最優(yōu)位置的青蛙跳動(dòng)，若跳動(dòng)后的新位置比原來(lái)位置差則向著全局最優(yōu)位置跳動(dòng)，若該位置仍舊比原位置差則再在解空間內(nèi)隨機(jī)跳動(dòng)一次，可見可以跳動(dòng)的青蛙最少跳動(dòng)一次，最多跳動(dòng)三次。當(dāng)每個(gè)石塊上的青蛙都跳動(dòng)后，將各個(gè)石塊上的青蛙合并，并重新合并然后分組，重復(fù)上述跳動(dòng)過(guò)程，直到滿足終止條件。流程如圖1所示。

圖1 混合蛙跳算法過(guò)程

詳細(xì)步驟如下：

Step1：將優(yōu)良種子庫(kù)中的種群作為青蛙種群分為K個(gè)組，位列第1的青蛙被分配給第1組，位列第2的青蛙分配給第2組，以次類推，直至將所有青蛙分別分配到K個(gè)組中，每個(gè)組中包含N/K個(gè)青蛙。

Step2：對(duì)每組執(zhí)行搜索過(guò)程。每組中排在最后位置的青蛙R向這個(gè)組中位置第一的青蛙F跳變，跳變規(guī)則為：Oi,j為R青蛙的OS部分與F青蛙的OS部分相異的基因位表示的工序，將此工序當(dāng)前安排的加工機(jī)器替換為此工序可選機(jī)器中時(shí)間加工最短的機(jī)器。若有多個(gè)相異工序，則全部替換。如圖2，F(xiàn)青蛙與R青蛙第三個(gè)位置的基因不同，此基因代表的工序是O3,1，因此根據(jù)規(guī)則將R青蛙MS部分代表O3,1的加工機(jī)器3替換為時(shí)間更短的加工機(jī)器2。然后計(jì)算R青蛙的適應(yīng)度值，若優(yōu)于位置第一的染色體，則替換其位置，否則繼續(xù)變換。

圖2 跳變規(guī)則

Step3：判斷是否滿足停止條件，如滿足停止條件則停止。如不滿足則跳轉(zhuǎn)Step2執(zhí)行。為防止將解劣化，若R青蛙沒(méi)有跳動(dòng)則此青蛙保持原來(lái)的值。

3 算法的總體過(guò)程

整體算法流程如圖3所示。

圖3 算法整體流程

算法具體步驟如下：

Step1：采用1.2節(jié)提出的混沌隨機(jī)數(shù)發(fā)生器生成隨機(jī)數(shù)，并結(jié)合GLR機(jī)器選擇法[8]，其中GS:LS:RS=0.6:0.3:0.1，從而生成分布均勻且個(gè)體適應(yīng)度較好的初始種群，個(gè)體適應(yīng)度值為Fi=1/Cmax。

Step2：若迭代次數(shù)大于MAXGEN，則找到當(dāng)前最優(yōu)解作為問(wèn)題的最終解；否則，執(zhí)行Step3。

Step3：采用輪盤賭選擇法從種群中選擇子代種群。

Step4：以概率pc在Step3選擇的子代種群中選擇進(jìn)行交叉操作的部分個(gè)體，再以交叉方式選擇概率px選擇采取何種交叉方式。

Step5：根據(jù)變異概率pm，從交叉后的種群中選取需要變異操作的個(gè)體，進(jìn)行變異操作。

Step6：選取適應(yīng)度值高的個(gè)體加入遺傳優(yōu)良種子庫(kù)。

Step7：執(zhí)行混合蛙跳算法，在遺傳優(yōu)良種子庫(kù)中進(jìn)行局部搜索尋優(yōu)，更新優(yōu)良種子庫(kù)。

Step8：跳轉(zhuǎn)執(zhí)行Step2。

3.1 染色體編碼方案

文中染色體編碼方案采用MS-OS編碼方案[6]，如圖4所示，包括四個(gè)工件，每個(gè)工件包括兩道工序。染色體編碼分成兩部分：OS(Operations Sequencing)部分與MS(Machines Selection)部分。OS部分有Osum位，數(shù)字i出現(xiàn)的第j次,代表工序Oi,j。例如圖4中OS部分的第一個(gè)“1”代表O1,1，即第一個(gè)工件的第一道工序，第二個(gè)1代表O1,2，即第一個(gè)工件的第二道工序。

圖4 FJSP染色體編碼示例圖

MS部分也有Osum位，按工件順序排列，第i個(gè)工件領(lǐng)域的第j位置數(shù)字m，表示Oi,j選擇其可選加工機(jī)器的第m個(gè)機(jī)器進(jìn)行加工。如圖4中MS部分有四個(gè)工件，每個(gè)工件有兩道工序，J1領(lǐng)域的第一位數(shù)字“1”，代表O1,1工序選擇在O1,1的可選加工機(jī)器集合Mi,j中的第1個(gè)機(jī)器上；J1領(lǐng)域的第二位數(shù)字“2”，代表O1,2工序需要安排在O1,2的可選加工機(jī)器集合Mi,j中的第1個(gè)機(jī)器上。解碼時(shí)，當(dāng)工序Oi,j被安排在機(jī)器k，即mi,j,k=1，檢查機(jī)器k所有空閑時(shí)區(qū)[ts,te]，若存在區(qū)間滿足max(asi,j,ts)+pi,j,k≤te，則將工序Oi,j插入到區(qū)間[ts,te]中，且Si,j=ts。若不存在則放置到機(jī)器加工隊(duì)列最后。

3.2 種群初始化

基于混沌原理所產(chǎn)生的隨機(jī)數(shù)在限定空間內(nèi)具有更好的遍歷性和隨機(jī)性，并且具有產(chǎn)生速度快、易于實(shí)現(xiàn)等特點(diǎn)。將其應(yīng)用在遺傳算法中，從而提高初始種群在解空間分布的均勻性及降低算法陷入局部最優(yōu)解的可能性。所以文中所有的隨機(jī)參數(shù)均為提出的結(jié)合Tent映射與Logistic映射的混沌隨機(jī)數(shù)發(fā)生器生成。

Tent混沌映射生成器[9]的迭代公式如下:

(8)

Tent映射是在區(qū)間[0,1]之間的兩個(gè)分段的線性迭代,包含一個(gè)參數(shù),其中γ為常數(shù)，γ∈[0,1]。序列的計(jì)算過(guò)程為：在區(qū)間(0，1)中任意選擇一個(gè)初始迭代點(diǎn)，迭代計(jì)算Xn+1即可得到一個(gè)該區(qū)間上的混沌映射。Logistic混沌映射的迭代公式如下[10]:

Xn+1=f(xn)=α×xn×(1-xn),0

(9)

其中，α為L(zhǎng)ogistic參數(shù)，當(dāng)3.569 945 6<α≤4時(shí)，迭代生成的值非周期，有良好的隨機(jī)性。n為其迭代次數(shù)。 該文將Logistic結(jié)合Tent得到隨機(jī)數(shù)生成器，取α=4,γ=0.5。其迭代公式如下：

(10)

3.3 選擇操作

采用輪盤賭選擇法從種群中選擇子代種群[8]，個(gè)體選中的概率與其適應(yīng)度函數(shù)值成正比，即適應(yīng)度越大被選擇進(jìn)行交叉操作的概率Pi越大。Pi計(jì)算方式如下：

(11)

3.4 交叉操作

機(jī)器選擇MS部分采用均勻交叉方式交叉，即依次掃描每個(gè)基因，以概率PS與對(duì)位基因進(jìn)行交叉操作，PS為0.5，如混沌隨機(jī)數(shù)大于PS，則與對(duì)位基因互換，否則不互換。

3.5 OS部分的交叉操作

OS交叉操作選擇改進(jìn)SEX[8](子路徑交交換交叉)交叉方式，如圖5所示。隨機(jī)劃分工件為兩個(gè)非空集合，隨機(jī)選擇其中一個(gè)集合，在兩個(gè)父代染色體中選中此集合基因，然后順序交換兩個(gè)父代其余位置基因，得到兩個(gè)子代。

圖5 子路徑交交換交叉示意圖

3.6 變異算子

(12)

3.7 優(yōu)良種子庫(kù)

遺傳算法中交叉算子全部來(lái)自于當(dāng)前種群，即有可能當(dāng)前種群經(jīng)過(guò)選擇的優(yōu)秀個(gè)體在交叉時(shí)被破壞了。為了解決這一問(wèn)題，該文采用優(yōu)良遺傳庫(kù)策略，將當(dāng)前種群產(chǎn)生的優(yōu)良個(gè)體加入優(yōu)良種子庫(kù)，并利用混合蛙跳算法(SFLA)針對(duì)OS序列對(duì)應(yīng)的MS序列尋優(yōu)，從而得到更優(yōu)的目標(biāo)函數(shù)，得到的更優(yōu)解供下一輪迭代的交叉操作，從而保留優(yōu)秀個(gè)體并有目的性地對(duì)MS序列進(jìn)行優(yōu)化。

4 算法測(cè)試與數(shù)值實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

為檢驗(yàn)該算法的有效性與可行性，通過(guò)Brandimarte(mk01～mk10)[12]算例對(duì)算法進(jìn)行測(cè)試。算法實(shí)現(xiàn)采用JAVA語(yǔ)言，實(shí)驗(yàn)環(huán)境為windows10系統(tǒng)，處理器為Intel i7 10750H 六核CPU、主頻為2.60 GHz、內(nèi)存16 GB。種群規(guī)模Size=200，最大迭代次數(shù) MAXGEN=200；交叉概率pc=0.8，交叉方式選擇概率px=0.3，變異概率pm=0.05；優(yōu)良種子庫(kù)的容量Cseed為種群規(guī)模的10%。為充分體現(xiàn)混合蛙跳算法尋優(yōu)能力，其分組個(gè)數(shù)K=10。

4.2 測(cè)試用例及實(shí)驗(yàn)結(jié)果

將mk01～mk10分別計(jì)算10次，記錄最優(yōu)值及平均值，將其與文獻(xiàn)[6,13]提出的算法結(jié)果及一般GA算法結(jié)果進(jìn)行比較，如表2所示，可以看出除了mk06與mk07算例，其他均得到了所對(duì)比算法中的最優(yōu)解，驗(yàn)證了文中算法的有效性。

表2 各算法對(duì)MK08算例求解結(jié)果對(duì)比分析

以20*10即20個(gè)工件10臺(tái)機(jī)器的mk08算例為例，算例描述如表2所示。圖6對(duì)比了傳統(tǒng)GA、文獻(xiàn)[6,13]所提算法的性能。可以看出由于文中算法采用了混沌理論使初始解在解空間分布更均勻，所以初始種群的最優(yōu)值優(yōu)于傳統(tǒng)GA及文獻(xiàn)[6,13]所提算法，且由于改進(jìn)了交叉與變異策略及采用了保優(yōu)策略，算法收斂速度優(yōu)于其他算法且文中算法得到了目前的mk08算例的最優(yōu)解。

圖6 mk08算例求解收斂圖

圖7為文中算法對(duì)mk08算例的最佳調(diào)度甘特圖，查閱mk08算例的源文件得知任何工件的任何工序都沒(méi)有涉及到使用機(jī)器6，從圖中也可以看到機(jī)器6為空閑狀態(tài)，從而也從側(cè)面驗(yàn)證了文中算法的可行性與正確性。

圖7 mk08算例調(diào)度甘特圖

5 結(jié)束語(yǔ)

針對(duì)柔性作業(yè)車間調(diào)度中最小化最大完工時(shí)間單目標(biāo)，提出一種融合遺傳算法與混合蛙跳算法的混合算法。對(duì)遺傳算法的變異與交叉規(guī)則根據(jù)柔性作業(yè)車間調(diào)度問(wèn)題的特性進(jìn)行了改進(jìn)，合理改進(jìn)了算法搜索過(guò)程的廣度與深度。通過(guò)對(duì)Brandimarte算例的測(cè)試，驗(yàn)證了該算法的可行性與有效性。并運(yùn)用混沌理論生成隨機(jī)數(shù)以使初始解在解空間分布更均勻，設(shè)計(jì)一種存優(yōu)策略，且運(yùn)用混合蛙跳算法提高了局部搜索能力。在未來(lái)的研究中，將考慮優(yōu)化數(shù)學(xué)模型，考慮更多影響因素，并且考慮與文獻(xiàn)[14]所用布谷鳥算法融合，使其更符合實(shí)際的生產(chǎn)環(huán)境。