陳嘉朋，張宏立，王 聰，馬 萍

(新疆大學(xué) 電氣工程學(xué)院，新疆 烏魯木齊 830017)

0 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem,FJSP）[1]是一類復(fù)雜的NP-hard優(yōu)化問題，其難點在于需要同時考慮作業(yè)車間的加工次序和加工機器.隨著對FJSP的研究不斷深入，更符合實際需要的多目標柔性作業(yè)車間調(diào)度問題（Multi-objective Flexible Job-shop Scheduling Problem,MOFJSP）[2]成為目前的研究熱點.在研究多目標柔性作業(yè)車間調(diào)度問題時，MOFJSP滿足更多的約束條件，同時各個目標函數(shù)之間互相制約，導(dǎo)致各個目標函數(shù)值很難同時達到最優(yōu).所以，MOFJSP是更難的NP-hard優(yōu)化問題.

許多學(xué)者針對MOFJSP進行了廣泛和深入的研究.Huang[3]等人將粒子群算法和遺傳算法巧妙融合，通過教與學(xué)的方式體現(xiàn)混合算法求解MOFJSP的有效性；朱光宇[4]等人將灰熵并行分析引入粒子群算法對多目標柔性作業(yè)車間調(diào)度問題進行求解，通過測試驗證了灰熵并行法的有效性；朱偉[5]等人運用遺傳算法（Genetic Algorithm,GA）來優(yōu)化以加工總成本和最大加工時間為目標的MOFJSP，通過對算法算子、編碼結(jié)構(gòu)、自適應(yīng)變異規(guī)則的改進和更新，算法和模型的魯棒性和有效性得以提高；趙博選[6]等人提出一種多策略融合Pareto人工蜂群算法來求解MOFJSP，多種搜索策略互相融合，不僅使算法實現(xiàn)了人工蜂群的自主與協(xié)同搜索，而且達到了全局探索與局部尋優(yōu)的平衡效果.上述智能優(yōu)化算法為MOFJSP的求解開辟了新的研究方向和思路，但算法求解全局最優(yōu)解的能力有待進一步提高.

為解決傳統(tǒng)群智能優(yōu)化算法在求解MOFJSP時存在易陷入局部最優(yōu)、算法后期收斂速度慢等問題，本文使用吳虎勝等人提出的一種新型群智能優(yōu)化算法——狼群算法[7]，并將量子粒子群算法中的三個重要參數(shù)與其融合，得到一種新的混合優(yōu)化算法對MOFJSP進行求解.狼群算法模擬狼群獵食行為及獵物分配方式，抽象出“游走”“召喚”“圍攻”3種智能行為和“勝者為王”的頭狼產(chǎn)生規(guī)則及“強者生存”的狼群更新機制.狼群算法結(jié)構(gòu)清晰，尋優(yōu)策略豐富，特別是針對多峰、高維的目標函數(shù)有著較好的求解性能，這些優(yōu)勢使算法在時間序列預(yù)測[8]、故障診斷[9]等方面有著廣泛的應(yīng)用，但狼群算法在尋優(yōu)過程中，也存在算法后期收斂速度慢、易陷入局部最優(yōu)的問題.

本文針對狼群算法尋優(yōu)過程中存在的問題，提出一種將量子粒子群算法中能夠引導(dǎo)粒子以較快的收斂速度，在一定的搜索范圍內(nèi)朝著全局最佳位置不斷靠近的三種性能參數(shù)與狼群算法融合的混合優(yōu)化算法來求解MOFJSP.創(chuàng)新點主要為：

（1）種群初始化.將高斯分布的概率密度函數(shù)運用于種群初始化，以得到質(zhì)量較高的初始種群.

（2）搜索策略.將量子粒子群算法中的吸引子、收縮擴張系數(shù)、勢阱特征長度三個重要參數(shù)和狼群算法融合，增強算法的全局搜索性能和收斂速度；采用物元分析法更新種群，提高種群的自適應(yīng)能力.

（3）最優(yōu)解操作.通過局部鄰域搜索，給予最佳序列充分的計算資源，以增強算法的全局搜索性能.

1 MOFJSP問題描述和數(shù)學(xué)模型建立

1.1 問題描述

