王秋蓮 段星皓

南昌大學(xué)經(jīng)濟(jì)管理學(xué)院，南昌，330031

0 引言

柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)是指在一定的約束條件下，同時(shí)確定工件加工機(jī)器和加工順序，以達(dá)到理想的調(diào)度目標(biāo)[1]。FJSP是NP-hard問題，大規(guī)模的FJSP很難通過數(shù)學(xué)規(guī)劃方法、拉格朗日松弛法等精確方法求得理論解，因此更多的研究采用啟發(fā)式算法對(duì)FJSP進(jìn)行求解。如何改進(jìn)啟發(fā)式算法使得其收斂性、穩(wěn)定性達(dá)到更優(yōu)是當(dāng)前研究的熱點(diǎn)。

FJSP根據(jù)調(diào)度目標(biāo)的數(shù)量分為單目標(biāo)FJSP和多目標(biāo)FJSP(multi-objective FJSP，MOFJSP)。其中，MOFJSP可進(jìn)一步細(xì)分為低維(調(diào)度目標(biāo)不超過3個(gè))MOFJSP和高維MOFJSP。目前，大部分學(xué)者主要對(duì)低維MOFJSP進(jìn)行研究，如孫麗珍等[2]以最小化最大完工時(shí)間、機(jī)器負(fù)載的均方差為目標(biāo)，設(shè)計(jì)了一種改進(jìn)解碼方法和初始化規(guī)則的遺傳算法；孟冠軍等[3]提出一種混合人工蜂群算法求解以最大完工時(shí)間、最大機(jī)器負(fù)荷和機(jī)器總負(fù)荷為目標(biāo)的低維MOFJSP。實(shí)際生產(chǎn)中，制造企業(yè)不僅需要考慮上述目標(biāo)，還需要考慮能源消耗。李進(jìn)宇等[4]研究了基于遞歸分析和圖像處理技術(shù)的混流車間能耗。李明等[5]提出一種新型帝國(guó)競(jìng)爭(zhēng)算法來求解以最小化完工時(shí)間、最大拖期、最大機(jī)器負(fù)荷和總能耗為目標(biāo)的高維MOFJSP，但該方法對(duì)高維多目標(biāo)解集個(gè)體的選擇壓力不足，可能導(dǎo)致算法的過早收斂。黃夏寶等[6]提出一種改進(jìn)的NSGAⅢ算法，引入基于參考點(diǎn)的小生境選擇機(jī)制來提高算法的多樣性，求解以最小化最大完工時(shí)間、機(jī)器總負(fù)荷、最大機(jī)器負(fù)荷和機(jī)器能耗為目標(biāo)的高維MOFJSP，但該算法的局部搜索能力還有待提高。由此可見，考慮能耗目標(biāo)的高維MOFJSP研究是當(dāng)前車間調(diào)度問題研究的熱點(diǎn)及難點(diǎn)，但處于起步階段[7]。

候鳥優(yōu)化(migrating birds optimization，MBO)算法[8]可用于求解二次分配問題，且所得的最終結(jié)果優(yōu)于遺傳算法、模擬退火算法等常用算法。QUAN等[9]將MBO算法用于求解混合流水車間的調(diào)度問題；任彩樂等[10]提出兩階段解碼方法及4種鄰域結(jié)構(gòu)的改進(jìn)MBO算法，求解混合流水車間調(diào)度問題。此外，有學(xué)者通過MBO算法來求解FJSP，如姚妮[11]以最小化最大完工時(shí)間為目標(biāo)，結(jié)合MBO算法和變鄰域搜索策略來提高算法局部搜索能力；劉雪紅等[12]設(shè)計(jì)一種改進(jìn)的MBO算法，引入精英分批策略和可行鄰域結(jié)構(gòu)策略來解決以最小化最大完工時(shí)間和最大批次數(shù)目為目標(biāo)的低維MOFJSP。

盡管這些學(xué)者證明MBO算法對(duì)FJSP能獲得高質(zhì)量解集，但用MBO算法進(jìn)行高維MOFJSP的研究較少，因此本文建立一種以最小化完工時(shí)間、機(jī)器總負(fù)荷、延期時(shí)間、生產(chǎn)總能耗為優(yōu)化目標(biāo)的MOFJSP模型，在改進(jìn)MBO算法的基礎(chǔ)上，引入Pareto思想和基于參考點(diǎn)的選擇算子，設(shè)計(jì)了一種高維多目標(biāo)候鳥優(yōu)化(multi-objective migrating birds optimization，MOMBO)算法，通過2種選擇算子給予鳥群選擇壓力，以提高鳥群的多樣性和收斂性，并基于屬性層次模型和灰色關(guān)聯(lián)度分析法的組合權(quán)重決策選擇最優(yōu)解。最后通過算例和實(shí)驗(yàn)驗(yàn)證算法的有效性。

1 高維多目標(biāo)柔性作業(yè)車間調(diào)度模型

