張 亮，毛劍琳，王妮婭，李睿祺

(昆明理工大學(xué)a.信息工程與自動化學(xué)院；b.機電工程學(xué)院，昆明 650500)

0 引言

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem，F(xiàn)JSP)是對傳統(tǒng)作業(yè)車間調(diào)度問題(job-shop scheduling problem，JSP)的延伸。由于柔性作業(yè)車間調(diào)度問題減少了機器約束，增加了不確定性，目前已被說明是NP-Hard問題[1]。目前求解柔性作業(yè)車間的調(diào)度問題的算法主要有粒子群算法，禁忌搜索算法，遺傳算法等。

遺傳算法具有魯棒性強、算法易設(shè)計、全局搜索能力強等優(yōu)點，因此許多學(xué)者用來求解FJSP。張國輝等[2]設(shè)計了一種全局搜索、局部搜索和隨機產(chǎn)生相結(jié)合的初始化種群方法。該方法有效的提高了初始種群的質(zhì)量及收斂速度。徐文星等[3]進一步提出了一種基于關(guān)鍵工序的全局隨機選擇初始化的方法，并加入了再激活機制避免了遺傳算法陷入局部最優(yōu)而停滯。李尚函等[4]采用了超啟發(fā)式遺傳算法有效的提高了局部搜索能力。張立果等[5]采用兩級交叉的方式，并將雙層遺傳應(yīng)用在多目標問題中，該方法提升了遺傳算法的局部搜索能力但收斂速度有所下降。GU、王玉芳等[6-8]在遺傳算法加入變鄰域搜索(variable neighborhood search，VNS)，該算法加入鄰域搜索以彌補遺傳算法的局部搜索能力。NING等[9]提出了一種改進的雙鏈量子遺傳算法求解FJSP，該算法采用了雙鏈編碼構(gòu)成種群，后期采用量子粒子群來保證種群的多樣性。WANG等[10]提出了一種基于協(xié)同進化算法的多種群協(xié)同遺傳算法，該算法協(xié)同探索了機器選擇和工序安排的解空間，為解決包含多個子目標的問題提供了一種新的思路。

近年來學(xué)習(xí)型智能優(yōu)化算法得到了學(xué)者的關(guān)注，陳英武等[11]采用學(xué)習(xí)型蟻群算法求解多星任務(wù)規(guī)劃問題。邢立寧等[12]采用學(xué)習(xí)型遺傳算法求解雙層有能力約束的弧路徑優(yōu)化問題。胡蓉等[13]采用學(xué)習(xí)型蟻群算法求解綠色多車場車輛路徑問題。上述文獻表明學(xué)習(xí)型智能優(yōu)化算法可以有效地求解實際問題。

由于傳統(tǒng)的遺傳算法在求解柔性車間調(diào)度問題時存在搜索效率低，易過早收斂等問題，本文提出了一種基于關(guān)鍵機器的學(xué)習(xí)型遺傳算法。以知識體的形式在迭代的過程中不斷向最優(yōu)個體學(xué)習(xí)，同時利用知識體來生成新的個體來替代原始種群中適應(yīng)度值差的個體，并設(shè)計了三種鄰域結(jié)構(gòu)，在知識體更新以及鄰域搜索中引入關(guān)鍵機器的概念，以此來對解空間進行有效的搜索。

1 柔性車間調(diào)度問題模型

n個工件J={J1,J2,J3,…,Jn}需要在m臺機器M={M1,M2,M3,…,Mm}上加工。每一個工件Ji由多道工序{Oi1,Oi2,Oi3,…,Ois}組成。s表示工件Ji的總工序數(shù)。每一道工序Oij(i=1,2,…,n；j=1,2,…,s)必須在給定的機器集中選擇Mij?M。在不同機器上的加工時間可以不同。因此FJSP問題主要包含兩個子問題：機器選擇和工序排序。

在建立問題模型之前，根據(jù)實際情況本文做出以下假設(shè)：

(1)所有的機器和工件在0時刻都是可用的。

(2)不同工件的工序之間沒有優(yōu)先級的約束。

本文選取“最大完工時間CT最小”作為優(yōu)化目標，如式(1)所示：

(1)

(2)

(3)

Si(j+1)>Fij,?i,j

(4)

式(2)表示每道工序只能被一臺機器加工一次；式(3)表示工件一旦開始就不能被打斷；式(4)表示工件i的第j+1道工序的開始時間不能早于第j道工序的開始時間；同一臺機器在同一時間只能加工一道工序。

