裴小兵，祁文博，戴毓彤

天津理工大學(xué) 管理學(xué)院，天津 300384

在現(xiàn)代制造系統(tǒng)中，調(diào)度管理問(wèn)題一直被人們認(rèn)為是能夠直接影響企業(yè)生產(chǎn)經(jīng)濟(jì)效益的一個(gè)關(guān)鍵問(wèn)題，生產(chǎn)調(diào)度主要指通過(guò)有效合理利用現(xiàn)有資源來(lái)不斷提高企業(yè)生產(chǎn)效率。柔性作業(yè)車(chē)間調(diào)度問(wèn)題（flexible job shop scheduling problem，F(xiàn)JSP）擴(kuò)展了調(diào)度問(wèn)題搜索空間，增加了車(chē)間調(diào)度操作的靈活性，相較于其他傳統(tǒng)作業(yè)生產(chǎn)車(chē)間，在調(diào)度管理問(wèn)題方面更貼近于實(shí)際生產(chǎn)狀況，是近年來(lái)制造生產(chǎn)車(chē)間調(diào)度管理領(lǐng)域的重要研究發(fā)展熱點(diǎn)。為解決FJSP，許多學(xué)者采用了不同類(lèi)型的智能優(yōu)化算法。顧幸生等[1]在自創(chuàng)的問(wèn)題編解碼方案上建立博弈集，結(jié)合粒子群算法提出一種改進(jìn)博弈粒子群算法。王家海等[2]設(shè)計(jì)了一種有效的鄰域結(jié)構(gòu)并講其與進(jìn)化算法結(jié)合。Li等[3]以使更優(yōu)化最大求解完工后時(shí)間為目標(biāo)，提出一種可以結(jié)合禁忌搜索算法的遺傳算法來(lái)求解FJSP，并由此得到了幾個(gè)對(duì)于基準(zhǔn)問(wèn)題相對(duì)新的最優(yōu)解。Hao 等[4]提出一種可變長(zhǎng)度的染色體編碼方式，針對(duì)非支配排序遺傳算法提出了自適應(yīng)分層策略，仿真實(shí)驗(yàn)表明該改進(jìn)算法可以提高生產(chǎn)效率。姜天華[5]首次提出了混合灰狼優(yōu)化算法，將遺傳算子和變鄰域搜索策略相結(jié)合。田旻等[6]針對(duì)遺傳算法求解FJSP的不足，設(shè)計(jì)了一種分層混合遺傳算法，將種群劃分為兩層并結(jié)合鄰域搜索進(jìn)行調(diào)節(jié)。Nouri 等[7]提出了一個(gè)集成基于鄰域的遺傳算法和局部搜索技術(shù)的整體多智能體模型，以提高解的質(zhì)量。Shen等[8]開(kāi)發(fā)了一種改進(jìn)的禁忌搜索算法，以解決具有序列相關(guān)設(shè)置時(shí)間的FJSP，同時(shí)考慮了最小化完工時(shí)間的性能度量。實(shí)驗(yàn)分析結(jié)果表明，與其他實(shí)驗(yàn)算法相比，該實(shí)驗(yàn)方法仍然具有顯著的性能優(yōu)越性。