FJSP可以描述為：工件集J={J1，J2，…，Jn}中的n個(gè)工件在機(jī)器集M={M1，M2，…，Mm}中的m臺(tái)機(jī)器上加工，其中，第i個(gè)工件Ji有ei個(gè)工序。MOFJSP主要需要解決兩類子問題：機(jī)器選擇和工序排序，其中，機(jī)器選擇是指從可選機(jī)器集Mij(i∈[1，n]，j∈[1，ei])中選擇一個(gè)機(jī)器完成工序Oij，工序排序是確定每個(gè)機(jī)器的加工順序。

工件加工過程中，有以下假設(shè)：①所有機(jī)器在0時(shí)刻均可開始加工工件，所有工件在0時(shí)刻均被釋放；②每臺(tái)機(jī)器一次只能完成一道工序，每道工序在同一時(shí)刻只能由一臺(tái)機(jī)器完成；③工件的加工需嚴(yán)格按照工序依次完成；④加工一旦開始就不能中止，直到完成；⑤機(jī)器完成最后一道加工就停止運(yùn)行；⑥加工過程中，工件的轉(zhuǎn)移時(shí)間忽略不計(jì)。

本文提出的多目標(biāo)柔性作業(yè)車間調(diào)度模型的調(diào)度目標(biāo)的具體描述如下：

(1)最大完工時(shí)間。最大完工時(shí)間是指所有工件加工完成的時(shí)間，即最后一個(gè)工件加工的完工時(shí)間，其計(jì)算公式為

f1=max(Ci|i=1，2，…，n)

(1)

式中，Ci為工件i最后一道工序的完工時(shí)間。

(2)總拖期?？蛻艉推髽I(yè)會(huì)約定產(chǎn)品的交貨期，交貨時(shí)間超過交貨期，企業(yè)會(huì)損失信譽(yù)并被罰款。總拖期可以反映企業(yè)的信譽(yù)情況，其計(jì)算公式為

(2)

式中，Di為工件i的交貨期。

(3)機(jī)器總負(fù)荷。機(jī)器總負(fù)荷指所有加工機(jī)器的負(fù)荷總和，可以反映企業(yè)資源的利用效率，其計(jì)算公式為

(3)

式中，tijk為工序Oij在機(jī)器k上的加工時(shí)間；xijk為0-1變量，xijk=1表示工序Oij在機(jī)器k上加工，xijk=0表示Oij不在機(jī)器k上加工。

(4)總能耗。總能耗主要包括車間固定能耗、機(jī)器空載能耗、機(jī)器加工能耗，其計(jì)算公式為

(4)

(5)

(6)

Eg=Pgmax(Ci|i=1，2，…，n)

(7)

2 高維多目標(biāo)候鳥優(yōu)化算法

候鳥在飛行過程中會(huì)自然排成V字形隊(duì)列，這是因?yàn)轭I(lǐng)飛鳥通過翅膀扇動(dòng)形成一股氣流，氣流向后方流動(dòng)從而加大后方壓力，跟飛鳥利用壓力差飛行得更加輕松。MBO算法模仿候鳥的遷徙過程，將表現(xiàn)最優(yōu)的可行解作為領(lǐng)飛鳥，將其他可行解作為跟飛鳥。MBO算法主要分為鳥群初始化、領(lǐng)飛鳥進(jìn)化、跟飛鳥進(jìn)化和替換領(lǐng)飛鳥四個(gè)階段。本文在此基礎(chǔ)上，引入基于Pareto支配和基于參考點(diǎn)的選擇算子，對(duì)鳥群初始化、飛鳥進(jìn)化階段進(jìn)行改進(jìn)，提出一種高維多目標(biāo)候鳥優(yōu)化算法，該算法流程如圖1所示。

圖1 高維多目標(biāo)候鳥優(yōu)化算法流程圖

2.1 基于Pareto支配和參考點(diǎn)的選擇規(guī)則

本文引入基于Pareto支配的選擇算子和基于參考點(diǎn)的選擇算子來增強(qiáng)對(duì)Pareto前沿面的選擇壓力，進(jìn)而對(duì)解進(jìn)行篩選和替換。

2.1.1基于Pareto支配的選擇算子

Pareto支配的定義為：對(duì)于解p和q，當(dāng)且僅當(dāng)解p的所有目標(biāo)值都不大于解q的目標(biāo)值且至少存在一個(gè)目標(biāo)值小于解q的目標(biāo)值，則稱p支配q(pq)。

定義si為鳥群中被個(gè)體i支配的個(gè)體集合，zi為鳥群中支配個(gè)體i的個(gè)體數(shù)量。

基于上述定義，提出一種快速非支配排序算法，具體步驟如下：

(1)將種群中不被其他個(gè)體支配的個(gè)體標(biāo)記為第1級(jí)非支配前端F1；

(2)F1中的個(gè)體p支配的個(gè)體集合為sp，對(duì)于sp中的個(gè)體q，將支配q的個(gè)體數(shù)zq減1即zq←zq-1后，若zq=0即不存在可以支配q的其他個(gè)體，則將q保存至集合Q中。對(duì)F1的每個(gè)支配個(gè)體集合中的全部個(gè)體執(zhí)行上述操作后，將最終得到的集合Q作為鳥群的第2級(jí)非支配前端F2；