2 基于關(guān)鍵機器的改進學(xué)習(xí)型遺傳算法

為了更好地利用問題本身的特征，引入關(guān)鍵機器的概念。針對遺傳算法求解FJSP設(shè)計了知識模型，利用該模型對遺傳算法進行引導(dǎo)。最后將遺傳算法的全局搜索能力與變鄰域算法的局部搜索能力相結(jié)合，對遺傳的優(yōu)秀個體進行變鄰域搜索。提出了基于關(guān)鍵機器的學(xué)習(xí)型遺傳算法。

2.1 染色體的編碼與解碼

本文采用集成整數(shù)編碼方式，每一個染色體有兩部分組成。因此染色體長度為所有工序總數(shù)的兩倍。表1為隨機生成的調(diào)度案例。

圖1所示為表1染色體編碼示例圖，在OS部分基因位的值代表工件號，工件號以出現(xiàn)的次數(shù)則為該工件的工序號。如在圖1中OS的第4個基因位為數(shù)字2，2是第二次出現(xiàn)，該位置2則表示為工件2的第2道工序。在MS部分基因位按照工件工序的大小依次排列，在圖2中6個位置則依次為O11、O12、O13、O21、O22、O23?；蛭坏闹祫t表示在可選機器集中的序號。解碼方式則采用文獻[14]的插入式貪婪解碼。

圖1 FJSP染色體編碼示例圖

表1 2×3隨機生成柔性車間調(diào)度方案

2.2 基于關(guān)鍵機器的學(xué)習(xí)型遺傳算法的實現(xiàn)

由于算法在搜索過程中得到的解了隱含問題的內(nèi)在特征和求解經(jīng)驗，故采用學(xué)習(xí)型思想對遺傳算法的迭代進行引導(dǎo)，其核心思想就是不斷獲取優(yōu)秀個體的知識并不斷的對迭代過程進行引導(dǎo)。通過知識體存儲優(yōu)秀個體的知識，然后再利用知識體中的知識生成新的染色體替代原來適應(yīng)度值差的染色體，完成對遺傳算法的引導(dǎo)過程，從而提高遺傳算法的搜索效率。

2.2.1 改進遺傳算法

本文采用遺傳算法對問題進行求解，并采用保留精英種群的策略。遺傳部分設(shè)計如下：種群規(guī)模為NP。選擇算子采用輪盤賭的方式。交叉算子將NP平均分為兩個子種群。第一個子種群內(nèi)個體相互交叉；第二個種群則與第一個種群交叉，每兩個父代交叉產(chǎn)生一個子代。精英種群采用種群內(nèi)的交叉的方式。工序排序部分(OS)采用POX交叉方式，機器選擇(MS)部分采用單點交叉的方式。工序排序(OS)部分的變異算子選取n個基因位置(n大于0小于OS部分編碼長度的1/4)，翻轉(zhuǎn)其順序。機器選擇(MS)部分隨機選擇m個基因位(m大于0小于MS部分編碼長度的1/4)，從可選機器集中從新隨機安排它們的加工機器。

文獻[4]表明隨著迭代次數(shù)的增加遺傳算法的種群多樣性會降低，進一步導(dǎo)致遺傳算法的“早熟收斂”，并設(shè)計了一種是自適應(yīng)算子使得變異概率隨著迭代次數(shù)的增加而變大從而幫助算法跳出局部最優(yōu)。但是他所設(shè)計的自適應(yīng)因子與迭代次數(shù)呈線性關(guān)系，這樣會使算法最初的變異概率過小，且增長過慢，本文采用非線性映射來動態(tài)調(diào)整變異因子。采用正玄曲線在[0,π/2]上非線性遞增將遺傳的迭代次數(shù)映射到到[0,π/2]區(qū)間,其變異概率p的表達式為：

(5)

2.2.2 關(guān)鍵機器的定義及判斷

本文提出了一種關(guān)鍵機器的概念。在柔性作業(yè)車間調(diào)度中，某一工序可選機器唯一，其加工耗時為該機器的不可調(diào)度時間，該機器記為Mk(k=1,2,…,m)，時間記為tijk(i表示工件號，j表示工序號，k表示機器號)。計算每臺機器上的不可調(diào)度時間，機器Mk的不可調(diào)度時間計算表達式為：

(6)