FJSP描述如下:m個工件在n臺機器上加工，每個工件至少有一道加工工序，每道工序可以選擇不同的機器進行加工，不同工序的加工時間取決于所選機器的性能.表1為FJSP的一個加工實例.

表1 FJSP加工實例

1.2 建立FJSP數(shù)學(xué)模型

1.2.1 數(shù)學(xué)變量定義

m為工件數(shù)；n為機器數(shù)；i為工件序號，i=1,2,3,···,m；j為機器序號，j=1,2,3,···,n；Ci為每個工件的完工時間；Cmax為最大完工時間；Oih為第i個工件的第h道工序；Mih為第i個工件的第h道工序的可選加工機器數(shù)；Mjih為第i個工件的第h道工序在機器j上加工；Pjih為第i個工件的第h道工序在機器j上的加工時間；Tih為第i個工件的第h道工序開始加工時間；Cih為第i個工件的第h道工序加工完成時間；Sjih為Mjih對應(yīng)的加工時間；L為工序序號，L=1,2,3···,hi；xjih=1，工序Oih選擇機器j進行加工；xjih=0，工序Oih不選擇機器j進行加工；yihjkl=1，工序Oih先于工序Ojkl進行加工；yihjkl=0，工序Oih晚于工序Ojkl進行加工.

1.2.2 MOFJSP調(diào)度指標

（1）最大完工時間

最大完工時間是指所有工件均被加工之后，最后離開機器的一道工序所對應(yīng)的完工時間.性能指標通常表述為：

其中：Ci代表每個工件的完工時間.

（2）機器總負荷

機器總負荷是指所有工件均被加工完成之后，工件在機器上的加工時間總和.

（3）瓶頸機器負荷

瓶頸機器負荷是指所有工序被加工完成之后，負荷（加工時間）最多的機器所用的時間.

2 算法介紹

狼群算法（Wolf Pack Algorithm,WPA）是基于狼群智能行為的新型優(yōu)化算法，算法基本思想是“任務(wù)分配，各盡其職”和“弱肉強食，適者生存”.算法意在通過模擬自然界的生物種群行為由概率模型搜索最優(yōu)解.量子粒子群算法（Quantum Particle Swarm Optimization,QPSO）是一種考慮量子行為的粒子群算法，該算法相較于傳統(tǒng)的粒子群算法，具有更好的收斂速度和全局搜索性能.將QPSO中的三種重要性能參數(shù)與WPA相結(jié)合，以形成改進狼群算法對多目標柔性作業(yè)車間調(diào)度問題進行求解.狼群位置更新分為三個階段，分別為探狼游走、頭狼召喚和猛狼圍攻.三個階段的主要改進位置更新公式如(4)、(5)和(6)所示：

式(4)為探狼游走位置更新公式.探狼在搜索空間中朝著獵物氣味濃度更深的方向不斷游走，以獲取最佳位置.當探狼達到最大游走次數(shù)時，選擇最佳目標函數(shù)值的狼為新頭狼.為使探狼進行更為精細的搜索，擴大種群的搜索范圍，避免算法陷入局部最優(yōu)，將收縮擴張系數(shù)β和歸一化因子w引入探狼游走行為.

式(5)為猛狼奔襲更新公式.QPSO中粒子i的吸引子s(i)能夠使粒子以較快的速度朝著最佳粒子不斷移動，以提高算法的收斂速度和全局搜索性能.

狼群在圍攻獵物的過程中，容易超出設(shè)定的搜索空間范圍，得到不可行解，從而導(dǎo)致算法的求解性能下降.將勢阱特征長度Li引入狼群圍攻行為的位置更新公式，如式(6).勢阱特征長度Li能夠使參與圍攻行為的個體處在有效的搜索空間內(nèi).

2.1 種群更新機制

采用物元分析法，對獵食之后的種群進行更新和保存操作，以滿足更優(yōu)的解進入種群下一次迭代.在物元分析中，物元R=(M,C,X)，M代表物元的名稱，C代表特征，X代表特征對應(yīng)的物元量值.將個體對應(yīng)的位置放入物元特征，將位置更新操作放入物元名稱，所得到的新適應(yīng)度函數(shù)值作為物元量值.矩陣Rmn為n個m維物元矩陣.

