宋昌興，阮景奎，王 宸

(湖北汽車工業(yè)學(xué)院 機(jī)械工程學(xué)院，湖北 十堰 442002)

0 引 言

車間生產(chǎn)調(diào)度是一種有效的調(diào)度方法與優(yōu)化技術(shù)，企業(yè)在生產(chǎn)加工制造過(guò)程中對(duì)生產(chǎn)計(jì)劃的合理編排，對(duì)提升企業(yè)生產(chǎn)效率、資源利用率、降低成本等起著關(guān)鍵作用。柔性作業(yè)車間調(diào)度問(wèn)題(fle-xible job scheduling problem，F(xiàn)JSP)相比傳統(tǒng)的作業(yè)車間調(diào)度問(wèn)題引入了新的決策內(nèi)容，包括對(duì)兩個(gè)子問(wèn)題的求解：一是為每道工序選擇合適的機(jī)器，二是確定工序在機(jī)器上的起止加工時(shí)間，是更復(fù)雜的NP-hard問(wèn)題[1]。

經(jīng)過(guò)近30年的探索，F(xiàn)JSP的研究取得了豐碩的成果。以遺傳算法[2]、粒子群算法[3]、禁忌搜索算法[4]、模擬退火算法[5]等為代表的元啟發(fā)式算法，在實(shí)際調(diào)度問(wèn)題中都得到了成功的應(yīng)用。

隨著研究的深入，更加符合生產(chǎn)實(shí)際的多目標(biāo)柔性作業(yè)車間調(diào)度(multi-objective FJSP，MO-FJSP)成為目前亟待解決的問(wèn)題，近年來(lái)許多新算法的不斷涌現(xiàn)，也為解決MO-FJSP提供了更多的選擇方案。孟冠軍等[6]提出了混合人工蜂群算法，在雇傭蜂、跟隨蜂、偵查蜂3個(gè)階段分別采用了不同的搜索方式，并引入禁忌搜索算法提升了獲得最優(yōu)解的概率;王英彥等[7]提出了改進(jìn)的人工免疫算法，采用了模擬退火算法的Metropolis準(zhǔn)則，在保證了種群多樣性的同時(shí)加快搜索效率；王思涵等[8]提出了改進(jìn)的鯨魚(yú)群算法，采用了協(xié)同搜索機(jī)制擴(kuò)大鯨魚(yú)個(gè)體的搜索范圍，同時(shí)引入了變鄰域搜索算法，提高了種群全局及局部搜索能力；曹磊等[9]提出了變鄰域雜草優(yōu)化算法，建立了具有Dejong學(xué)習(xí)效應(yīng)的調(diào)度模型，在迭代后期引入了N1、N2、N3 3種鄰域結(jié)構(gòu)的變鄰域搜索算法，并通過(guò)實(shí)驗(yàn)對(duì)算法的有效性進(jìn)行了驗(yàn)證。

近年來(lái)的研究表明，針對(duì)單一算法的不足，混合算法將兩種及以上算法的特性進(jìn)行互補(bǔ)，相比單一算法具有更優(yōu)的適應(yīng)性和魯棒性，是研究和解決MO-FJSP的重要方向。

本文將在非支配排序遺傳算法的基礎(chǔ)上引入和聲搜索算法(harmony search，HS)，提出一種混合多目標(biāo)遺傳算法(HMO-NSGA-II)，并通過(guò)實(shí)驗(yàn)證明所提算法的可行性、有效性和實(shí)用性。

1 多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題

1.1 問(wèn)題描述

FJSP可描述為：有n個(gè)工序順序已知的工件J={J1,J2,…,Jn}和m臺(tái)不同機(jī)器M={M1,M2,…,Mm}，其中工件Ji的每道工序Oij可在相應(yīng)的可選機(jī)器集Mij中任意選擇1臺(tái)機(jī)器進(jìn)行加工，且選擇不同機(jī)器對(duì)應(yīng)的加工時(shí)間可能不同。