從以上研究中可以看出，元啟發(fā)式方法已經(jīng)越來(lái)越多地被用于解決FJSP 問(wèn)題，由于FJSP 的復(fù)雜性和多約束性，利用算法優(yōu)化求解的時(shí)間過(guò)長(zhǎng)成為實(shí)時(shí)調(diào)度策略的主要障礙。在不同的方法中，元啟發(fā)式算法具有計(jì)算時(shí)間合理、求解質(zhì)量高等優(yōu)點(diǎn)。Rao[9]于2016 提出了一種新的元啟發(fā)式算法Jaya，并將其應(yīng)用于諸多領(lǐng)域的優(yōu)化問(wèn)題中。在文獻(xiàn)[9]中，Jaya 與幾種存在的mete 啟發(fā)式優(yōu)化算法分別進(jìn)行了實(shí)驗(yàn)比較，實(shí)驗(yàn)和討論結(jié)果驗(yàn)證了其中Jaya 算法的有效性。與現(xiàn)有的大多數(shù)元啟發(fā)式算法相比，Jaya算法的優(yōu)勢(shì)和競(jìng)爭(zhēng)力在于不需要調(diào)整任何特定的參數(shù)，只需要種群規(guī)模和迭代次數(shù)等常用控制參數(shù)以達(dá)到最優(yōu)。并且在相對(duì)較少的函數(shù)求值次數(shù)下提供了最優(yōu)結(jié)果。Jaya 算法的局限性在于無(wú)法有效地探索解空間中的區(qū)域，容易陷入局部最優(yōu)解。Gao等[10]以快速最小化柔性機(jī)器工作時(shí)間負(fù)載長(zhǎng)度為目標(biāo)，采用Jaya算法快速求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題，與國(guó)內(nèi)現(xiàn)有的新型啟發(fā)式算法結(jié)果進(jìn)行了比較，實(shí)驗(yàn)結(jié)果證明了該新型算法的技術(shù)優(yōu)越性。Rylan等[11]在Jaya算法的基礎(chǔ)上又引入有效的局部搜索技術(shù)，提出了一種算法I-Jaya，以最大完工時(shí)間為主要性能指標(biāo)，比較了這種I-Jaya算法與其他常用元啟發(fā)式算法的不同性能，驗(yàn)證了該類(lèi)算法的性能有效性。然而，通過(guò)查閱文獻(xiàn)可知，由于Jaya算法提出時(shí)間較晚，國(guó)內(nèi)運(yùn)用Jaya求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題的研究還較少，且運(yùn)用Jaya求解調(diào)度問(wèn)題仍有很大的改進(jìn)空間。

綜上所述，本文針對(duì)Jaya算法易陷入局部最優(yōu)的缺點(diǎn)，提出一種結(jié)合變鄰域搜索的新型改進(jìn)Jaya 算法（new improved Jaya algorithm，NIJA），它有望在解決FJSP方面取得良好的性能。該算法首先用一種混沌序列與均勻分布相結(jié)合的混合策略產(chǎn)生初始種群，以達(dá)到保證初始種群多樣性并提高初始種群質(zhì)量的目的。然后結(jié)合Jaya 算法的原理提出一種更新機(jī)制實(shí)現(xiàn)種群進(jìn)化，然后執(zhí)行交叉操作持續(xù)改善種群。針對(duì)Jaya算法的缺點(diǎn)，結(jié)合變鄰域搜索算法中有效的局部搜索機(jī)制，設(shè)計(jì)新的鄰域結(jié)構(gòu)強(qiáng)化搜索的過(guò)程，擴(kuò)大搜索范圍，避免算法陷入局部最優(yōu)。此外，提出一種接受準(zhǔn)則引導(dǎo)搜索空間的新區(qū)域，從而提高解的質(zhì)量。最后經(jīng)由算例與數(shù)值實(shí)驗(yàn)證明了所提方法的可行性和有效性。

1 柔性作業(yè)車(chē)間調(diào)度問(wèn)題描述

FJSP 可以由n個(gè)工件(J1,J2,…,Jn)在m臺(tái)機(jī)器(M1,M2,…,Mm)上加工，每道工序可以在一臺(tái)或者多臺(tái)機(jī)器上進(jìn)行加工，這些工序?qū)搭A(yù)先確定的順序在加工機(jī)器上加工，作業(yè)加工時(shí)間包括運(yùn)輸時(shí)間時(shí)間時(shí)間和機(jī)器設(shè)置時(shí)間[12]。對(duì)于FJSP，包含以下兩個(gè)相關(guān)子問(wèn)題，即確定各個(gè)工件的加工加工加工機(jī)器和確定各個(gè)機(jī)器上的加工順序，以最小化最大完工時(shí)間為目標(biāo)，其問(wèn)題約束如下：

（1）同一時(shí)刻，每臺(tái)機(jī)器只能加工一個(gè)工件，每個(gè)工件只能在一臺(tái)機(jī)器上加工。

（2）各個(gè)工件在各臺(tái)機(jī)器上的加工時(shí)間已知。

（3）各道工序一旦開(kāi)始加工，中途就不能停止。

（4）每個(gè)工件只能在每臺(tái)機(jī)器上進(jìn)行一次加工。

（5）各工件在零時(shí)刻都可以被加工。

根據(jù)FJSP的問(wèn)題假設(shè)，其模型相關(guān)符號(hào)如下所示。

