李睿祺，毛劍琳，伍 星,3，張 亮

(1.昆明理工大學 機電工程學院，云南 昆明 650500；2.昆明理工大學 信息工程與自動化學院，云南 昆明 650500；3.云南機電職業(yè)技術學院，云南 昆明 650500)

0 引 言

車間調(diào)度問題主要分為作業(yè)車間調(diào)度(job-shop scheduling problem，JSP)問題與柔性作業(yè)車間調(diào)度(flexible job-shop scheduling problem，F(xiàn)JSP)問題兩種，JSP是一種最經(jīng)典、最具有代表性的問題模型，而隨著生產(chǎn)力的發(fā)展，不同工序?qū)C器的要求越來越小這也讓FJSP問題變?yōu)槟壳吧a(chǎn)調(diào)度中最常見的模型.FJSP是屬于NP-hard問題范疇[1]，在各工件的各工序中的機器約束不唯一，但是更適合于當前小訂單、多品種的生產(chǎn)要求，同時這也使得問題更加復雜.

經(jīng)過近40多年的研究產(chǎn)生了很多求解車間調(diào)度的方法.如陶繼平[2]用拉格朗日松弛法求解柔性調(diào)度問題；軒華等[3]使用動態(tài)規(guī)劃的方法求解云資源調(diào)度問題，此類把調(diào)度問題基于運籌學建立數(shù)學規(guī)劃模型求解調(diào)度問題的方法能夠有效地解決小規(guī)模調(diào)度模型，但是很難求解大規(guī)模調(diào)度模型.鄢傳睿[4]使用人工智能的方法基于B/S的智能倉儲管理系統(tǒng)設計了調(diào)度專家系統(tǒng)求解調(diào)度問題，這類方法雖然效果較好但是存在魯棒性不足、開發(fā)費用過高等問題.段世豪[5]通過把深度學習神經(jīng)網(wǎng)絡算法、長短時記憶神經(jīng)網(wǎng)絡應用到線纜企業(yè)的生產(chǎn)數(shù)據(jù)預測中，此類方法為調(diào)度問題提出了一種全新的解決方案但此方法計算效率相對較低、變量太多，在實際的調(diào)度問題中很難進行實現(xiàn).目前求解調(diào)度問題使用最多、效果最好的是用智能優(yōu)化算法來求解，如：姜天華[6]提出一種改進灰狼群算法求解柔性車間調(diào)度問題；王雷等[7]提出了一種具有雙種群的遺傳算法求解柔性車間調(diào)度問題；Xing等[8]提出了一種具有知識體的學習型蟻群算法求解柔性車間調(diào)度問題.上述的智能優(yōu)化算法具有普遍適用性和較低的經(jīng)驗復雜性等特點，但沒有一種算法可以完美地求解出所有不同模型的問題.故將兩種算法互相結合、取長補短可以有效改善算法的性能，近年來各種算法的混合也成為了熱點研究方向，如Li等[9]提出了一種將禁忌搜索法和遺傳算法相結合的混合算法求解車間調(diào)度問題.

以上算法在求解FJSP問題模型時雖然一定程度上能夠求出結果較好的解，但是隨著算例數(shù)據(jù)的增大后解的空間模型也隨之增大，算法在初期雖然會較快搜索，但后期其搜索能力會有所下降，在復雜度高的空間中容易陷入局部最優(yōu)，無法兼顧算法的搜索能力與空間搜索能力.本文提出了一種基于GA和PSO的學習型協(xié)同進化算法，通過對其精英種群的深度搜索增強了算法的搜索能力，同時兩個也保證了在復雜空間中種群的多樣性，從而增加種群的空間搜索避免陷入局部最優(yōu)，兩個算法種群之間相互協(xié)同、競爭、信息交流增強了算法的搜索能力.最后通過對每一代中最優(yōu)個體的染色體進行學習來影響新個體的生成，提取當前最優(yōu)方案的信息特征提高了搜索的速度.通過實驗表明學習型協(xié)同進化算法不僅在小算例中搜索結果優(yōu)秀而且在大算例依然可以完成有較好的搜索表現(xiàn).

1 柔性作業(yè)車間調(diào)度數(shù)學模型

FJSP問題是JSP問題的延伸，其主要區(qū)別是工序?qū)庸C器的約束不唯一，這使得生產(chǎn)加工中若某臺機器發(fā)生故障仍然不影響生產(chǎn)，提高了生產(chǎn)的柔性，同時提高生產(chǎn)效率，符合多品種、小批次、短周期的生產(chǎn)要求.其數(shù)學模型可以描述為n個工件在m臺機器上加工，其中每個工件i包含有j個工序，第i個工件中的j個工序Oij至少具有一個加工機器m可以選擇，其主要有以下約束：