(3)遍歷F2中的個(gè)體，參照步驟(2)中的操作，找到第3級(jí)非支配前端F3。以此類推，直到種群中的每一個(gè)個(gè)體都分配到對(duì)應(yīng)的非支配前端等級(jí)。

通過基于Pareto思想的快速非支配排序算法將鳥群分為不同等級(jí)，等級(jí)越低說明該個(gè)體越優(yōu)。

2.1.2基于參考點(diǎn)的選擇算子

基于參考點(diǎn)的選擇算子首先在目標(biāo)空間內(nèi)采用單層參考點(diǎn)生成法[13]得到均勻分布的多個(gè)參考點(diǎn)，即將A個(gè)目標(biāo)均勻劃分成H份，然后根據(jù)參考點(diǎn)依附的個(gè)體數(shù)量選擇較優(yōu)個(gè)體，具體流程如下：

(8)

然后通過下式歸一化鳥群個(gè)體的目標(biāo)值：

(9)

歸一化鳥群個(gè)體的目標(biāo)值后，此時(shí)理想點(diǎn)變?yōu)樵c(diǎn)，然后將理想點(diǎn)與各參考點(diǎn)的連線作為參考線，計(jì)算歸一化后的目標(biāo)點(diǎn)與所有參考線的距離，選擇最近的參考線作為個(gè)體依附對(duì)象；

(10)

最后依次遍歷鳥群個(gè)體，統(tǒng)計(jì)每個(gè)參考點(diǎn)的依附個(gè)體數(shù)量即該參考點(diǎn)的小生境數(shù)。在MOMBO算法鳥群進(jìn)化操作時(shí)，對(duì)于同一級(jí)非支配前端中的個(gè)體集合，優(yōu)先選擇小生境數(shù)更少的個(gè)體，保證算法的多樣性。

2.2 多目標(biāo)候鳥優(yōu)化算法的主要步驟

2.2.1編碼

運(yùn)用MOMBO算法求解MOFJSP時(shí)首先要解決編碼問題，即將FJSP的潛在解轉(zhuǎn)換至可被MOMBO算法搜索的空間中。本算法采用二段式編碼規(guī)則[14]，將解分為機(jī)器選擇(machine selection，MS)和工序排序(operation sequence，OS)兩部分。MS按工件的工序順序依次排列，每個(gè)位置的數(shù)值為該道工序選擇的加工機(jī)器號(hào)；OS中，每個(gè)位置的數(shù)值為工件號(hào)，從左往右遍歷OS，同一工件號(hào)出現(xiàn)第j次數(shù)表示對(duì)應(yīng)工件的第j道工序。MS和OS如圖2所示。

圖2 二段式編碼示意圖

2.2.2解碼

解碼則是將解空間轉(zhuǎn)換為問題空間。本算法采用貪婪插入式解碼法[15]，以保證每道工序在所選加工機(jī)器上盡可能早地開始，對(duì)于前插的工序，它在OS上的位置也要相應(yīng)調(diào)整。

2.2.3鳥群初始化

初始化是車間調(diào)度問題的一個(gè)重要步驟，它生成解集的好壞對(duì)算法的收斂性和多樣性有很大的影響。為保證初始解的質(zhì)量和多樣性，本文分別對(duì)機(jī)器選擇和工序排序采用多種初始化規(guī)則。

2.2.3.1 MS初始化規(guī)則

(1)改進(jìn)的全局選擇規(guī)則[16]。設(shè)定一個(gè)初始值為0的機(jī)器負(fù)荷數(shù)組，從工件集合中隨機(jī)選擇一個(gè)工件，從該工件的工序中隨機(jī)選擇一個(gè)工序，將該工序的可選機(jī)器加工時(shí)間與機(jī)器負(fù)荷數(shù)組的已有負(fù)荷相加，得到臨時(shí)機(jī)器負(fù)荷數(shù)組。從臨時(shí)機(jī)器負(fù)荷數(shù)組中選擇臨時(shí)負(fù)荷最小的機(jī)器作為該工序的加工機(jī)器；若臨時(shí)負(fù)荷最小的機(jī)器不只一個(gè)，則選擇加工時(shí)間最短的機(jī)器作為該工序的加工機(jī)器；更新機(jī)器負(fù)荷數(shù)組。當(dāng)前工件的所有工序選擇完加工機(jī)器后，隨機(jī)選擇下一個(gè)工件，依次類推，直到所有工件的工序都選擇完機(jī)器。