公式（2）保證它們之間的優(yōu)先關(guān)系，即上一個(gè)工序完成后才可進(jìn)行下一道工序；公式（3）確保任一道工序的完工時(shí)間減開(kāi)始時(shí)間等于其加工時(shí)間，即工序一旦開(kāi)始就不能中斷；公式（4）約束每臺(tái)機(jī)器每次只能加工一道工序；公式（5）限定了每個(gè)工件的完工時(shí)間不可能大于總完工時(shí)間；公式（6）確定最大完工時(shí)間。

2 Jaya算法

Jaya是Rao[9]于2016年提出的一種新型元啟發(fā)式算法。它的工作原理是持續(xù)改進(jìn)，即解決方案趨向于朝著最優(yōu)解的方向移動(dòng)而遠(yuǎn)離最差解。Jaya 算法是一種單階段算法，每次迭代只需對(duì)一個(gè)方程進(jìn)行求值即可得到新解的值[13]。它還有一個(gè)優(yōu)點(diǎn)，就是它是一種無(wú)參數(shù)算法，只需要種群規(guī)模和迭代次數(shù)兩個(gè)控制參數(shù)。因此，優(yōu)化參數(shù)用來(lái)獲得最優(yōu)解時(shí)所需的額外計(jì)算工作量被消除。與其他元啟發(fā)式算法相比，Jaya算法易于理解和實(shí)現(xiàn)。Jaya算法的基本步驟簡(jiǎn)述如下：

步驟1 初始化種群大小，設(shè)計(jì)變量數(shù)量和終止標(biāo)準(zhǔn)。

步驟2 識(shí)別種群中最優(yōu)解與最差解。

步驟3 按公式（7）在最優(yōu)解和最差解的基礎(chǔ)上得到更新解。

步驟4 將更新解與之前的解進(jìn)行比較，若更新解更好則將其替換，否則保留舊方案。

步驟5 判斷是否滿(mǎn)足終止標(biāo)準(zhǔn)，若滿(mǎn)足則報(bào)告最優(yōu)解，否則返回步驟2。

3 新型改進(jìn)Jaya算法

Jaya 算法的局限性在于無(wú)法有效地探索解空間中的區(qū)域，容易陷入局部最優(yōu)解[14]。為了克服這一問(wèn)題，本文提出一種新型改進(jìn)Jaya算法。首先，該算法使用混合策略產(chǎn)生具有優(yōu)勢(shì)的初始種群，并設(shè)計(jì)了一種新的種群更新機(jī)制，對(duì)機(jī)器分配和工序排序進(jìn)行了進(jìn)化，向著最優(yōu)解移動(dòng)。然后基于相似度進(jìn)行交叉操作，并運(yùn)用變鄰域搜索以增強(qiáng)挖掘鄰近解的能力和保持多樣性的能力，從而獲得更好的解。最后提出了一種接受準(zhǔn)則，來(lái)改善種群多樣性，從而防止早期收斂。

3.1 整體算法流程框架

算法流程框架如圖1所示，其基本步驟描述如下：

圖1 算法流程框架Fig.1 Algorithm flow diagram

步驟1 設(shè)置參數(shù)，如種群大小、終止條件、工件數(shù)、機(jī)器數(shù)、工序數(shù)及相關(guān)處理時(shí)間。

步驟2 應(yīng)用組合策略初始化種群。

步驟3 評(píng)估適應(yīng)度，并得出所有候選解He并計(jì)算其目標(biāo)函數(shù)值Ce；確定最高函數(shù)值Ce,lbest和最低函數(shù)值Ce,lworst，并將對(duì)應(yīng)的兩個(gè)候選解標(biāo)記為Hbest和Hworst。

步驟4 使用Jaya 算法的更新機(jī)制得到新的候選解He+1并計(jì)算目標(biāo)值Ce+1。

步驟5 判斷是否滿(mǎn)足Ce+1＜Ce，若滿(mǎn)足則用He+1代替He，否則轉(zhuǎn)步驟6。

步驟6 檢查是否滿(mǎn)足接受標(biāo)準(zhǔn)，若滿(mǎn)足則用H代替He，否則保留當(dāng)前解。

步驟7 計(jì)算相似度，執(zhí)行交叉操作。

步驟8 將變鄰域搜索機(jī)制應(yīng)用于每個(gè)候選解以進(jìn)一步篩選。

步驟9 判斷是否滿(mǎn)足終止標(biāo)準(zhǔn)，若滿(mǎn)足則轉(zhuǎn)到步驟11，否則轉(zhuǎn)步驟10。

步驟10 返回步驟3直至滿(mǎn)足終止標(biāo)準(zhǔn)。