在實(shí)際生產(chǎn)調(diào)度過(guò)程中，常會(huì)對(duì)多個(gè)不同的目標(biāo)進(jìn)行優(yōu)化，如最大完工時(shí)間、生產(chǎn)成本、總拖期時(shí)間、機(jī)器總負(fù)荷、瓶頸機(jī)器負(fù)荷等。MO-FJSP的求解即在滿足時(shí)間、資源等約束條件下，采用最優(yōu)化方法合理解決機(jī)器分配和工序排列2個(gè)子問(wèn)題，分配各工序在機(jī)器上加工的起止時(shí)間，并實(shí)現(xiàn)對(duì)多個(gè)給定性能指標(biāo)的優(yōu)化，最終得到1組非劣調(diào)度方案。

1.2 數(shù)學(xué)模型

本文選擇以下3個(gè)具有實(shí)際應(yīng)用價(jià)值的目標(biāo)，以降低機(jī)器生產(chǎn)負(fù)荷、縮短加工產(chǎn)品完工時(shí)間，從而提高生產(chǎn)效率。

(1)最大完工時(shí)間最短：

f1=min(max(Ci))

(1)

(2)最大瓶頸機(jī)器負(fù)荷最?。?/p>

(2)

(3)最大機(jī)器負(fù)荷最?。?/p>

(3)

式中：Ci—工件Ji的完工時(shí)間；n—工件總數(shù)；ni—工件i的總工序數(shù)；m—機(jī)器總數(shù)；Pijk—工件i的第j道工序在機(jī)器k上的加工時(shí)間；Xijk—判斷工件i的第j道工序是否在機(jī)器k上加工，是則取1，否則取0。

1.3 約束條件

一般的，在調(diào)度過(guò)程中MO-FJSP模型應(yīng)滿足以下約束條件[10，11]：

(1)所有設(shè)備在t0時(shí)刻均可用；

(2)不同工件的加工優(yōu)先級(jí)相同，一旦開(kāi)始加工便不可中斷；

(3)同工件的不同工序之間，需滿足工藝先后順序約束，即：

Sij+PijkXijk≤Si(j+1)

(4)

(4)同時(shí)刻，同一臺(tái)機(jī)器只能加工某工件的某一道工序，即：

Sij+Pijk≤Shl+L(1-yijhlk)

(5)

Cij≤Si(j+1)+L(1-yiji(j+1)k)

(6)

(5)同時(shí)刻，同一個(gè)工件的同一工序能且只能被一臺(tái)機(jī)器加工，即：

(7)

式中：Sij—工件i的第j道工序開(kāi)始加工的時(shí)間；Pijk—工件i的第j道工序在機(jī)器k上的加工時(shí)間；Xijk—判斷工件i的第j道工序是否在機(jī)器k上加工，是則取1，否則取0；Si(j+1)—工件i的第j+1道工序開(kāi)始加工的時(shí)間；Shl—工件h的第l道工序開(kāi)始加工的時(shí)間；L—足夠大的正數(shù)；yijhlk—判斷在同機(jī)器k上，工件i的第j道工序較工件h的第l道工序是否先加工，若是值為1，否則為0；Cij為工件i的第j道工序停止加工的時(shí)間；yiji(j+1)k—在同機(jī)器k上，工件i的第j道工序較工件i的第j+1道工序是否先加工，若是值為1，否則為0。

2 混合多目標(biāo)遺傳算法設(shè)計(jì)

NSGA-II在求解MO-FJSP上應(yīng)用廣泛，但由于交叉、變異操作以及精英策略等自身的局限性，在求解收斂速度以及保持種群多樣性等方面存在缺陷。和聲搜索算法實(shí)現(xiàn)原理簡(jiǎn)單，易于與其他算法結(jié)合，在新解的產(chǎn)生上能夠全面利用存在的解向量，有效保證了種群的多樣性，但比較依賴好的初始解。

因此，本文以NSGA-II為主體，把每代經(jīng)過(guò)自適應(yīng)交叉變異以及改進(jìn)的精英保留策略等操作所得到的種群精英庫(kù)，作為和聲搜索算法的和聲記憶庫(kù)，并通過(guò)改進(jìn)的和聲搜索算法提高精英庫(kù)種群質(zhì)量，加快引導(dǎo)種群向pareto最優(yōu)前沿收斂。

