基于混合多目標遺傳算法的柔性作業車間調度問題研究*

2021-02-25 02:43:14宋昌興阮景奎

機電工程 2021年2期

宋昌興，阮景奎，王宸

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

0 引言

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

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

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

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

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

1 多目標柔性作業車間調度問題

1.1 問題描述

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

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

1.2 數學模型

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

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

f1=min(max(Ci))

(1)

(2)最大瓶頸機器負荷最小：

(2)

(3)最大機器負荷最小：

(3)

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

1.3 約束條件

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

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

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

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

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

2.1 編碼與解碼

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

基于機器、工序的雙層編碼過程如圖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)根據式(8)計算各工序Oij的加工起始時間ta；

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

2.2 種群初始化

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

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

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

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

2.3 交叉與變異

2.3.1 混合交叉方案

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

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

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

機器編碼部分采用改進的MPX交叉。首先從工件集J中隨機選取若干個工件如：{J2,J3}并記錄其出現的位置；接著分別將父代機器編碼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 交叉、變異算子的自適應改進。

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

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

(11)

Pm(i)=minPm+

(12)

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

2.4 精英策略

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

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

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

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

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

(13)

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

2.5 改進的和聲搜索算法

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

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

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

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

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

(14)

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

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

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

2.6 步驟流程

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

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

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

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

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

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

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

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

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

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數據集[15](MK01-MK10)。

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

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

具體步驟為：

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

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

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

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

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

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

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

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

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

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

表2 各算法運行結果對比

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

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

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

線束產品加工生產數據如表3所示。