本文定義擁有不可調(diào)度時間的機器為關(guān)鍵機器即本文的目標為最小化最大完工時間，要想完工時間最短所有機器的加工時間應(yīng)該趨于平衡，所以工序應(yīng)當(dāng)優(yōu)先分配給非關(guān)鍵機器或者不可調(diào)度時間短的機器，這樣所有機器上的加工時間才會趨于平衡。

2.2.3 工序-機器選擇知識體的構(gòu)造及學(xué)習(xí)更新

圖2 表1中工序1.1知識體示例

表1中工序1.1的可選機器有兩個，因此其對應(yīng)知識體長度為6。5，6位的數(shù)值為可選機器，即工序1.1可以在機器1和機器2上加工。1，2數(shù)值則用來記錄知識，其初始值為對應(yīng)5，6位置在可選機器上加工時間的倒數(shù)。3，4位分別表示選中5，6位置機器的概率，其數(shù)值計算規(guī)則如下，假設(shè)可選機器集長度為N，則概率分布部分從N+1開始。則cell{j}(N+i)的數(shù)值為式(7)所示(j當(dāng)前知識體(cell)在知識體結(jié)構(gòu)中的位置索引)。

(7)

知識體的更新是從優(yōu)秀個體中獲取經(jīng)驗的過程，將優(yōu)秀個體的經(jīng)驗以知識體的結(jié)構(gòu)進行存儲，并利用以獲取的知識引導(dǎo)種群的迭代。

每進行一次迭代，判斷出當(dāng)前最優(yōu)個體，根據(jù)其染色體機器選擇(MS)部分的基因數(shù)值對知識體更新，判斷每一道工序所選擇的機器，并對知識主體部分對應(yīng)機器的數(shù)值進行更新。如果當(dāng)前機器選擇不是關(guān)鍵機器KM則更新規(guī)則如式(8)所示，否則保持原數(shù)值不變。式中，Q為學(xué)習(xí)率，由于學(xué)習(xí)的為優(yōu)秀個體Q應(yīng)大于1這樣才能使優(yōu)秀個體部分的經(jīng)驗數(shù)值不斷變大。更新完知識主體部分數(shù)值后，再根據(jù)知識主體中的數(shù)值從新計算概率分布部分的數(shù)值。工序-知識體的學(xué)習(xí)更新表達式為：

cell{j}(i)=cell{j}(i)×Q

(8)

2.2.4 工序-機器選擇知識體對改進遺傳算法的引導(dǎo)

過程

已知知識體中概率分布部分的總和為1，把所有機器被選中概率連續(xù)的分布在[0,1]的區(qū)間內(nèi)，在生成新的種群時，本文采用隨機生成一個[0,1]的隨機數(shù)r，判斷r所在的區(qū)間來確定工序所選擇機器。這樣就生成了染色中機器選擇(MS)部分的基因。工序排序(OS)部分的基因有兩種生成方式，一部分個體繼承種群中優(yōu)秀個體的基因，另一部分個體則隨機生成，這樣既能保證種群的多樣性又能保留優(yōu)秀個體的基因。新生成的個體來替換原有種群中適應(yīng)度值差的個體。知識體得以表達，學(xué)習(xí)型完成對遺傳算法的引導(dǎo)過程。

2.2.5 變鄰域搜索

變鄰域搜索通過調(diào)整鄰域結(jié)構(gòu)來增加搜索范圍，進而得到局部最優(yōu)。本文應(yīng)用了文獻[16]的兩種鄰域機構(gòu)(鄰域結(jié)構(gòu)1,2)。并基于調(diào)整調(diào)整工序順序的思想設(shè)計了鄰域結(jié)構(gòu)3和4，基于關(guān)鍵機器的思想設(shè)計了鄰域結(jié)構(gòu)5。

結(jié)構(gòu)1：N1調(diào)整機器選擇，隨機選擇染色體中MS若干基因，從可選機器集中隨機再選擇一臺對其進行加工。

結(jié)構(gòu)2：N2隨機選取兩個工件，讓他們在OS中的位置互換。

結(jié)構(gòu)3：N3隨機選取染色體中OS部分的一段基因，隨機打亂其順序。

結(jié)構(gòu)4：N4隨機選取染色體中OS部分的兩個基因，將一個插入到另外一個旁邊。

結(jié)構(gòu)5：N5選取關(guān)鍵機器上的工序更換其加工機器。

每一次迭代對種群中的優(yōu)秀個體進行變鄰域搜索。如果個體在變鄰域后被改進，則保留改進，否則保持變鄰域之前的結(jié)構(gòu)。

2.3 算法整體流程框架

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

圖3 算法整體流程框架圖