2.1 編碼與解碼

針對(duì)求解MO-FJSP，本文采用基于機(jī)器、工序雙層編碼的方式，以對(duì)應(yīng)機(jī)器分配和工序排列2個(gè)子問(wèn)題。以一個(gè)4×5的部分柔性作業(yè)車間調(diào)度問(wèn)題(partial FJSP，P-FJSP)為例，工件1有3道工序，工件2-4分別有2道工序，各工件每道工序?qū)?yīng)的可選機(jī)器集Mij為5臺(tái)機(jī)器中的部分機(jī)器。編碼的長(zhǎng)度等于各加工工件工序總數(shù)之和，工序編碼部分為所有工序的一種排列，數(shù)字代表工件號(hào)，出現(xiàn)的次數(shù)代表相應(yīng)工序，接著為每道工序從可選機(jī)器集中分配加工機(jī)器組成機(jī)器編碼。

基于機(jī)器、工序的雙層編碼過(guò)程如圖1所示。

圖1 基于機(jī)器、工序的雙層編碼過(guò)程

解碼采用插入式貪婪解碼方法，將個(gè)體編碼轉(zhuǎn)換為調(diào)度甘特圖。

加工起始時(shí)間計(jì)算如下式所示：

ta=max(Ci(j-1),TSkr)

(8)

ta+Pijk≤TEkr

(9)

tb=max(Ci(j-1),LMk)

(10)

式中：ta—工序的加工起始時(shí)間；Ci(j-1)—工件i的第j-1道工序停止加工的時(shí)間；TSkr—機(jī)器k上第r個(gè)空閑時(shí)間段的開(kāi)始時(shí)間；Pijk—工件i的第j道工序在機(jī)器k上的加工時(shí)間；TEkr—機(jī)器k上第r個(gè)空閑時(shí)間段的結(jié)束時(shí)間；tb—工序的加工起始時(shí)間；LMk—機(jī)器k上最后一道工序的結(jié)束時(shí)間。

具體步驟流程如下：

(1)找到當(dāng)前同機(jī)器上所有加工空閑時(shí)間段[TSkr,TEkr]；

(2)根據(jù)式(8)計(jì)算各工序Oij的加工起始時(shí)間ta；

(3)根據(jù)式(9)判斷當(dāng)前工序能否在同機(jī)器上向前插入空閑間隙，若能則按起始時(shí)間ta進(jìn)行加工，若不能則根據(jù)式(10)按tb進(jìn)行加工。

2.2 種群初始化

為提高種群初始解的質(zhì)量，本文采用全局選擇與快速選擇相結(jié)合的方式，快速得到較好的初始解：

(1)通過(guò)全局選擇將工序盡可能安排到當(dāng)前累積加工負(fù)荷最小的加工機(jī)器上，以保證加工機(jī)器負(fù)荷平衡；

(2)通過(guò)快速選擇，為各工序按概率隨機(jī)分配或分配到加工該工序用時(shí)最短的機(jī)器上，以擴(kuò)大搜索范圍保證初始種群的多樣性。

對(duì)應(yīng)兩種方式的種群產(chǎn)生比例分別設(shè)置為0.4、0.6。

2.3 交叉與變異

2.3.1 混合交叉方案

工序編碼部分采用張超勇等[12]提出的IPOX交叉。為適應(yīng)2.1節(jié)中的編碼策略，在交叉過(guò)程中機(jī)器編碼也做出相應(yīng)的變換。

基于工序編碼的IPOX交叉如圖2所示。

圖2 基于工序編碼的IPOX交叉

機(jī)器編碼部分采用改進(jìn)的MPX交叉。首先從工件集J中隨機(jī)選取若干個(gè)工件如：{J2,J3}并記錄其出現(xiàn)的位置；接著分別將父代機(jī)器編碼MF1、MF2中非記錄位置基因放入子代機(jī)器編碼MC1、MC2；最后交換MF1、MF2中記錄位置的同工序機(jī)器基因并依次插入子代對(duì)應(yīng)位置。