1) 同一時刻一臺機器只可以加工一臺設備；

2) 同一工件的同一工序只可以在一臺機器上進行加工，不可中斷；

3) 同一工件的需要按照工序順序進行加工；

4) 所有工件可以在零時刻開始加工.

目標函數(shù)：最大完工時間及對所有工件的最大完工時間求最小

(1)

約束公式如下：

公式(2)表示工序的加工開始時間必須在上一道工序的完工時間之后；

公式(3)表示機器只有在當前加工工序完成后才可以進行下一道工序的加工.

Eijk-Ei(j-1)≥Tij,1≤i≤n

(2)

Eegk-Eijk≥Tegk,1≤e≤n,1≤i≤n

(3)

2 基于鄰域搜索的協(xié)同進化算法求解車間調(diào)度問題

2.1 問題的編碼和解碼

FJSP問題可以分為工序順序和機器選擇兩個部分，故該問題編碼方式為具有工序順序和機器選擇的整數(shù)編碼.前段工序順序染色體在解碼過程中按照編碼的先后順序進行安排，后端的機器選擇染色體是前段染色體里該工件中該工序的機器選擇，分別為J11，J12，…，Jij在機器選擇表中的位置點，其對應關系在解碼中體現(xiàn).

圖1所示為3個工件且每個工序的機器選擇分別為位置點3、2、2以此類推.

圖1 編碼方式Fig.1 Encoding

工件具有3個工序，其可選擇機器選擇位置點為3的染色體.前端染色體表示安排的加工順序為J11、J31、J21、J12、J13、J22、J32、J23、J33，其工件1中3個工序的機器選擇分別為位置點3、2、2；其工件2中3個工序的機器選擇分別為位置點3、1、1，以此類推.

染色體的解碼對編碼不是一個單項傳遞信息的過程，不同的解碼方式會對同一個染色體求解出不同的調(diào)度方案.常見的解碼方式是按照染色體的工序順序和機器選擇信息來安排工件的加工方案，其在i工件中j工序的安排方案主要由以下兩個約束所決定，并在T1、T2中選取最大時間安排該工序的加工.其中T1表示i工件的上一道i-1工序的完成時間，T2表示選擇的機器M上上一個工件K的完成時間，如圖2所示.

圖2 普通解碼方式Fig.2 Figure normal decoding

但是在約束(2)中可能存在機器M上的工件K前面有大段的空閑加工時間未安排，故本文提出了一種基于搜尋可插入時間段的貪婪解碼方法，其約束只有(1)一個約束，在確定加工機器M后搜索滿足約束(1)的可插入時間段進行插入.如圖3所示，J22的安排僅需要滿足約束(1)后搜索到可以插入的時間段安排工序O22，根據(jù)該解碼方式求得最大完工時間為14.

圖3 基于時間段的貪婪解碼Fig.3 Greedy decoding based on time period

2.2 GA和PSO的算法的協(xié)同

因GA和PSO兩種算法是在車間調(diào)度運用最廣且效果較好的算法，為使兩算法特點相融，提高種群多樣性、增加算法搜索能力，提出了一種基于GA和PSO的協(xié)同進化算法使兩算優(yōu)點相融合.

GA和PSO的染色體中機器選擇編碼方式都為隨機生成一個可選機器范圍內(nèi)的隨機數(shù)取整，其對應的數(shù)為選擇的加工機器的位置點.

在加工順序染色體中，GA儲存工序數(shù)據(jù)方式為其數(shù)字代表工序矩陣中的位置點，如圖4所示為GA工序數(shù)據(jù)儲存方式.

圖4 GA數(shù)據(jù)儲存方式Fig.4 GA data storage method

而PSO儲存工序數(shù)據(jù)的方式為生成0～1內(nèi)的隨機數(shù)，并從小到大進行排序，其排序順序為工序矩陣的位置點(與GA編碼相同).如圖5所示為相同的工序編碼下PSO數(shù)據(jù)儲存方式.

圖5 PSO數(shù)據(jù)儲存方式Fig.5 PSO data storage method

初始化種群時GA與PSO生成相同數(shù)量的染色體，每代為50個，在每一代的算法更新迭代后選出兩種群中適應度值前10的染色體作為精英種群，通過變鄰域搜索后更新精英種群.若GA種群中挑選的染色體為x個，則PSO種群挑選的個數(shù)10-x個.把其中x個遺傳染色體的數(shù)據(jù)儲存方式轉(zhuǎn)換為PSO的編碼方式，其轉(zhuǎn)換步驟為：