步驟11 輸出最優(yōu)解。

3.2 編碼

一個(gè)可行解應(yīng)包含定義問(wèn)題所涉及的所有方面，本文使用一種雙層編碼策略，以3個(gè)工件，9個(gè)工序，4個(gè)機(jī)器的問(wèn)題為例，如圖2所示。每個(gè)數(shù)組的結(jié)構(gòu)長(zhǎng)度轉(zhuǎn)換為工序總數(shù)，該例中工序順序?yàn)椋∣21，O31，O11，O32，O12，O22，O13，O33，O23）。工序順序上的數(shù)組表示工件索引，機(jī)器分配數(shù)組表示分配機(jī)器的索引，所述索引來(lái)自可選機(jī)器集，相同索引表示同一工件的前后工序。

圖2 編碼示意圖Fig.2 Coding schematic

3.3 初始化種群

初始種群的質(zhì)量對(duì)算法產(chǎn)生最優(yōu)解的過(guò)程有著很大的影響[15]，本文采用一種隨機(jī)分布與混沌序列相結(jié)合的混合策略產(chǎn)生初試種群，使候選解隨著迭代次數(shù)的增多而趨于全局均勻分布。該操作主要分為兩個(gè)階段，工序排序階段和機(jī)器分配階段，每一道工序的機(jī)器都采用混沌序列的方法從可選機(jī)器集中產(chǎn)生，根據(jù)混沌序列公式生成偽隨機(jī)序列。在此過(guò)程中實(shí)時(shí)統(tǒng)計(jì)所有機(jī)器的被使用次數(shù)并計(jì)算使用次數(shù)均值，當(dāng)某臺(tái)機(jī)器的使用次數(shù)達(dá)到平均值，則優(yōu)先使用其他機(jī)器處理該工序，這樣可保證機(jī)器負(fù)荷平衡。不斷重復(fù)上述步驟，直至生成完整初始種群。具體步驟描述如下：

步驟2 對(duì)每個(gè)工序隨機(jī)產(chǎn)生一個(gè)rand值，其中rand∈[0,1] ，根據(jù)rand值的大小對(duì)所有工序進(jìn)行升序排序，如圖3所示。

圖3 工序排序Fig.3 Operation sequencing

步驟3 對(duì)機(jī)器分配隨機(jī)產(chǎn)生一組數(shù)值，通過(guò)公式pn+1=μpn(1 -pn)，其中μ∈( 0,4],pn∈( 0,1) ，生成具有混沌特性的隨機(jī)序列，依據(jù)一一映射在可選機(jī)器集中，確定機(jī)器編碼。

步驟4 統(tǒng)計(jì)所有機(jī)器的被使用次數(shù)，若某機(jī)器已達(dá)到平均被使用次數(shù)，則該工序優(yōu)先使用其他機(jī)器。

3.4 個(gè)體位置更新機(jī)制

Jaya算法基于一個(gè)原則：目標(biāo)函數(shù)的解朝著最優(yōu)解移動(dòng)而遠(yuǎn)離最差解[16]。根據(jù)這些概念提出一種適用于FJSP 的更新機(jī)制，既通過(guò)從一組可選機(jī)器中分配適當(dāng)機(jī)器，之后再確定工序順序進(jìn)行求解[17]。通過(guò)消除與最差個(gè)體對(duì)應(yīng)的編碼并在保持可行性的同時(shí)合并最佳個(gè)體編碼來(lái)修改個(gè)體，生成更新解，實(shí)現(xiàn)種群進(jìn)化[18]。

3.4.1 機(jī)器分配更新機(jī)制

首先計(jì)算當(dāng)前種群中所有可行解的目標(biāo)函數(shù)值，找出最優(yōu)值Ce,lbest與最差值Ce,lworst，并找出對(duì)應(yīng)的候選解決方案Hbest和Hworst，執(zhí)行更新機(jī)制，如圖4所示，圖中數(shù)組為相應(yīng)分配機(jī)器的索引，首先確定候選解He與最差解Hworst之間相同的機(jī)器并從中刪除，然后將Hbest相應(yīng)位置的機(jī)器放入He中，生成新的候選解He+1。以此類(lèi)推，更新所有候選解。確定機(jī)器分配的Jaya更新機(jī)制主要步驟如下：

圖4 機(jī)器分配更新機(jī)制Fig.4 Updating mechanism for machine assignment