基于機(jī)器編碼的改進(jìn)MPX交叉如圖3所示。

圖3 基于機(jī)器編碼的改進(jìn)MPX交叉

2.3.2 混合變異方案

工序編碼部分采用插入變異。隨機(jī)選取2個(gè)位置點(diǎn)S1、S2，假設(shè)S1

基于工序編碼的插入變異如圖4所示。

圖4 基于工序編碼的插入變異

機(jī)器編碼部分采用貪婪組合變異策略。隨機(jī)產(chǎn)生一個(gè)位置點(diǎn)，一是在該道工序的可選機(jī)器集中隨機(jī)選出一臺(tái)不重復(fù)的機(jī)器，替換當(dāng)前機(jī)器基因；二是在其可選集中選擇當(dāng)前負(fù)荷最小的機(jī)器，替換當(dāng)前機(jī)器基因，兩種方式比例設(shè)置為0.5、0.5。

基于機(jī)器編碼的貪婪組合變異如圖5所示。

圖5 基于機(jī)器編碼的貪婪組合變異

2.3.3 交叉、變異算子的自適應(yīng)改進(jìn)。

交叉、變異操作分別影響算法的全局、局部搜索性能。在種群進(jìn)化前期，優(yōu)秀解距離pareto最優(yōu)前沿較遠(yuǎn)，為保證群體的參與性，筆者采用較大的交叉概率Pc，以提高全局搜索能力，加快種群進(jìn)化過(guò)程；在種群進(jìn)化中后期，種群中優(yōu)秀解的數(shù)量居多，為防止算法陷入局部最優(yōu)，筆者采用較大的變異概率Pm，以提高局部搜索能力。

交叉概率范圍設(shè)置為(0.4，0.8)，變異概率范圍設(shè)置為(0.01，0.2)，自適應(yīng)算子計(jì)算公式如下：

(11)

Pm(i)=minPm+

(12)

式中：Pc(i)—第i代的交叉概率；Pm(i)—第i代的變異概率；gen—總迭代數(shù)；maxPc—最大交叉概率；minPc—最小交叉概率；maxPm—最大變異概率；minPm—最小變異概率。

2.4 精英策略

針對(duì)傳統(tǒng)精英策略保持種群多樣性能力差、易于收斂于局部最優(yōu)等問(wèn)題，本文對(duì)其進(jìn)行了改進(jìn)：

(1)對(duì)各等級(jí)非支配層上的個(gè)體進(jìn)行擁擠度排序；

(2)為了保留盡可能多的精英解，將位于1級(jí)非支配層上的所有個(gè)體直接選入子代中，若其數(shù)量超過(guò)子代種群數(shù)量N的0.15倍，則按照擁擠度排序選擇前0.15N個(gè)個(gè)體進(jìn)入子代；

(3)對(duì)其他等級(jí)非支配層上的個(gè)體，分別按在種群大小為Np的合并種群中所占的比例，選取Ni個(gè)個(gè)體進(jìn)入子代。

其中，每級(jí)非支配層個(gè)體數(shù)量選擇函數(shù)如下：

(13)

式中：i—非支配層等級(jí)；Fi—第i級(jí)非支配層；Ni—從第i級(jí)非支配層Fi中選取的個(gè)體數(shù)量；|Fi|—第i級(jí)非支配層上的個(gè)體數(shù)；Np—合并種群的大小；N—子代種群的大小。

2.5 改進(jìn)的和聲搜索算法

標(biāo)準(zhǔn)和聲搜索算法的核心在于新和聲的產(chǎn)生以及和聲記憶庫(kù)的更新。為了更好地與HMO-NSGA-II相融合，本文做出了以下改進(jìn)：

(1)將種群精英庫(kù)與和聲記憶庫(kù)相結(jié)合，以解決HS依賴較好初始解的弊端，并采用改進(jìn)的精英策略完成和聲記憶庫(kù)的更新；

(2)在新和聲的產(chǎn)生上采用優(yōu)秀片段保留以及基于關(guān)鍵路徑的變鄰域搜索策略。