其中：C1,C2,C3···Cm為捕獵之后個體對應(yīng)的位置；M1,M2,M3···Mn為不同位置下的不同更新策略；fit()為不同位置更新之后的適應(yīng)度函數(shù)值.

以C1為例：

3 編碼和解碼

3.1 種群初始化

初始種群的質(zhì)量對種群迭代過程中的收斂速度以及全局最優(yōu)解的求解起到重要的作用，生成一個較高質(zhì)量的初始種群十分關(guān)鍵.本文采用高斯分布的概率密度函數(shù)[10]產(chǎn)生隨機變量來調(diào)整加工序列，從而對種群進行初始化.采用的概率密度函數(shù)為：

其中：μ為均值，表示概率密度函數(shù)分布曲線的對稱軸；σ為標準差，表示對稱軸到左右兩邊曲線的某一寬度.

初始化操作

Step1設(shè)置x1=rand(0,1)，σi=rand(0,1)，μi=rand(-1,1)，i=1,2,3···L，L為總工序數(shù).保持x1不變，將L組(σi,μi)帶入f(x),得到一組隨機序列[f1(x1),f2(x1)···fL(x1)]，對應(yīng)初始加工工序；

Step2將[f1(x1),f2(x1)···fL(x1)]進行升序排列，同時將初始加工工序隨著變量的升序進行調(diào)整，得到新的加工工序.

通過重復(fù)Step1到Step2，直到產(chǎn)生與種群規(guī)模相同的初始加工工序.利用高斯分布的概率密度函數(shù)產(chǎn)生隨機數(shù)序列的方式來進行種群初始化，可以使初始種群個體離散地分布在解空間內(nèi)，有效提高了初始種群的質(zhì)量和多樣性.種群初始化過程如表2所示.

表2 種群初始化

3.2 編碼和解碼

為更好滿足工藝路線的約束，本文采用雙層編碼方式進行編碼.基于表1，工序編碼為(113322)，表示O11、O12、O31、O32···，以此類推；設(shè)機器編碼為(113212)，表示O11選擇機器1，O12選擇機器1，O13選擇機器3，O21選擇機器2···以此類推（Oij代表工件i的第j道工序）.

工序解碼

根據(jù)Logistic映射方程[11]，產(chǎn)生一組隨機均勻的隨機數(shù)S1.S1對應(yīng)相應(yīng)的加工工序.將S1升序，并得到對應(yīng)索引值.升序時，若S1出現(xiàn)相同的數(shù)值，以左（小數(shù)值）進行優(yōu)先排序.S1進行升序后，計算S(new)=S1×(G÷V)，G為工件總數(shù)，V 為工序總數(shù).當S(new)為小數(shù)時，將其朝著比自身大的方向進行取整.S(new)對應(yīng)相應(yīng)的工件號.表3為工序解碼過程.

表3 工序解碼

機器解碼

設(shè)工件i的第h道工序為u；第i個工件的第h道工序開始加工時間為ST(u)，加工時間為Tp，則完工時間為ST(u)+Tp；該工序的工件前任工序和機器前任工序分別用JP(u)和MP(u)表示.則有：

本文采用貪婪策略對機器進行解碼.選擇使ST(u)+Tp最小的機器加工，若出現(xiàn)機器的加工時間相同，則選擇使Tp最小的機器加工.

3.3 最佳序列更新機制

本文采用鄰域結(jié)構(gòu)搜索策略，給予最佳序列充分的計算資源，不斷提高算法尋求全局最優(yōu)解的能力和收斂速度.

NS1：隨機選擇工序碼的兩個位置進行交換；

NS2：隨機選擇工序碼的一個位置為交換點，將兩端的序列直接旋轉(zhuǎn)交換；

NS3：隨機選擇工序碼的一個位置，將其對應(yīng)的數(shù)值從工序碼中剔除，再隨機插入剩余序列的任意位置；

NS4：將原工序碼整體進行倒序操作；

NS5：任意選擇工序碼的一個位置數(shù)值i變?yōu)閕+1(i/=i(max))，同時任意選擇工序碼的一個位置數(shù)值i+1變?yōu)閕.

4 多目標策略

本文通過計算種群個體的非支配等級[12]和擁擠度的方法，對狼群中的最優(yōu)解和最劣解進行保存，便于狼群在迭代過程中個體狼的位置更新.

