宋昌興，阮景奎，王 宸

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

0 引 言

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

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

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

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

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

1 多目標柔性作業(yè)車間調度問題

1.1 問題描述

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

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

1.2 數(shù)學模型

本文選擇以下3個具有實際應用價值的目標，以降低機器生產負荷、縮短加工產品完工時間，從而提高生產效率。

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

f1=min(max(Ci))

(1)

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

(2)

(3)最大機器負荷最?。?/p>

(3)

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

1.3 約束條件

一般的，在調度過程中MO-FJSP模型應滿足以下約束條件[10，11]：

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

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

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

Sij+PijkXijk≤Si(j+1)

(4)

(4)同時刻，同一臺機器只能加工某工件的某一道工序，即：

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

(5)

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

(6)

(5)同時刻，同一個工件的同一工序能且只能被一臺機器加工，即：

(7)

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

2 混合多目標遺傳算法設計

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

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

2.1 編碼與解碼

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

基于機器、工序的雙層編碼過程如圖1所示。

圖1 基于機器、工序的雙層編碼過程

解碼采用插入式貪婪解碼方法，將個體編碼轉換為調度甘特圖。

加工起始時間計算如下式所示：

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

(8)

ta+Pijk≤TEkr

(9)

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

(10)

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

具體步驟流程如下：

(1)找到當前同機器上所有加工空閑時間段[TSkr,TEkr]；

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

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

2.2 種群初始化

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

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

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

對應兩種方式的種群產生比例分別設置為0.4、0.6。

2.3 交叉與變異

2.3.1 混合交叉方案

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

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

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

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

基于機器編碼的改進MPX交叉如圖3所示。

圖3 基于機器編碼的改進MPX交叉

2.3.2 混合變異方案

工序編碼部分采用插入變異。隨機選取2個位置點S1、S2，假設S1

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

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

機器編碼部分采用貪婪組合變異策略。隨機產生一個位置點，一是在該道工序的可選機器集中隨機選出一臺不重復的機器，替換當前機器基因；二是在其可選集中選擇當前負荷最小的機器，替換當前機器基因，兩種方式比例設置為0.5、0.5。

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

圖5 基于機器編碼的貪婪組合變異

2.3.3 交叉、變異算子的自適應改進。

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

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

(11)

Pm(i)=minPm+

(12)

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

2.4 精英策略

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

(1)對各等級非支配層上的個體進行擁擠度排序；

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

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

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

(13)

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

2.5 改進的和聲搜索算法

標準和聲搜索算法的核心在于新和聲的產生以及和聲記憶庫的更新。為了更好地與HMO-NSGA-II相融合，本文做出了以下改進：

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

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

對應標準HS中對音調高低進行升降微調的2種方式，具體方法如下：

(1)從和聲記憶庫中隨機抽出一個和聲，即：

(14)

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

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

(2)變鄰域搜索采用2種鄰域結構。對于工序的調整采用張國輝等[13]提出的改進的N5鄰域結構，即分別交換關鍵塊首塊、尾塊中塊尾、塊首的兩相鄰工序，其他關鍵塊只交換塊首及塊尾的兩相鄰工序，若兩相鄰工序為同工件則不交換；對于機器的調整，在關鍵路徑中隨機選擇一道工序，將其當前使用機器替換為可選集中加工時間最短的機器。

2.6 步驟流程

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

(2)通過二元錦標賽機制，隨機選擇Pt中的個體進行2.3節(jié)中的自適應混合交叉、變異操作，得到子代種群Qt；

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

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

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

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

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

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

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

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

圖6 HMO-NSGA-II流程框架

3 實驗及結果分析

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

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

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

具體步驟為：

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

HMO-NSGA-II與NSGA-II對比結果如表1所示。

表1 HMO-NSGA-II與NSGA-II對比結果

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

HMO-NSGA-II與NSGA-II求解MK01問題過程對比如圖7所示。

圖7 HMO-NSGA-II與NSGA-II求解MK01問題過程對比

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

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

各算法運行結果對比如表2所示。

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

表2 各算法運行結果對比

Kacem15×10問題調度甘特圖如圖8所示。

圖8 Kacem15×10問題調度甘特圖

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

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

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

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

各調度方法求解實際問題的結果對比如表4所示。

表4 各調度方法求解實際問題的結果對比

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

汽車線束實際調度方案甘特圖如圖9所示。

圖9 汽車線束實際調度方案甘特圖

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

4 結束語

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

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

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