(2)改進(jìn)的局部選擇規(guī)則[16]。設(shè)定一個(gè)初始值為0的機(jī)器負(fù)荷數(shù)組，從工件集合中依次選擇一個(gè)工件，從該工件的工序集合中隨機(jī)選擇一個(gè)工序，將該工序的可選機(jī)器加工時(shí)間與機(jī)器負(fù)荷數(shù)組的已有負(fù)荷進(jìn)行相加，得到臨時(shí)機(jī)器負(fù)荷數(shù)組。從臨時(shí)機(jī)器負(fù)荷數(shù)組中選擇臨時(shí)負(fù)荷最小的機(jī)器作為該工序的加工機(jī)器；若臨時(shí)負(fù)荷最小的機(jī)器不只一個(gè)，則選擇加工時(shí)間最短的機(jī)器作為該工序的加工機(jī)器；更新機(jī)器負(fù)荷數(shù)組。當(dāng)前工件的所有工序選擇完加工機(jī)器后，將機(jī)器負(fù)荷數(shù)組重新置0，選擇下一個(gè)工件，依次類推，直到所有工件的工序都選擇完機(jī)器。

(3)隨機(jī)選擇。在加工工序的可選機(jī)器中隨機(jī)選擇一臺(tái)機(jī)器進(jìn)行加工。

2.2.3.2 OS初始化規(guī)則

(1)剩余負(fù)荷最大規(guī)則[17]。將工件按剩余工序加工時(shí)間總和進(jìn)行降序排列，優(yōu)先加工剩余加工時(shí)間長(zhǎng)的工件。

(2)最短加工時(shí)間規(guī)則[18]。將工序按照加工時(shí)間升序排列，優(yōu)先完成加工時(shí)間短的工序。

(3)隨機(jī)選擇。隨機(jī)選擇工序進(jìn)行加工。

參考文獻(xiàn)[16，19]，首先按照鳥總數(shù)(即個(gè)體總數(shù))4∶4∶2的比例，分別通過改進(jìn)的全局選擇規(guī)則、改進(jìn)的局部選擇規(guī)則和隨機(jī)選擇規(guī)則生成初始鳥群的MS，再按照上述比例生成初始鳥群的OS。

初始化之后，按如下步驟將鳥群分為領(lǐng)飛鳥和左右跟飛鳥群：首先根據(jù)基于Pareto支配的選擇算子進(jìn)行非支配排序，找到初始種群中的非支配解集；然后通過基于參考點(diǎn)的選擇算子，選擇小生境數(shù)最小的非支配解作為領(lǐng)飛鳥，若小生境數(shù)最小的非支配解有多個(gè)，則隨機(jī)選擇一個(gè)作為領(lǐng)飛鳥，并將剩下個(gè)體按非支配等級(jí)均勻分為左右跟飛鳥群。

2.2.4鳥群進(jìn)化

首先定義三種鄰域結(jié)構(gòu)：

N1：隨機(jī)產(chǎn)生i(i=2，3，4)個(gè)變異工序。將i個(gè)工序順序重新排列組合，然后計(jì)算不同排列組合的目標(biāo)值，通過上文中的兩種選擇算子選擇其中最好的新解作為鄰域解。

N2：基于工序變異，交換兩個(gè)不同工件的任意工序位置。

N3：基于機(jī)器變異，隨機(jī)選擇兩個(gè)變異工件，并在這兩個(gè)變異工件上分別隨機(jī)選擇一道工序，在不考慮原加工機(jī)器的情況下，重新選擇這兩道工序加工時(shí)間最短的機(jī)器。

基于上述3種鄰域結(jié)構(gòu)，增加鳥群個(gè)體的局部尋優(yōu)能力，鳥群進(jìn)化具體步驟如下。

2.2.4.1 領(lǐng)飛鳥進(jìn)化

按上述3種鄰域結(jié)構(gòu)產(chǎn)生領(lǐng)飛鳥的3個(gè)鄰域解后，將領(lǐng)飛鳥與3個(gè)鄰域解合并作為進(jìn)化解集，接著從該進(jìn)化解集中選擇1個(gè)個(gè)體作為新的領(lǐng)飛鳥，具體的選擇規(guī)則如下：①若鄰域解支配領(lǐng)飛鳥，則替換領(lǐng)飛鳥；②若領(lǐng)飛鳥支配鄰域解，則不替換；③若領(lǐng)飛鳥與鄰域解互不支配，則進(jìn)行領(lǐng)飛鳥選擇，具體的領(lǐng)飛鳥選擇操作如下。

首先將原鳥群中的進(jìn)化個(gè)體剔除，計(jì)算剔除進(jìn)化個(gè)體后的鳥群的小生境數(shù)；然后找出具有最小小生境數(shù)的參考點(diǎn)集J，遍歷J中的每個(gè)參考點(diǎn)。假設(shè)Ja是J中的一個(gè)參考點(diǎn)，判斷進(jìn)化解集(包括進(jìn)化個(gè)體、進(jìn)化個(gè)體的鄰域解)的非支配解集中是否有個(gè)體依附于參考點(diǎn)Ja，若進(jìn)化解集的非支配解集中沒有個(gè)體依附于參考點(diǎn)Ja，則將參考點(diǎn)Ja的小生境數(shù)ρa(bǔ)設(shè)為無窮大。若進(jìn)化解集的非支配解集中有個(gè)體依附于參考點(diǎn)Ja，則進(jìn)一步判斷ρa(bǔ)是否為0，若ρa(bǔ)為0，則從進(jìn)化解集的非支配解集中依附Ja的個(gè)體中將與參考點(diǎn)Ja對(duì)應(yīng)參考線距離最短的個(gè)體作為新的領(lǐng)飛鳥加入鳥群；若ρa(bǔ)不為0，則在進(jìn)化解集的非支配解集中隨機(jī)選擇1個(gè)依附該參考點(diǎn)的個(gè)體作為新的領(lǐng)飛鳥加入鳥群。進(jìn)化過程中選擇領(lǐng)飛鳥的流程如圖3所示。