對(duì)應(yīng)標(biāo)準(zhǔn)HS中對(duì)音調(diào)高低進(jìn)行升降微調(diào)的2種方式，具體方法如下：

(1)從和聲記憶庫(kù)中隨機(jī)抽出一個(gè)和聲，即：

(14)

式中：l—保留的優(yōu)秀基因片段長(zhǎng)度；lhs—和聲的長(zhǎng)度，即總工序數(shù)；index—該和聲在和聲記憶庫(kù)中的非支配排序序號(hào)；HMS—和聲記憶庫(kù)的大小。

按該和聲的優(yōu)秀度選擇保留優(yōu)秀基因片段的長(zhǎng)度l，對(duì)于剩余位置基因按1.3節(jié)中的約束條件隨機(jī)補(bǔ)充。

(2)變鄰域搜索采用2種鄰域結(jié)構(gòu)。對(duì)于工序的調(diào)整采用張國(guó)輝等[13]提出的改進(jìn)的N5鄰域結(jié)構(gòu)，即分別交換關(guān)鍵塊首塊、尾塊中塊尾、塊首的兩相鄰工序，其他關(guān)鍵塊只交換塊首及塊尾的兩相鄰工序，若兩相鄰工序?yàn)橥ぜt不交換；對(duì)于機(jī)器的調(diào)整，在關(guān)鍵路徑中隨機(jī)選擇一道工序，將其當(dāng)前使用機(jī)器替換為可選集中加工時(shí)間最短的機(jī)器。

2.6 步驟流程

(1)設(shè)置迭代次數(shù)、交叉變異概率等初始化參數(shù)，采用2.2節(jié)中的方法生成包含N個(gè)個(gè)體的初始種群P0作為第一代父種群Pt，并對(duì)其進(jìn)行非支配排序及擁擠度計(jì)算；

(2)通過(guò)二元錦標(biāo)賽機(jī)制，隨機(jī)選擇Pt中的個(gè)體進(jìn)行2.3節(jié)中的自適應(yīng)混合交叉、變異操作，得到子代種群Qt；

(3)合并父代種群Pt和子代種群Qt得到新種群Rt，大小為Np。然后對(duì)Rt進(jìn)行非支配排序并計(jì)算每個(gè)個(gè)體擁擠度大小，得到各級(jí)pareto非支配層F1,F2,…Fn；

(4)采用2.4節(jié)中改進(jìn)的精英策略保留各級(jí)非支配層中的優(yōu)秀個(gè)體，形成大小為N的新父代種群Pt′；

(5)將種群精英庫(kù)作為HS的和聲記憶庫(kù)，用精英庫(kù)父代種群Pt′初始化和聲記憶庫(kù)HM，和聲記憶庫(kù)大小HMS為N；

(6)產(chǎn)生一組隨機(jī)數(shù)r1、r2，其中r1∈[1,HMS]、r2∈(0,1)；

(7)從和聲記憶庫(kù)HM中選擇第r1條和聲，并判斷r2是否小于和聲微調(diào)概率PAR，若成立則采用2.5節(jié)(1)中的和聲優(yōu)秀片段保留策略對(duì)選擇的和聲進(jìn)行微調(diào)，否則采用2.5節(jié)(2)中的基于關(guān)鍵路徑的變鄰域搜索策略進(jìn)行微調(diào)，得到新和聲Xnew；

(9)判斷迭代次數(shù)j是否達(dá)到最大，若是則跳轉(zhuǎn)至下一步，否則迭代次數(shù)加一跳轉(zhuǎn)至(6)進(jìn)行下一輪循環(huán)；

(10)判斷迭代次數(shù)i是否達(dá)到最大，若是則結(jié)束迭代得到一組非劣調(diào)度方案，否則迭代次數(shù)加一跳轉(zhuǎn)至(2)進(jìn)行下一輪循環(huán)。

HMO-NSGA-II流程框架如圖6所示。

圖6 HMO-NSGA-II流程框架