4.1 計算個體非支配等級

對于種群規(guī)模為N(t)的種群P，t為迭代次數(shù).具體操作步驟如下：

Step1設(shè)i=1；

Step2對于所有的j=1,2,3···N(t)，且j/=i，基于個體的適應(yīng)度函數(shù)比較個體i和個體j之間的非支配和支配關(guān)系.如果所有個體j均不優(yōu)于個體i，則將i判定為非支配個體；

Step3令i=i+1，返回Step1，直到找出所有的非支配個體.

通過Step1至Step3得到第一層的非支配解集.然后，剔除第一層非支配解集對剩余個體重復(fù)Step1至Step3，得到第二層非支配解集···直到種群被分層.種群規(guī)模隨著迭代次數(shù)，不斷進行更新操作.

4.2 計算個體擁擠度

擁擠度即為擁擠距離，是指單個Rank層中個體的密集程度.計算個體擁擠度是為了得到同一等級Pareto解的優(yōu)先級關(guān)系，擁擠度計算公式如下：

其中：V 為目標函數(shù)的個數(shù)，fv(i?1)和fv(i+1)為該個體排序之后前后兩位目標函數(shù)值；fmaxv為某一目標函數(shù)的最大值；fminv為某一目標函數(shù)的最小值.當個體i的擁擠度ndi大于個體j的擁擠度ndj，則個體i占優(yōu).

5 IWPA解決MOFJSP步驟

Step1種群初始化.設(shè)置種群規(guī)模、迭代次數(shù)、探狼比例因子、探狼初始游走方向數(shù)、步長因子等參數(shù).計算個體非支配等級以及個體擁擠度后對個體進行排序，選出適應(yīng)度值最佳的狼為頭狼，并對頭狼采用最佳序列機制進行調(diào)整（在種群更新和迭代的過程中，只要產(chǎn)生頭狼，就使用最佳序列更新機制，更新頭狼），其余個體狼分別為探狼和猛狼；

Step2種群迭代.探狼位置更新；頭狼召喚猛狼，猛狼位置更新；然后計算猛狼和當前新頭狼之間的距離，判斷猛狼是否轉(zhuǎn)入獵物圍攻行為；圍攻獵物之后，使用物元分析法更新種群，再次計算個體的非支配等級和擁擠距離，選出最佳個體為種群新頭狼；

Step3判斷是否滿足要求，若滿足算法輸出條件，則輸出對應(yīng)的最優(yōu)解以及適應(yīng)度函數(shù)值；若不滿足，返回Step2.

6 仿真測試及分析

仿真實驗采用MATLAB 2018b實現(xiàn)，運行環(huán)境：處理器Core i5-8265U@1.60 GHz，Windows10操作系統(tǒng).IWPA參數(shù)設(shè)置如下：設(shè)置探狼比例因子為3，探狼每一次游走的方向數(shù)最小值為4，最大值為10；步長因子為200；改進狼群算法的種群規(guī)模和最大迭代次數(shù)等基本參數(shù)和比較算法保持一致.

為了驗證IWPA的優(yōu)勢，本文選擇3種不同規(guī)模的算例，使用不同文獻中的算法進行求解比較.3種算例分別為：Kacem1、Kacem2、Kacem3.參考文獻分別為：混合人工蜂群算法（Hybrid Artificial Bee Colony Algorithm,HTABC）[13]、狀態(tài)轉(zhuǎn)移算法（State Transition Algorithm,STA）[14]、改進入侵雜草優(yōu)化算法（Improve Invasive Weed Optimization Algorithm,IIWO）[15]、多種鄰域結(jié)構(gòu)雜草優(yōu)化算法（Multiple Neighborhood Structures Weed Optimization Algorithm,MNSEO）[16]、狼群算法（Wolf Colony Algorithm,WPA）、灰狼算法（Grey Wolf Optimization,GWO）.對比結(jié)果如表4所示.

從“非劣解組數(shù)”“單目標最優(yōu)解”“Pareto占優(yōu)”三個層面對表4進行分析.

表4 多種算法結(jié)果比較

（1）非劣解組數(shù)