圖3 進(jìn)化過程中基于參考點(diǎn)的選擇算子流程圖

更新完領(lǐng)飛鳥之后，選擇一個(gè)次優(yōu)解作為第一個(gè)跟飛鳥的共享解，以增強(qiáng)跟飛鳥群的尋優(yōu)能力。次優(yōu)解的選擇過程如下：判斷進(jìn)化解集中剩余個(gè)體的非支配等級(jí)，選擇非支配等級(jí)最低的個(gè)體作為次優(yōu)解；若非支配等級(jí)最低的個(gè)體數(shù)大于1，則比較其依附參考點(diǎn)在鳥群中的小生境數(shù)，優(yōu)先選擇小生境數(shù)更小的個(gè)體，若小生境數(shù)相同，則隨機(jī)選擇一個(gè)體作為次優(yōu)解。

2.2.4.2 跟飛鳥進(jìn)化

跟飛鳥進(jìn)化包括對(duì)左右跟飛鳥群的進(jìn)化，即首先將領(lǐng)飛鳥進(jìn)化解集中的次優(yōu)解作為左右跟飛鳥群中第一只跟飛鳥的共享解，將共享解與生成的3個(gè)鄰域解組成該跟飛鳥的進(jìn)化解集。然后，選擇進(jìn)化解集中的最優(yōu)解作為新的跟飛鳥，同時(shí)將進(jìn)化解集中的次優(yōu)解作為下一只跟飛鳥的共享解，替換跟飛鳥和選擇次優(yōu)解規(guī)則與上文中領(lǐng)飛鳥的進(jìn)化過程相同。按上述步驟依次遍歷所有跟飛鳥，完成跟飛鳥的進(jìn)化。

2.2.5跟飛鳥交叉

每次對(duì)左右跟飛鳥群執(zhí)行完進(jìn)化操作后，從左右跟飛鳥群中隨機(jī)選擇Cr(Cr為交叉?zhèn)€數(shù))對(duì)個(gè)體，并對(duì)每對(duì)個(gè)體依次進(jìn)行交叉操作。

MS、OS的交叉操作分別采用均勻交叉策略和POX(precedence operation crossover)交叉策略[15]。MS的均勻交叉策略是：隨機(jī)產(chǎn)生一個(gè)長(zhǎng)度為工序總數(shù)的0、1數(shù)組，交換父代數(shù)字1對(duì)應(yīng)位的機(jī)器號(hào)，產(chǎn)生2個(gè)新的子代。OS的POX交叉策略是：首先將工件隨機(jī)地分為子集合J1和J2；然后將父代1中J1部分的工件號(hào)復(fù)制到子代1對(duì)應(yīng)位置，將父代2中J2部分的工件號(hào)復(fù)制到子代2中對(duì)應(yīng)位置；最后將父代2中J2部分的工件號(hào)按順序依次填入子代1中的剩余位，將父代1中J1部分的工件號(hào)按順序依次填入子代2中的剩余位。MS交叉如圖4所示，OS交叉如圖5所示。

圖4 MS均勻交叉圖

圖5 OS POX交叉圖

2.2.6篩選個(gè)體產(chǎn)生新鳥群

個(gè)體交叉生成子代鳥群Q后，將子代加入至原鳥群Y(數(shù)量為n)中，將Q和Y合并為R，對(duì)R重新進(jìn)行非支配排序，在非支配解集中隨機(jī)選擇小生境數(shù)最小的個(gè)體作為新鳥群S的領(lǐng)飛鳥，同時(shí)更新S的小生境數(shù)；然后按照非支配層等級(jí)由低到高將每層個(gè)體加入至S中，直至S的數(shù)量等于n；若S的飛鳥數(shù)量大于n，則需要重新在最后一層非支配層中通過基于參考點(diǎn)的選擇算子選擇一定數(shù)量個(gè)體保留在S中，未被選擇個(gè)體則剔除出S，使S的數(shù)量等于n。新鳥群生成如圖6所示。

圖6 新鳥群生成圖

生成新鳥群之后，若未達(dá)到最大迭代次數(shù)，則返回至鳥群進(jìn)化階段進(jìn)行下一次迭代；若達(dá)到最大迭代次數(shù)，則將新鳥群的非支配解集作為最終優(yōu)化結(jié)果輸出。

2.2.7基于AHM和灰色關(guān)聯(lián)度分析法的組合權(quán)重決策

實(shí)際生產(chǎn)需要選擇一個(gè)確定的方案。MOMBO最終的非支配解集可能存在多個(gè)解，本節(jié)采用組合賦權(quán)法進(jìn)行方案選擇。組合賦權(quán)是主觀賦權(quán)和客觀賦權(quán)的線性加權(quán)，其中，主觀賦權(quán)采用屬性層次模型，客觀賦權(quán)采用灰色關(guān)聯(lián)度分析法。