3 實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文提出的HMO-NSGA-II在MO-FJSP求解上的可行性、有效性和實(shí)用性，筆者選擇通用國(guó)際標(biāo)準(zhǔn)算例和實(shí)際生產(chǎn)案例進(jìn)行測(cè)試，其中，標(biāo)準(zhǔn)算例包括Kacem測(cè)試集[14](8x8(P-FJSP)、10x10(T-FJSP)、15x10(T-FJSP))和BRdata數(shù)據(jù)集[15](MK01-MK10)。

算法采用MATLAB R2018a編程，運(yùn)行環(huán)境為：CPU Intel i7-4558U主頻2.80 GHz，內(nèi)存4 GB，Windows 7操作系統(tǒng)的個(gè)人筆記本電腦。

測(cè)試目標(biāo)函數(shù)選用1.2節(jié)中的式(1～3)，HMO-NSGA-II參數(shù)設(shè)置為：總迭代次數(shù)，種群大小，交叉概率范圍(0.4，0.8)，變異概率范圍(0.01，0.2)，和聲搜索算法迭代次數(shù)，和聲記憶庫(kù)微調(diào)概率。

具體步驟為：

(1)在BRdata數(shù)據(jù)集下，本文將NSGA-II與HMO-NSGA-II各運(yùn)行20次后的非劣解按最大完工時(shí)間最小進(jìn)行對(duì)比。

HMO-NSGA-II與NSGA-II對(duì)比結(jié)果如表1所示。

表1 HMO-NSGA-II與NSGA-II對(duì)比結(jié)果

從表1可以看出：相對(duì)于Brandimarte方法而言，兩種算法都取得了較好的測(cè)試結(jié)果，但隨著問(wèn)題規(guī)模的增大，NSGA-II較HMO-NSGA-II求得非劣解的質(zhì)量有所下降；在MK01問(wèn)題上兩者所得的值相同，但HMO-NSGA-II的均值及標(biāo)準(zhǔn)差均低于NSGA-II；在MK02-MK10問(wèn)題上HMO-NSGA-II所得的非劣解均優(yōu)于NSGA-II，且20次運(yùn)算結(jié)果波動(dòng)不大，在求解質(zhì)量上表現(xiàn)出很好的穩(wěn)定性。其中，以MK01問(wèn)題為例，兩算法某次運(yùn)行結(jié)果的迭代過(guò)程及非劣解分布對(duì)比分析如下。

HMO-NSGA-II與NSGA-II求解MK01問(wèn)題過(guò)程對(duì)比如圖7所示。

圖7 HMO-NSGA-II與NSGA-II求解MK01問(wèn)題過(guò)程對(duì)比

從圖7可以看出：在得到相同解的情況下HMO-NSGA-II能夠穩(wěn)定、快速的找到最優(yōu)解，具有很好的收斂性；HMO-NSGA-II最終得到13個(gè)非支配解，NSGA-II最終得到8個(gè)非支配解，HMO-NSGAII得到的非支配解個(gè)數(shù)多、分布范圍廣且均勻，體現(xiàn)出較好的全局、局部搜索性能。

(2)在Kacem測(cè)試集下，本文將HMO-NSGA-II與孟冠軍提出的混合人工蜂群算法(ABC+TS)、曹磊提出的變鄰域雜草優(yōu)化算法(IWO+VNS)、Kacem提出的局部逼近與控制遺傳算法的混合算法(AL+CGA)、喻明讓提出的離散粒子群算法(PDPSO)[16]的運(yùn)行結(jié)果進(jìn)行了對(duì)比。

各算法運(yùn)行結(jié)果對(duì)比如表2所示。

從表2可以看出：在Kacem8×8問(wèn)題上曹磊提出的IWO+VNS得到了更多的非劣解，但均未達(dá)到最優(yōu)值；對(duì)于其余問(wèn)題，與其他算法相比HMO-NSGA-II在求解精度上都可以達(dá)到最優(yōu)值標(biāo)準(zhǔn)，在求得的非支配解個(gè)數(shù)上均不劣于其他算法。

表2 各算法運(yùn)行結(jié)果對(duì)比