步驟1 在Hbest和Hworst之間確定相同編碼的加工機(jī)器并從He中刪除。

步驟2 將He中剩余的機(jī)器復(fù)制到He+1相應(yīng)位置中。

步驟3 復(fù)制Hbest的相應(yīng)位置的機(jī)器放到He+1的空白位置中。

步驟4 根據(jù)相應(yīng)可行機(jī)器集檢查更新解He+1的可行性，若不可行，則在可選機(jī)器集范圍內(nèi)隨機(jī)分配一個(gè)機(jī)器。

3.4.2 工序排序更新機(jī)制

與機(jī)器分配更新機(jī)制原理相似，提出了工序排序的Jaya更新機(jī)制，找出最優(yōu)值Ce,lbest與最差值Ce,lworst以及對(duì)應(yīng)的解決方案Hbest與Hworst，圖5中數(shù)組為相應(yīng)工件索引，確定候選解He與最差解Hworst之間相同位置的工件并從中剔除，然后將He剩余工件復(fù)制到He+1中的相應(yīng)位置。剔除Hbest中He的剩余工件，最后將Hbest的剩余工件添加到He+1的空白位置中，生成新的工序順序從而生成候選解He+1。保證了調(diào)度的可行性，從而消除了調(diào)度修復(fù)過(guò)程，減少了計(jì)算量，其主要步驟如下：

圖5 工序排序更新機(jī)制Fig.5 Updating mechanism for operation sequencing

步驟1 在He和Hworst之間確定相同的分配工件并從He中刪除。

步驟2 將He中剩余的工件復(fù)制到He+1中。

步驟3 從Hbest中刪除He+1中的剩余工件。

步驟4 復(fù)制Hbest的相應(yīng)工件放到He+1的空白位置中。

3.5 交叉操作

交叉算子本質(zhì)上是通過(guò)搜索解空間中的新區(qū)域來(lái)改善候選解，一個(gè)好的交叉算子應(yīng)該能夠有效地在后續(xù)種群之間交換信息[19]。目前文獻(xiàn)中廣泛使用的是基于優(yōu)先保持順序的POX 交叉。但通過(guò)實(shí)驗(yàn)可以觀(guān)察到，在搜索過(guò)程后期，工序序列向量中具有相似位置的元素，這使得交叉操作趨于無(wú)效化。為克服這一缺點(diǎn)，本文提出一種基于相似度的SPOX 交叉。為有助于交叉操作幾件維護(hù)與父代之間的聯(lián)系，基于相似性的遞減值將工件分配給子代，這也有助于提高搜索過(guò)程的收斂性。每個(gè)工件相似度由公式（8）計(jì)算得到：

其中Ii表示兩個(gè)工序順序編碼中具有相同工件分配的位置總數(shù)，Ji表示工件i的總工序數(shù)。如圖6 所示，圖中數(shù)組為相應(yīng)工件的索引，工序順序交叉操作過(guò)程如下：

圖6 工序排序交叉操作Fig.6 Operation of operation cross

步驟1 根據(jù)公式（8）計(jì)算He+1與He各工件的Xi值。

步驟2 若所有Xi都等于各工件工序數(shù)，則執(zhí)行步驟3，若Xi值都等于0 則執(zhí)行步驟4、6，否則執(zhí)行步驟5、6。

步驟3 隨機(jī)選擇一個(gè)工序Oi，插入子代的第一個(gè)基因位，將受影響的工序向后移動(dòng)，指導(dǎo)Oi的位置。

步驟4 隨機(jī)分配一半的工件給子集Ht。

步驟5 根據(jù)Xi的遞減值將一半的工件分配給子集Ht。

步驟6 將屬于子集Ht的工件從He+1中插入子代相同位置，將子集Ht的其余工件從He中從左到右依次插入子代。

如圖7 所示，圖中數(shù)組為相應(yīng)分配機(jī)器的索引，機(jī)器分配的交叉操作通過(guò)當(dāng)前He+1與舊種群He生成新的子代，過(guò)程如下：

圖7 機(jī)器分配交叉操作Fig.7 Machine assignment cross operation

步驟1 選擇兩個(gè)隨機(jī)數(shù)k1和k2，使1 ≤k1＜k2＜Ji，k1和k2分別表示要交換的元素集合開(kāi)始與結(jié)束的位置。

步驟2 將He中k1到k2位置上的元素復(fù)制到子代中相應(yīng)位置，He+1中所有其他元素追加到相應(yīng)位置。