(1)屬性層次模型(attribute hierarchical model，AHM)先將各個(gè)指標(biāo)劃分為相互關(guān)聯(lián)的有序結(jié)構(gòu)，再結(jié)合專家的主觀意見和分析者的判斷來確定指標(biāo)權(quán)重?；贏HM 的權(quán)重計(jì)算方法如下：

①建立判斷矩陣A=[aij]，比較同一等級(jí)指標(biāo)之間的重要性，其中，aij=1/aji(i≠j)，aii=1。

②設(shè)μ=[μij]為測(cè)度矩陣，μij是由aij換算而成的測(cè)度指標(biāo)，令

(11)

k=1，2，…

這里設(shè)置β=1。

③計(jì)算指標(biāo)權(quán)重。指標(biāo)主觀權(quán)重向量Wa=(w1，w2，…，wm)按下式計(jì)算：

(12)

其中，w1+w2+…+wm=1且0≤wi≤1。

(2)灰色關(guān)聯(lián)度分析(gray relation analysis，GRA)法的思想是：先根據(jù)某個(gè)問題的實(shí)際情況確定理想的最優(yōu)序列；然后，通過方案的序列曲線和幾何形狀與理想最優(yōu)序列的曲線和幾何形狀的相似程度來判斷方案的序列與理想最優(yōu)序列之間的關(guān)聯(lián)程度，曲線和幾何形狀越接近說明關(guān)聯(lián)度越大，方案越接近理想最優(yōu)，則該方案的權(quán)重越大。GRA的主要步驟如下：

①數(shù)據(jù)規(guī)范化處理。假設(shè)有n個(gè)方案，每個(gè)方案有m個(gè)目標(biāo)值，首先對(duì)各個(gè)指標(biāo)進(jìn)行規(guī)范化處理，規(guī)范化處理計(jì)算式為

(13)

②由下式計(jì)算灰色關(guān)聯(lián)系數(shù)：

(14)

灰色關(guān)聯(lián)系數(shù)反映yij與理想值之間的關(guān)聯(lián)程度。

③權(quán)重計(jì)算。根據(jù)灰色關(guān)聯(lián)系數(shù)矩陣計(jì)算得到客觀權(quán)重向量Wb，其中，第j個(gè)目標(biāo)的權(quán)重為

(15)

(16)

(3)綜合權(quán)重確定。將AHM得出的權(quán)重Wa與灰色關(guān)聯(lián)度分析法的權(quán)重Wb結(jié)合，求得綜合權(quán)重：

w*=θWa+(1-θ)Wb

(17)

其中，θ為主觀偏重系數(shù)，θ∈[0，1]，由決策者依據(jù)偏好給出。組合賦權(quán)法既能充分利用專家長(zhǎng)期積累的生產(chǎn)加工經(jīng)驗(yàn)，使結(jié)果更貼近實(shí)際生產(chǎn)，又能在一定程度上從數(shù)據(jù)本身特性來確定其重要性。

3 性能測(cè)試與案例研究

為驗(yàn)證本算法的有效性，首先將MOMBO分別與三個(gè)變體、NSGAⅡ及NSGAⅢ的最終解集進(jìn)行對(duì)比，然后通過仿真對(duì)MOMBO求得的非支配解集進(jìn)行分析。本節(jié)所有算法均由MATLAB R2014實(shí)現(xiàn)，MATLAB在Intel i5-8300H、內(nèi)存8.00 GB的計(jì)算機(jī)上運(yùn)行。

3.1 算法性能測(cè)試

本小節(jié)通過10個(gè)BRdata測(cè)試問題[20]來驗(yàn)證MOMBO的性能，將測(cè)試問題的加工時(shí)間作為本調(diào)度問題中各個(gè)工序的基本加工時(shí)間，算例的其他數(shù)據(jù)如交貨期、機(jī)器加工功率、空載功率等數(shù)據(jù)如表1所示。

表1 算例數(shù)據(jù)

多目標(biāo)優(yōu)化算法的解集有多種評(píng)價(jià)指標(biāo)，本文采用的評(píng)價(jià)指標(biāo)是反向世代距離(inverted generational distance，IGD)[21]和超體積(hypervolume，HV)[22]。

IGD能綜合評(píng)價(jià)解集的收斂性和多樣性，其計(jì)算公式為

(18)

其中，P*為一組理想解集，本文設(shè)定為所有算法多次運(yùn)算后得到的全部解中的非支配解集；|P*|為解集P*中解的個(gè)數(shù)；x為解集P*中的某個(gè)解；解集P是某算法求出的該前沿面的一個(gè)近似解集，y是解集P中的某個(gè)解；d(x，y)為解x和y在目標(biāo)空間中的歐氏距離。IGD值越小，算法性能越好。

超體積能綜合反映解集的收斂性和多樣性，其計(jì)算公式為

(19)