算法求出的非劣解組數(shù)較多，可以體現(xiàn)出算法有較好的求解性能.針對Kacem1算例：IWPA可以求出3組非劣解，和HTABC求解性能相同，強于IIWO、STA、MNSEO、GWO、WPA；針對Kacem2算例：IWPA可以求出5組非劣解，和MNSEO求解性能相同，強于HTABC、IIWO、STA、GWO、WPA；針對Kacem3算例：IWPA可以求出3組非劣解，和HTABC求解性能相同，強于IIWO、STA、MNSEO、GWO、WPA.

（2）單目標最優(yōu)解

通過比較單目標最優(yōu)解，可以從整體性能上判斷算法的優(yōu)劣.將每種算法求出的Pareto解集中的單個目標的最優(yōu)解進行取出合并，構(gòu)成單目標最優(yōu)解.針對Kacem1算例，IWPA求出非劣解的能力要強于HTABC、IIWO、STA、WPA、GWO；針對Kacem2算例，IWPA求出非劣解的能力要強于HTABC、IIWO、STA、MNSEO、GWO、WPA；針對Kacem3算例，IWPA求出非劣解的能力要強于HTABC、STA、WPA，和GWO能力大致相同.

（3）Pareto占優(yōu)

比較不同算法之間的Pareto占優(yōu)關(guān)系，對算法求解Pareto解集的能力進行綜合判斷.通過Pareto占優(yōu)分析可知：針對Kacem1算例，IWPA求出非劣解的能力要強于WPA、GWO、IIWO，和STA大致相同，弱于HTABC；針對Kacem2算例，IWPA求出非劣解的能力要強于其他5種對比算法，和MNSEO大致相同；針對Kacem3算例，IWPA求出非劣解的能力要強于WPA、GWO、STA，弱于HTABC.針對Kacem3算例，選擇一組非劣解集，使用IWPA畫出相應(yīng)的甘特圖，如圖1所示.

圖1 Kacem3調(diào)度甘特圖

通過“非劣解個數(shù)”“單目標最優(yōu)解”“Pareto占優(yōu)”三個層面進行分析，可以得到：

（a）IWPA能夠求出較多組數(shù)目的Pareto解集，求取的非支配解的數(shù)目越多，被選擇為Pareto最優(yōu)解的可能性就越大；

（b）IWPA有較好的單目標最優(yōu)解，通過與其他智能優(yōu)化算法所得結(jié)果進行比較，可以看出本文的IWPA具有一定的求解優(yōu)勢.針對Kacem1算例，IWPA求出的單目標最優(yōu)解為(11,31,8)，較其他算法有較強的求解優(yōu)勢；針對Kacem2算例，IWPA求出的單目標最優(yōu)解為(14,73,11)，IWPA求出非劣解的能力要強于HTABC、IIWO、STA、MNSEO、GWO、WPA；針對Kacem3算例，IWPA求出非劣解的能力要強于HTABC、IIWO、STA、MNSEO、GWO、WPA；IWPA在Pareto占優(yōu)層面，也具有較強的尋優(yōu)優(yōu)勢，能夠向組合后的單目標最優(yōu)解提供較多的選擇.

7 結(jié)論

本文基于狼群算法的基本結(jié)構(gòu)和尋優(yōu)優(yōu)勢，提出一種將量子粒子群算法的重要參數(shù)和狼群算法融合的混合優(yōu)化算法對多目標柔性作業(yè)車間調(diào)度問題進行求解.

（1）新型混合優(yōu)化算法使尋優(yōu)種群在一定的搜索范圍之內(nèi)，以較快的收斂速度朝著全局最優(yōu)個體不斷靠攏，算法求解全局最優(yōu)解的能力得以增強；

（2）采用高斯分布的概率密度函數(shù)對種群進行初始化，提高初始種群的質(zhì)量和多樣性；通過最佳序列調(diào)整機制，不斷更新最優(yōu)解的同時也提高了算法的收斂速度；

（3）物元分析法豐富了種群的更新策略，有利于種群的迭代進化.

通過以上分析，可知本文所提出的混合優(yōu)化算法對求解MOFJSP具有一定的合理性和優(yōu)勢.筆者將在本文研究基礎(chǔ)之上，進一步探究混合狼群算法應(yīng)用于不確定因素影響、動態(tài)重調(diào)度等更加復(fù)雜的車間調(diào)度問題.