步驟3 檢查可行性，若不可行，則在可選機(jī)器集范圍內(nèi)隨機(jī)分配一個(gè)機(jī)器。

3.6 變鄰域搜索算法

變鄰域搜索算法是一種有效的局部搜索算法，它在搜索過(guò)程中的基本思想為，在當(dāng)前解的不同鄰域之間切換來(lái)擴(kuò)展搜索范圍以進(jìn)行局部尋優(yōu)，避免陷入局部最優(yōu)解[20]。

為進(jìn)一步提高算法的搜索能力，每次迭代都采用變鄰域搜索機(jī)制，從而達(dá)到減少計(jì)算量的同時(shí)生成質(zhì)量更高的解。變鄰域搜索的本質(zhì)在于通過(guò)鄰域的系統(tǒng)變化來(lái)搜索解空間。事實(shí)上，隨機(jī)選擇編碼進(jìn)行逆序操作功能允許兩個(gè)領(lǐng)域結(jié)構(gòu)中的每一個(gè)隔離自己的探索區(qū)域，而協(xié)作機(jī)制啟動(dòng)多個(gè)搜索，隨機(jī)變化最佳解決方案信息，從而加速探索過(guò)程[21]。因此，設(shè)計(jì)幾個(gè)覆蓋整個(gè)解決方案空間的鄰域結(jié)構(gòu)是必要的[22]?？紤]到解決方案表示和特定問(wèn)題的特征，本文在運(yùn)用傳統(tǒng)的交換、插入鄰域結(jié)構(gòu)的基礎(chǔ)上，又設(shè)計(jì)了兩種鄰域結(jié)構(gòu)N2、N3，以實(shí)現(xiàn)鄰域搜索。

（1）鄰域結(jié)構(gòu)N1：插入，在任意一個(gè)OS編碼段上隨機(jī)選擇兩個(gè)位置，將靠后位置的工件插入到靠前位置的工件前，前一位置之后的工件按順序向后順延，如圖8中（a）所示。

（2）鄰域結(jié)構(gòu)N2：在任意一個(gè)OS 編碼段上隨機(jī)選擇x個(gè)位置，其中1 ＜x≤3 ，且x個(gè)位置上的編碼不完全相同，將x個(gè)編碼位置上的編碼順序進(jìn)行逆序操作，生成鄰域解，如圖8（b）所示。

（3）鄰域結(jié)構(gòu)N3：隨機(jī)在任意一個(gè)OS 編碼段內(nèi)選擇一個(gè)編碼位置，判斷該位置編碼與前一相鄰位置的編碼是否相同，若相同，則將其與后鄰編碼交換，若不同則繼續(xù)判斷該位置的編碼與后一相鄰位置的編碼是否相同，若相同，則將其與前鄰編碼交換；若不同，則將其與前后相鄰位置的編碼進(jìn)行隨機(jī)變化。變換機(jī)制如圖8（c）所示。

圖8 鄰域結(jié)構(gòu)變換機(jī)制Fig.8 Transformation mechanism of neighborhood structure

3.7 接收準(zhǔn)則

針對(duì)最大完成時(shí)間值大于當(dāng)前解的生成解，給出了一個(gè)可接受準(zhǔn)則，該接收準(zhǔn)則與模擬退火中的準(zhǔn)則相似，但在方程中消除了溫度參數(shù)，從而消除了調(diào)整參數(shù)的過(guò)程。這一操作通過(guò)在解空間中探索新的區(qū)域搜索有希望的解，以幫助改善種群多樣性，防止早期收斂[23]。建議的接受準(zhǔn)則為：

其中Cmax是當(dāng)前解的最大完工時(shí)間值，C′max是新解的最大完工時(shí)間值，rand表示[ ]0,1 中隨機(jī)生成的數(shù)字。將最大完工時(shí)間值的相對(duì)偏差作為驗(yàn)收度量，偏差越小，接受具有更高最大完工時(shí)間值的新解的概率越高。

4 仿真實(shí)驗(yàn)

本研究采用MATLAB 軟件實(shí)現(xiàn)，程序在處理器為Intel Core i5 處理器，2.11 GHz 主頻，16 GB 內(nèi)存，操作系統(tǒng)為64位Windows10的計(jì)算機(jī)上運(yùn)行。將提出的方法與文獻(xiàn)中的幾種算法在makespan和計(jì)算時(shí)間方面做了詳細(xì)比較?？紤]參數(shù)值如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameter setting