其中，解集P是Pareto前沿面的近似解集；fm為解集P中某個(gè)非支配解f=(f1，f2，…，fm)T的第m個(gè)目標(biāo)值；r=(r1，r2，…，rm)T為目標(biāo)空間中的一個(gè)參考向量，它被解集P中所有目標(biāo)向量支配；volume(*)表示近似Pareto前沿面與參考向量所圍成的超立方體的超體積。那么關(guān)于參考向量r的超體積指的是被解集P所支配且以參考向量r為邊界的目標(biāo)空間的體積。

將超體積定義為被解集P所支配且以參考點(diǎn)r為邊界的目標(biāo)空間的體積，HV(P，r)越大，算法性能越好。對(duì)于4個(gè)目標(biāo)的柔性作業(yè)車間調(diào)度問題，本文采用BADER等[23]提出的蒙特卡羅模擬方法計(jì)算HV(P，r)。

3.1.1MOMBO與MOMBO變體的比較

為驗(yàn)證所做改進(jìn)對(duì)MOMBO算法性能的影響，構(gòu)建以下幾種變體類型：

MOMBO1：采用半主動(dòng)解碼。

MBMBO2：種群初始化階段采用隨機(jī)初始化方式。

MOMBO3：飛鳥進(jìn)化過程僅采用N1鄰域結(jié)構(gòu)產(chǎn)生鄰域解。

MOMBO算法參數(shù)設(shè)置如表2所示。多次運(yùn)行MOMBO及其3種變體，求得多個(gè)近似解集，然后計(jì)算IGD值和HV值，最終取平均值進(jìn)行對(duì)比，結(jié)果如表3所示，其中，最優(yōu)的結(jié)果用加粗?jǐn)?shù)字表示。由表3可知，除了算例MK04和MK05，MOMBO算法的IGD值、HV值都優(yōu)于3種變體算法，由此可知基于MBO算法提出的貪婪插入式解碼法、改進(jìn)的多種初始化規(guī)則，以及改進(jìn)的鄰域搜索策略在大部分情況下更適用于高維多目標(biāo)柔性作業(yè)車間調(diào)度模型。

表2 MOMBO參數(shù)設(shè)置

表3 MOMBO及其變體的IGD、HV

3.1.2MOMBO與NSGAⅡ、NSGAⅢ的比較

NSGAⅡ、NSGAⅢ的參數(shù)設(shè)置如表4所示。多次運(yùn)行MOMBO、NSGAⅡ和NSGAⅢ，求得多個(gè)近似解集，然后計(jì)算IGD值和HV值，最終取平均值進(jìn)行對(duì)比，結(jié)果如表5所示，其中，最優(yōu)的結(jié)果用加粗?jǐn)?shù)字表示。由表5可知，MOMBO的IGD值和HV值都顯著優(yōu)于NSGAⅡ和NSGAⅢ，驗(yàn)證了MOMBO求解該問題的有效性。

表4 NSGAⅡ、NSGAⅢ的參數(shù)設(shè)置

表5 MOMBO、NSGAⅡ和NSGAⅢ的IGD、HV

3.1.3算法收斂性分析

為驗(yàn)證算法運(yùn)行過程中的收斂性，繪制MOMBO、3種變體、NSGAⅡ和NSGAⅢ的HV值隨迭代次數(shù)變化的進(jìn)化軌跡圖。由圖7可以看出，6種算法的HV值都隨著迭代次數(shù)的增大而增大，這意味著它們的收斂性能穩(wěn)定；MOMBO每代的HV值在MK08、MK09算例上遠(yuǎn)大于其他算法的HV值，說明MOMBO的進(jìn)化效果最好；MOMBO2、NSGAⅡ、NSGAⅢ的HV值明顯小于MOMBO、MOMBO1、MOMBO的HV值，這說明本文提出的多種初始化方式是有效的。接下來考慮非支配解集占比情況，MOMBO求解MK01的初始解集中，非支配等級(jí)共有5層，其中，非支配解集占所有解集的比例為28.6%；MOMBO求解MK01的最終解集的非支配等級(jí)為4層，其中，非支配解集占所有解集的68.6%。這說明所提出的兩種選擇算子能給予算法有效的進(jìn)化壓力，能有效促進(jìn)算法的收斂。

(a)MK04 (b)MK08 (c)MK09

3.2 實(shí)例研究

為驗(yàn)證本文算法在實(shí)際生產(chǎn)加工中的效果，在某工廠進(jìn)行加工實(shí)驗(yàn)。實(shí)驗(yàn)內(nèi)容是，5臺(tái)加工機(jī)器上加工4個(gè)工件，通過Precision Power Analyzer LMG671收集機(jī)床加工工件過程中的功率。對(duì)得到的數(shù)據(jù)進(jìn)行預(yù)處理，獲得每臺(tái)機(jī)器的加工功率和空載功率曲線圖。為方便計(jì)算，通過取均值求得各機(jī)器的加工功率和空載功率。車間固有功率為2kW，每個(gè)工件的交貨期和加工時(shí)間如表6所示，其中，“-”表示該工序不能在此機(jī)器上完成。