Kacem15×10問(wèn)題調(diào)度甘特圖如圖8所示。

圖8 Kacem15×10問(wèn)題調(diào)度甘特圖

(3)為進(jìn)一步驗(yàn)證HMO-NSGA-II算法求解實(shí)際問(wèn)題的實(shí)用性，本文選擇某汽車線束生產(chǎn)企業(yè)的實(shí)際調(diào)度案例進(jìn)行測(cè)試。汽車線束生產(chǎn)工藝流程包括下線、壓接、內(nèi)聯(lián)、分裝、總裝等，以某個(gè)具有6條支路的線束產(chǎn)品為例，對(duì)應(yīng)工藝流程中6條分裝支路相當(dāng)于6個(gè)工件，其中工件J1、J3、J4分別包含工序序號(hào)為1、2、3、4的4道工序，工件J2、J5、J6分別包含工序序號(hào)為1、2、4的3道工序，該產(chǎn)品產(chǎn)量為50根。

線束產(chǎn)品加工生產(chǎn)數(shù)據(jù)如表3所示。

表3 線束產(chǎn)品加工生產(chǎn)數(shù)據(jù)

根據(jù)表3中的實(shí)際生產(chǎn)數(shù)據(jù)，本文采用NSGA-II和HMO-NSGA-II進(jìn)行調(diào)度求解，并將求解結(jié)果與傳統(tǒng)的人工調(diào)度方法進(jìn)行對(duì)比。

各調(diào)度方法求解實(shí)際問(wèn)題的結(jié)果對(duì)比如表4所示。

表4 各調(diào)度方法求解實(shí)際問(wèn)題的結(jié)果對(duì)比

從表4可以看出：人工調(diào)度方法較兩種智能調(diào)度算法對(duì)人的依賴程度大，并且調(diào)度與生產(chǎn)加工所用時(shí)間長(zhǎng)，調(diào)度效果比較差；HMO-NSGA-II相對(duì)于NSGA-II雖調(diào)度用時(shí)稍長(zhǎng)，但在生產(chǎn)加工用時(shí)和非劣解個(gè)數(shù)的性能指標(biāo)上優(yōu)勢(shì)明顯，該汽車線束企業(yè)可根據(jù)實(shí)際情況，從所得非劣解集中選擇合適的解用于指導(dǎo)生產(chǎn)。

汽車線束實(shí)際調(diào)度方案甘特圖如圖9所示。

圖9 汽車線束實(shí)際調(diào)度方案甘特圖

綜上所述，本文提出的HMO-NSGA-II與單一算法相比求解精度高、收斂速度快，具有很好的全局、局部搜索能力；在測(cè)試選取的不同規(guī)?；鶞?zhǔn)實(shí)例與實(shí)際生產(chǎn)案例上都取得了最優(yōu)的結(jié)果，具有很好的適應(yīng)性和魯棒性。由此可以證明，HMO-NSGA-II用于求解MO-FJSP是可行、有效的，具有很好的實(shí)用價(jià)值。

4 結(jié)束語(yǔ)

(1)本文對(duì)NSGA-II的種群初始化、交叉變異方式、精英保留策略等進(jìn)行了改進(jìn)，有效保證了種群多樣性，提高了算法的全局、局部搜索能力；

(2)以NSGA-II為主和聲搜索算法為輔，充分結(jié)合兩種算法的優(yōu)點(diǎn)提出了混合多目標(biāo)遺傳算法HMO-NSGA-II，提高了求解質(zhì)量并通過(guò)測(cè)試國(guó)際標(biāo)準(zhǔn)算例Kacem測(cè)試集、BRdata數(shù)據(jù)集和實(shí)際生產(chǎn)案例，驗(yàn)證了算法求解MO-FJSP的可行性和有效性，具有很好的實(shí)用價(jià)值；

(3)接下來(lái)，筆者將深入研究MO-FJSP自身特征領(lǐng)域，在不同目標(biāo)需求下繼續(xù)探索混合多目標(biāo)遺傳算法的改進(jìn)策略，以不斷完善、提高算法的求解質(zhì)量和效率。