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

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

0 引言

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

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

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

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

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

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

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

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

1.1 問題描述

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

表1 FJSP加工實(shí)例

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

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

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

1.2.2 MOFJSP調(diào)度指標(biāo)

（1）最大完工時(shí)間

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

其中：Ci代表每個(gè)工件的完工時(shí)間.

（2）機(jī)器總負(fù)荷

機(jī)器總負(fù)荷是指所有工件均被加工完成之后，工件在機(jī)器上的加工時(shí)間總和.

（3）瓶頸機(jī)器負(fù)荷

瓶頸機(jī)器負(fù)荷是指所有工序被加工完成之后，負(fù)荷（加工時(shí)間）最多的機(jī)器所用的時(shí)間.

2 算法介紹

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

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

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

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

2.1 種群更新機(jī)制

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

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

以C1為例：

3 編碼和解碼

3.1 種群初始化

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

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

初始化操作

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),得到一組隨機(jī)序列[f1(x1),f2(x1)···fL(x1)]，對(duì)應(yīng)初始加工工序；

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

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

表2 種群初始化

3.2 編碼和解碼

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

工序解碼

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

表3 工序解碼

機(jī)器解碼

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

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

3.3 最佳序列更新機(jī)制

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

NS1：隨機(jī)選擇工序碼的兩個(gè)位置進(jìn)行交換；

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

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

NS4：將原工序碼整體進(jìn)行倒序操作；

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

4 多目標(biāo)策略

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

4.1 計(jì)算個(gè)體非支配等級(jí)

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

Step1設(shè)i=1；

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

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

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

4.2 計(jì)算個(gè)體擁擠度

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

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

5 IWPA解決MOFJSP步驟

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

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

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

6 仿真測(cè)試及分析

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

為了驗(yàn)證IWPA的優(yōu)勢(shì)，本文選擇3種不同規(guī)模的算例，使用不同文獻(xiàn)中的算法進(jìn)行求解比較.3種算例分別為：Kacem1、Kacem2、Kacem3.參考文獻(xiàn)分別為：混合人工蜂群算法（Hybrid Artificial Bee Colony Algorithm,HTABC）[13]、狀態(tài)轉(zhuǎn)移算法（State Transition Algorithm,STA）[14]、改進(jìn)入侵雜草優(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）.對(duì)比結(jié)果如表4所示.

從“非劣解組數(shù)”“單目標(biāo)最優(yōu)解”“Pareto占優(yōu)”三個(gè)層面對(duì)表4進(jìn)行分析.

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

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

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

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

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

（3）Pareto占優(yōu)

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

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

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

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

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

7 結(jié)論

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

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

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

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

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