表6 實(shí)驗(yàn)數(shù)據(jù)

3.2.1MOMBO與單目標(biāo)MBO的比較

通過MOMBO算法求得Pareto前沿解集，如表7所示。通過MBO算法分別求解出以最大完工時(shí)間f1、總拖期f2、機(jī)器最大負(fù)荷f3、總能耗f4為目標(biāo)的單目標(biāo)最優(yōu)解，如表8所示。觀察表8可以發(fā)現(xiàn)，雖然單目標(biāo)最優(yōu)解在某個(gè)目標(biāo)值上最優(yōu)，但其他3個(gè)目標(biāo)值較差，單目標(biāo)最優(yōu)解與通過MOMBO算法求出的最優(yōu)解集中的某個(gè)解的目標(biāo)值之差即Δf1～Δf4如表9所示。由表9可見，在MOMBO求出的最優(yōu)解集中，總能找出優(yōu)于單目標(biāo)最優(yōu)解的解，因此通過MOMBO求出的最優(yōu)解集相對(duì)于單目標(biāo)最優(yōu)解具有更好的質(zhì)量。

表7 實(shí)例Pareto前沿解集

表8 實(shí)例單目標(biāo)最優(yōu)解

表9 單目標(biāo)最優(yōu)解與多目標(biāo)最優(yōu)解的目標(biāo)值之差

3.2.2MOMBO與NSGAⅡ、NSGAⅢ的比較

NSGAⅡ、NSGAⅢ求得的最優(yōu)解集分別如表10、表11所示。對(duì)比表7可以看出，MOMBO求出的最優(yōu)解大部分都優(yōu)于NSGAⅡ、NSGAⅢ求得的解。為進(jìn)一步對(duì)比MOMBO與NSGAⅡ、NSGAⅢ的收斂性和多樣性，通過式(18)、式(19)求得3種算法的IGD值和HV值，如表12所示。在求解過程中，本文設(shè)定P*為三種算法多次運(yùn)算后得到的非支配解集。如表12所示，對(duì)于本實(shí)例，MOMBO取得了優(yōu)于另外2個(gè)算法的結(jié)果。

表10 NSGAⅡ的實(shí)例Pareto前沿解集

表11 NSGAⅢ的實(shí)例Pareto前沿解集

表12 MOMBO、NSGAⅡ和NSGAⅢ求解實(shí)例的結(jié)果

圖8、圖9所示為3種算法求解實(shí)例的HV值和IGD值隨迭代次數(shù)的進(jìn)化曲線。3種算法的HV值都隨著迭代次數(shù)的增大而增大，IGD值均隨著迭代次數(shù)的增大而減小，這說明它們的收斂性能穩(wěn)定。本文提出的MOMBO的HV值大于另外兩種算法的HV值，IGD值小于另外兩種算法的IGD值，因此MOMBO的進(jìn)化效果最好。

圖8 3種算法求解實(shí)例所得HV值隨迭代次數(shù)的進(jìn)化軌跡

圖9 3種算法求解實(shí)例所得IGD值隨迭代次數(shù)的進(jìn)化軌跡

3.2.3基于組合權(quán)重法的最優(yōu)方案決策

首先根據(jù)專家對(duì)不同目標(biāo)的打分情況建立AHM需要的判斷矩陣，然后通過計(jì)算得到各個(gè)目標(biāo)的主觀權(quán)重向量Wa=(0.264，0.361，0.264，0.111)；接著根據(jù)表7中的Pareto前沿解集計(jì)算出灰色關(guān)聯(lián)度分析法的各個(gè)數(shù)據(jù)：

Wb=(0.261，0.189，0.281，0.269)

進(jìn)一步取θ=0.5，求得綜合權(quán)重w*=(0.263，0.275，0.272，0.190)。由于本文是逆指標(biāo)，故需要對(duì)y采用減法一致法處理得到y(tǒng)′，即利用每一列的最大值Mj依次減去該列的原始數(shù)據(jù)，然后將y′×w*，得到最終得分矩陣：

由R可知第二組方案的得分最高，其加工時(shí)間為53.42 s，拖期為0 s，機(jī)器負(fù)載為178.50 s，總能耗為364 681 J。圖10為按第二個(gè)調(diào)度方案加工的甘特圖。

圖10 解2的甘特圖

4 結(jié)論

本文提出以最小化最大完工時(shí)間、總拖期、機(jī)器總負(fù)荷、總能耗為目標(biāo)的高維多目標(biāo)柔性作業(yè)車間調(diào)度模型，并運(yùn)用一種MOMBO進(jìn)行求解。算法性能測(cè)試表明MOMBO相對(duì)于其3種變體以及NSGAⅡ、NSGAⅢ來說，其最優(yōu)解集在IGD和HV兩種性能指標(biāo)上表現(xiàn)更優(yōu)。實(shí)例研究證明本文提出的MOMBO算法相對(duì)于單目標(biāo)MBO算法、NSGAⅡ和NSGAⅢ有著更好的解集質(zhì)量，在實(shí)際生產(chǎn)加工中能夠給予決策者更好的選擇。