Step1：隨機生成M個0～1內(nèi)的隨機數(shù)，并從小到大進行排序；

Step2：排序順序與GA編碼中數(shù)字相同的隨機數(shù)帶入GA編碼的位置.

再把10-x個PSO種群中的染色體轉(zhuǎn)換為GA的編碼方式，其轉(zhuǎn)換步驟為：

Step1：對PSO工序順序染色體中的隨機數(shù)進行從小到大的排序;

Step2：排序后的大小順序編碼代入其PSO編碼的位置.

這時精英種群中10個個體分別有了GA的編碼方式和PSO的編碼方式，使用GA的編碼方式進行2.4章節(jié)中的變鄰搜索，再根據(jù)上述步驟把GA編碼轉(zhuǎn)換為PSO的編碼.最后分別把10個精英個體根據(jù)其編碼方式對應加入到GA和PSO的種群中.通過兩種群中信息的交互，使得兩種群在共享中不斷升值.

2.3 兩種群的競爭淘汰機制

為使PSO與GA算法能夠進行優(yōu)勝劣汰的良性競爭，提高差的算法種群的質(zhì)量，并增加一定的淘汰率使得步驟2.5中具有優(yōu)秀知識的個體加入種群中，本文設計的淘汰機制有兩種：

(1)當兩個種群分別加入10個精英個體后，為保證種群數(shù)量不變，需淘汰適應最差的10個染色體.

(2)淘汰相同的染色體.

為了增加種群的淘汰率，保證新的具有優(yōu)秀知識的個體加入GA種群中，故GA有10個染色體來自于前40個染色體中適應度前10的個體，保證使用淘汰機制(2)后GA種群的數(shù)量不足50.通過自然演化，若一種群效果比另一個算法效果好很多，則其精英個體可以全部替代另一種群中的最差個體，而自己的精英個體再替代自己的較差個體從而實現(xiàn)優(yōu)勝劣汰的演化.

2.4 變鄰域搜索

鄰域搜索可以增強算法的搜索能力，針對該協(xié)同進化算法，對所有種群使用了文獻[10]和[11]中提出的3種鄰域結構(1)～(3)進行搜索，針對精英種群提出了2種遍歷搜索的鄰域結構(4)和(5)進行隨機遍歷搜索(本文中使用的隨機概率為0.2)，若適應度值更優(yōu)則代替之前染色體，反之則不.

(1)VNS1:在工序順序染色體讓隨機選擇一段連續(xù)的染色體，進行倒轉(zhuǎn).

(2)VNS2:在工序順序染色體上隨機選擇兩個染色體進行位置交換.

(3)VNS3:在機器選擇染色體上隨機選擇一個染色體使其選擇時間最短的機器，若已是最短則不執(zhí)行.

(4)VNS4:在工件順序染色體上每個染色體有0.2的概率被選中，使其與其他所有的染色體互換一遍.

(5)VNS5:在機器選擇染色體上每個染色體有0.2的概率被選中，使其把所有可選的機器號都選一遍.

2.5 根據(jù)最優(yōu)個體生成新個體

針對編碼中機器選擇編碼部分在算法后期，適應度較好的個體基本機器選擇基本類似，故本文提出了一種對當前全局最優(yōu)解進行機器選擇知識學習的知識結構.在每一次迭代更新全局最優(yōu)解后，機器的選擇可能與上一代最優(yōu)解的機器選擇知識完全不同，故本算法使用的知識體僅為當前最優(yōu)解的染色體.通過根據(jù)全局最優(yōu)的機器選擇部分染色體的位置點來提高下一代種群生成時機器選擇染色體與全局最優(yōu)相同的概率,從而根據(jù)全局最優(yōu)解的機器選擇知識來指導新種群生成的方向，增強種群的質(zhì)量，提高收斂的速度，減少低效的搜索.

知識體結構如圖6所示，當機器有J個選擇位置，Xi為最優(yōu)個體時，第i個工件的產(chǎn)生概率Px公式(4)、(5)為機器選擇知識體的變更公式.

圖6 知識體結構Fig.6 Body of knowledge

P(i)=P(i)+0.2

(4)

(5)

與文獻[8]相比，本文知識體避免了在迭代后期部分機器選擇概率收斂為1的情況.

2.6 算法框架