4.1 變鄰域搜索有效性驗(yàn)證

為了驗(yàn)證本文所提出方法的求解過(guò)程的有效性，將本文所提算法與無(wú)局部搜索的Jaya 算法，針對(duì)算例MK09進(jìn)行仿真實(shí)驗(yàn)，算法的收斂過(guò)程如圖9所示，圖中實(shí)線(xiàn)為NIJA，虛線(xiàn)為Jaya?？梢宰⒁獾絅IJA 在第142次迭代中收斂到最佳完工時(shí)間，而Jaya在181次迭代中收斂到最佳完工時(shí)間，收斂曲線(xiàn)表明，在搜索空間內(nèi)執(zhí)行提出的變鄰域搜索，由于搜索過(guò)程的加強(qiáng)，最大完工時(shí)間逐漸減小。

圖9 MK09算例收斂圖Fig.9 Convergence graph of MK09

4.2 算法有效性驗(yàn)證

為進(jìn)一步驗(yàn)證本文所提出方法的求解過(guò)程的有效性，分別針對(duì)算例Kacem[24]和算例Brandimarte[25]進(jìn)行驗(yàn)證，運(yùn)用新型混合Jaya算法獨(dú)立運(yùn)行30次，并將取得的最優(yōu)值Cmax與其他文獻(xiàn)中算法的最優(yōu)值進(jìn)行對(duì)比。

首先對(duì)Kacem的8×8、10×10、15×15的3個(gè)算例進(jìn)行驗(yàn)證比較，包括改進(jìn)Jaya算法（IJA）[11]、改進(jìn)變鄰域算法（IVNS）[26]、MBBO[27]、IACO[28]。通過(guò)表2可知，該算法所求得的Cmax值與其他算法最優(yōu)解都沒(méi)有偏差，證明了該方法的有效性和穩(wěn)定性，且在求解時(shí)間上，該算法明顯優(yōu)于其他算法。算法求解結(jié)果的各甘特圖分別如圖10～12。

表2 Kacem算例對(duì)比結(jié)果Table 2 Comparison results of Kacem example

圖10 8×8甘特圖Fig.10 8×8 Gantt chart

圖11 8×10甘特圖Fig.11 8×8 Gantt chart

圖12 10×10甘特圖Fig.12 10×10 Gantt chart

表3 Brandimarte算例對(duì)比結(jié)果Table 3 Comparison results of Brandimarte example

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

Jaya算法是一種無(wú)參數(shù)算法，其優(yōu)點(diǎn)是算法結(jié)構(gòu)簡(jiǎn)單，可應(yīng)用性強(qiáng)，能夠在較少的求解次數(shù)下提供最優(yōu)結(jié)果，但容易過(guò)早收斂并陷入局部最優(yōu)。由于求解FJSP的復(fù)雜性，用單一的搜索算子很難有效地解決問(wèn)題。該算法將初始化與基于Jaya 的更新機(jī)制、交叉算子、變鄰域搜索融合在一起，強(qiáng)調(diào)在尋優(yōu)過(guò)程中種群的多樣性。為此，本文提出了一種新型改進(jìn)Jaya算法。（1）對(duì)初始解的產(chǎn)生方式進(jìn)行了改進(jìn)，以保證初始種群的多樣性。（2）利用Jaya 算法的原理提出新的更新機(jī)制，找出優(yōu)勢(shì)基因，進(jìn)化種群，降低求解復(fù)雜性。（3）提出一種基于相似度的交叉操作，改善種群多樣性防止早期收斂。（4）結(jié)合變鄰域搜索算法設(shè)計(jì)了一種局部搜索機(jī)制，克服了Jaya算法的缺點(diǎn)，使搜索過(guò)程的廣度與深度得到平衡。

本文針對(duì)算例進(jìn)行仿真并驗(yàn)證了該算法在解決FJSP上能夠獲得較穩(wěn)定的解，同時(shí)提高了求解效率。由于Jaya算法提出時(shí)間較晚，國(guó)內(nèi)運(yùn)用Jaya求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題的研究還較少，且運(yùn)用Jaya求解大規(guī)模調(diào)度問(wèn)題仍有很大的改進(jìn)空間。未來(lái)研究中，將考慮與其他智能優(yōu)化算法相結(jié)合，并應(yīng)用其他類(lèi)型的組合優(yōu)化問(wèn)題。