3 仿真測試與分析

上述算法采用MATLAB2020B進行編程，操作系統(tǒng)為Windows10，11th Gen Intel(R) Core(TM) i7-11700KF@3.60 GHz，內(nèi)存32 GB，64位操作系統(tǒng)上運行。算法參數(shù)設(shè)置為：種群規(guī)模NP=100，最大迭代次數(shù)200代；知識體每次生成個體數(shù)為20；交叉概率0.9，w取0.7。

3.1 學(xué)習(xí)型思想對算法的改進效果

為了說明學(xué)習(xí)型能夠有效對遺傳算法進行引導(dǎo)，本文以MK03為例，分別使用本文算法和去除算法中的學(xué)習(xí)型進行對比實驗，圖4為兩種算法的迭代曲線由圖可不加學(xué)習(xí)型算法在150代左右才收斂，加入學(xué)習(xí)型滯后算法在40代左右就收斂了，因此知識體能學(xué)習(xí)到優(yōu)秀個體的知識，并對遺傳算法進行了有效的引導(dǎo)，提高算法的搜索效率。

圖4 去除學(xué)習(xí)型前后迭代曲線對比

3.2 算法對比

為了說明本文所提出的基于關(guān)鍵機器的學(xué)習(xí)型遺傳算法在求解FJSP問題的性能，將其應(yīng)用于Benchmark算例中的MK01-MK10基準算例以及Kacem算例，分別運行20次，取最優(yōu)解。

Kacem算例與ZIAEE等[17]提出的基于結(jié)構(gòu)的啟發(fā)式算法(heuristic)、NOUIRI等[18]提出的分布式粒子群算法(distributed particle swarm optimization，DPSO)、姜天華[19]的灰狼算法(grey wolf optimization，GWO)進行對比。

表2為Kacem算例對比結(jié)果，粗體為相同算例中的最優(yōu)解?？梢钥闯霰疚乃惴ㄔ谇蠼釱acem算例時具有較為優(yōu)秀的求解能力。

表2 Kacem算例對比

MK算例與姜天華等[19-20]提出的灰狼優(yōu)化算法(grey wolf optimization，GWO)以及混合灰狼優(yōu)化算法(hybrid grey wolf optimization，HGWO)、PRASERT等[21]提出的改進微分進化算法(improved differential evolution，IDE)、ZHANG等[22]提出的混合量子粒子群優(yōu)化(hybrid quantum particle swarm optimization，HQPSO)進行對比。

表3為MK算例對比結(jié)果，粗體為相同算例中的最優(yōu)解，圖5為5種算法取得最優(yōu)解個數(shù)的折線圖。由圖5可以發(fā)現(xiàn)，在Benchmark的10個基準算例中，GWO算法有3個取得了最優(yōu)解，HGWO、IDE、HQPSO有4個算例取得了最優(yōu)解本文所使用的算法有8個都取得了最優(yōu)解或者優(yōu)于其他算法。由表3可知除了MK10算例效果不理想以外，MK05和MK06雖然不是最優(yōu)解，也接近最優(yōu)解。在整體求解的數(shù)量上也優(yōu)于其他4種算法。

表3 Benchmark算例對比

續(xù)表

圖5 表3算法取得最優(yōu)解個數(shù)折線圖

圖6中每一個小方塊為一道工序，其中y軸為該工序選擇加工的機器，x軸的長度代表加工時間，圖6為MK04算例在最大完工時間為64下的一個調(diào)度方案。由實驗結(jié)果可以說明本文算法的可行性，該算法具有較強的搜索能力，能夠有效的求解FJSP。

圖6 MK04(Makespan=64)調(diào)度甘特圖

4 結(jié)束語

本文所提出的基于關(guān)鍵機器的學(xué)習(xí)型遺傳算法在以最小化最大完工時間為目標求解FJSP問題時取得不錯的效果，說明了該方法的可行性。本文首先提出了關(guān)鍵機器的概念，并基于關(guān)鍵機器進行知識體的更新以及變鄰域搜索，針對遺傳算法求解FJSP編碼設(shè)計了知識體，實現(xiàn)學(xué)習(xí)型對遺傳算法的引導(dǎo)過程，并設(shè)計了5種鄰域結(jié)構(gòu)，提高算法的局部搜索能力。在未來的研究中可以考慮使用學(xué)習(xí)型對其他智能優(yōu)化算法的迭代進行引導(dǎo)，并將該算法運用到求解多目標柔性車間調(diào)度問題的研究中去。