本文提出了一種基于GA和PSO的學習型協(xié)同進化算法.遺傳算法中染色體共有50個，其中有40 個染色體是隨機生成的，其中有10個個體是來自于前40個中適應度前10的染色體.這樣即可以把優(yōu)良的染色體保留下來，讓其與普通種群的染色體進行信息交流，同時在淘汰染色體重復種群過程中增加淘汰的數(shù)量，增加種群的多樣性.通過錦標賽選擇讓染色體不過于單一也保證種群的多樣性，使用文獻[12]中提出的IPOX交叉來增加交叉的概率保證了遺傳算法的搜索能力.同時加入了50個PSO的種群進行搜索，來增加算法收斂速度.在淘汰染色體相同的個體后，根據(jù)全局最優(yōu)的染色體中獲取更新機器選擇的知識，使用機器選擇知識來生成新的染色體以補齊兩種群中個體的數(shù)量，算法流程如圖7所示.

圖7 學習型協(xié)同進化算法流程圖Fig.7 Flowchart of Learning co-evolutionary algorithm

3 仿真與分析

本文采用MATLAB2020b進行編程并在 Windows10, Intel (R) Core (TM) i7-5500U, CPU2.4 GHz，內(nèi)存4GB，輸入種群規(guī)模為100，最大迭代次數(shù)為200，交叉概率為0.6，變異概率為0.1.

3.1 實驗1

為了驗證該算法的搜索能力，結合Benchmark標準算例，每個算例分別運行5次取最優(yōu)結果為值，并找到相同參數(shù)下的不同或理論相似的算法：姜天華[6,13]于2018年提出的灰狼優(yōu)化算法 (grey wolf optimization, GWO) 以及混合灰狼優(yōu)化算法 (hybrid grey wolf optimization, HGWO),Caldeira 等[14]于2019年提出的改進Jaya算法(improver jaya algorithm, IJaya),Chen等[15]于2020年提出的一種基于強化學習的自學習遺傳算法 (self leaning Genetic Algorithm,SLGA), Ding等[16]于2020年提出的基于改進粒子群優(yōu)化算法的柔性作業(yè)車間調(diào)度新編碼和解碼方案(improve Particle swarm optimization,IPSO)進行比較.

由表1可以看出在Benchmark算例中本文算法除了MK01～MK06、MK08～MK10算例外都可以求出與這些算法對比下的最優(yōu)解；在MK06、MK07算例中，算法效果也僅比IJaya算法效果差，并且結果都是接近于最優(yōu)解并且優(yōu)于其他算法最優(yōu)解的.同時在空間度較為復雜的大算例MK09、MK10中，在之前算例中出眾的IJava、SLGA等算法無法求解或求解效果較差，但是本文算法能夠求出遠優(yōu)于其他算法的結果.

圖8為表1中標準算例MK09的調(diào)度甘特圖.

表1 算例對比

續(xù)表1

圖8 MK09甘特圖Fig.8 MK09 Gantt Chart

為進一步測試本文算法的優(yōu)越性，將本文算法與文獻[13，18，19]的算法使用kacem算例進行對比，能夠求解的最優(yōu)值如表2所示.

表2 算例對比

由表2可以看出本文算法在5個算例中均能求出最優(yōu)值，結合表1的數(shù)據(jù)對比可以看出本文算法在求解FJSP問題時具有一定的有效性.

3.2 實驗2

為了證明算法的穩(wěn)定性，使用文獻[16]提出的算例，同時與文獻[7，15，17]的實驗在相同的參數(shù)條件下進行對比求解10次并求平均值.由表3可以看出本文算法求出該算例的最優(yōu)值且平均在19.3代以內(nèi)就可以求解出最優(yōu)值.

表3 算例對比

圖9為實驗2中算例的調(diào)度甘特圖.

圖9 調(diào)度甘特圖Fig.9 Schedule a Gantt chart

可以由上面的表格數(shù)據(jù)看出本文提出的算法不僅在平均值上優(yōu)于其他算法，而且穩(wěn)定性方面同樣表現(xiàn)優(yōu)秀.

4 結 論

針對FJSP算法在大規(guī)模算例中搜索能力差、容易陷入局部最優(yōu)解的問題設計了一套基于GA和PSO的改進協(xié)同進化算法，加入了變鄰域搜索和對機器知識的學習，通過與其他算法在標準算例中的對比得出如下結論：

1) 針對最優(yōu)全局個體的染色體來設計針對機器選擇知識的知識體，從而影響下一代個體的生成，可以提高新生成種群的質(zhì)量，提高算法的搜索能力.

2) 多種群的協(xié)同可使兩算法相互競爭、共享精英個體，同時增加種群的多樣性來擺脫局部最優(yōu)，提高算法搜索能力.

3) 針對精英個體進行變鄰域搜索，在提高算法搜索能力的同時還可以節(jié)省算法的計算工作量.