不同支配關(guān)系的多目標(biāo)算法的柔性作業(yè)調(diào)度

李曉輝，刁林倩，張 秀2，趙 毅，李 杰

(1.長安大學(xué) 電子與控制工程學(xué)院, 西安 710064; 2.陜西汽車集團(tuán)有限責(zé)任公司，西安 710119)

0 引言

隨著大批量連續(xù)生產(chǎn)時代正逐漸被適應(yīng)市場動態(tài)變化的多品種、小批量離散生產(chǎn)所代替，一個制造企業(yè)的生存能力和競爭能力在很大程度上取決于它是否能在較短的生產(chǎn)周期內(nèi)，生產(chǎn)出較低成本、較高質(zhì)量的多個產(chǎn)品品種的能力。柔性制造系統(tǒng)(FMS)是高度自動化的生產(chǎn)系統(tǒng)，能夠生產(chǎn)各種各樣的作業(yè)類型。許多FMS采用自動制導(dǎo)車輛系統(tǒng)(AGVS)，這是各種先進(jìn)的材料處理技術(shù)之一。由于縮短交貨期一直是工業(yè)界的一個重要目標(biāo)，因此FMS調(diào)度受到了廣泛的關(guān)注。在靈活作業(yè)車間調(diào)度問題(FJSP)[1]中，每個作業(yè)都可以在任何可用的機(jī)器上執(zhí)行。J.Blazewicz等人[2]指出，F(xiàn)MS中最困難的操作問題之一是對所有所需資源的生產(chǎn)順序和時間分配進(jìn)行適當(dāng)?shù)膮f(xié)調(diào)，即開發(fā)考慮工作、機(jī)器和車輛的高效FMS調(diào)度計(jì)劃。開發(fā)高效的FMS調(diào)度仍然是一個重要而活躍的研究領(lǐng)域。近年來，對FJSP的擴(kuò)展進(jìn)行了研究，提出了不同的精確和近似方法來解決這一問題，以編制接近實(shí)際的調(diào)度。關(guān)于FJSP建模的最早研究可以在P.Brucker和R.Schlie[3]中找到，提出了一種考慮兩種工作的多項(xiàng)式算法來解決這類問題。近年來，一些問題也采用了精確的方法。例如，M.Mousakhani[4]使用混合整數(shù)線性規(guī)劃(MILP)方法解決了設(shè)置時間依賴于序列的FJSP問題。

典型的半導(dǎo)體自動化制造單元，如：M.Dawande等人[5]，C.R.Pan等人[6]，如圖1所示，裝備了一個搬運(yùn)機(jī)器人，可以在工作站之間精確地運(yùn)送作業(yè)。當(dāng)作業(yè)在工作站上完成當(dāng)前處理階段時，機(jī)器人執(zhí)行加載的移動，包括3個步驟:從工作站上卸載作業(yè)，將其傳輸?shù)较乱粋€工作站上并將其加載。連續(xù)地，機(jī)器人要么在工作站上等待同一作業(yè)的下一個移動，要么在沒有任何作業(yè)的情況下執(zhí)行空洞移動，以移動到另一個工作站上執(zhí)行下一個作業(yè)的移動。在這種情況下，作業(yè)移動及其持續(xù)時間在調(diào)度過程中不能被忽略。自動化作業(yè)運(yùn)輸機(jī)器人在化工、電鍍處理和金屬切削行業(yè)也很常見如：車阿大等[7]，晏鵬宇等[8]，Gultekin等[9]。這種以機(jī)器人為中心的制造系統(tǒng)稱為機(jī)器人單元。

圖1 一個典型的帶有材料處理機(jī)器人的機(jī)器人單元

實(shí)際應(yīng)用問題中往往需要同時優(yōu)化幾個目標(biāo)，在多目標(biāo)問題求解中，由于各目標(biāo)之間是相互矛盾的，所以不能找到一個優(yōu)化解使得所有優(yōu)化目標(biāo)達(dá)到最優(yōu)，因此我們的目的是找到一個非支配解的集合代替僅有的一個最優(yōu)解。近10年來，國內(nèi)外許多研究者相繼提出大量的優(yōu)化算法，如NSGA-II[10], SPEA-II[11](strength pareto evolutionary algorithm)等在解決多目標(biāo)優(yōu)化問題上取得了很好的效果。但是隨著目標(biāo)維數(shù)的增加，基Pareto支配關(guān)系的多目標(biāo)進(jìn)化算法收斂性能下降，在求解過程中出現(xiàn)了種群早熟，收斂停滯，非支配解的比率過大的現(xiàn)象。雖然通過擴(kuò)大種群規(guī)模，可以一定程度上緩解非支配解比例過大的問題，但卻增加了求解過程的計(jì)算難度。

對于多目標(biāo)優(yōu)化問題，研究人員往往從三方面對算法進(jìn)行改善[12]：1)基于Pareto支配關(guān)系，進(jìn)行目標(biāo)降維;2)采用不同的支配方法，如：占優(yōu)，Lorenz[13]支配，CDAS[14]支配，r[15]支配等;3)引進(jìn)新的策略或機(jī)制。肖婧[16]等人提出基于全局排序的高維多目標(biāo)優(yōu)化研究，鞏敦衛(wèi)[17]等人提出基于目標(biāo)分解的高維多目標(biāo)并行進(jìn)化優(yōu)化方法，陳小紅[18]等人提出基于稀疏特征選擇的目標(biāo)降維方法，與此同時將不同的支配方法和傳統(tǒng)優(yōu)化算法結(jié)合去求解高維多目標(biāo)優(yōu)化問題也是研究的熱點(diǎn)，如Atefeh Moghaddam[19]將不同的支配方式和算法相結(jié)合求解調(diào)度問題，通過大量案例比較算法的優(yōu)越性。

多目標(biāo)優(yōu)化問題和調(diào)度問題現(xiàn)在都是我們研究的熱點(diǎn)，本文的目的就是通過不同的方法求得優(yōu)化問題的最優(yōu)解，應(yīng)用不同的支配方式去求解帶有機(jī)器人搬運(yùn)的柔性作業(yè)車間調(diào)度問題，以傳統(tǒng)的NSGA-II為框架，分別基于Lorenz支配關(guān)系和CDAS支配關(guān)系對問題進(jìn)行求解，并將所得的解通過[13]距離準(zhǔn)則和C[20]準(zhǔn)則進(jìn)行比較分析。

1 問題描述

1.1 研究問題

參數(shù)定義如下：

J為工件集合，J={J1,…,Jn};

M為工作站集合，M={M0,M1,M2,...,Mm},M0為裝/卸載站;

I為根據(jù)工件序列，工件操作集合I={1,2,…,|I|};

lij為工作站i到工作站j之間的帶載移動時間，(i,j)∈M2;

vij為工作站i到工作站j之間的空載移動時間，(i,j)∈M2;

μi為操作i(i∈I)對應(yīng)的加工站;

H為一個很大的正整數(shù);

ti為操作i的完成時間，i∈I;

Cj為是工件j的完工時間:

(i,j)∈I2并且μi=μi,i≠j;

(r,s)∈T2并且r≠s;

(r,s)∈T2并且r≠s

本文研究問題數(shù)學(xué)模型引用Caumond[22]論文中的數(shù)學(xué)模型，假設(shè)條件為：

1)同一工件根據(jù)加工順序執(zhí)行不同工序；

2)同一工作站在同一時刻只能執(zhí)行一道加工操作；

3)同一時刻搬運(yùn)機(jī)器人執(zhí)行一個搬運(yùn)操作；

4)工件搬運(yùn)時間約束，工件前道工序加工完成后才能搬運(yùn)；

5)不考慮機(jī)器和機(jī)器人故障；

6)不考慮機(jī)器人和加工站之間的裝載和卸載時間；

7)無優(yōu)先處理約束，緩沖管理規(guī)則為FIFO(First In First Out)。

目標(biāo)函數(shù)：

(1)

minimizeα∑Ej+β∑Tj

(2)

其中:α和β分別代表總提前量與總延遲量的權(quán)重。Ej和Tj代表工件j的提前量和延遲量。

Ej=max(0,aj-Cj)

(3)

Tj=max(0,Cj-bj)

(4)

其中:aj和bj表示工件j的最早到期日和最晚到期日。

1.2 解的支配關(guān)系

本節(jié)介紹了三種支配關(guān)系：Pareto支配關(guān)系、Lorenz支配關(guān)系和CDAS支配關(guān)系。下面以一個最小化的多目標(biāo)遺傳優(yōu)化問題為研究對象闡述這三種支配關(guān)系：

MinF(X)=(f1(X),f2(X),…,(fn(X)))T,x∈D

(5)

其中:X=(x1,x2,...xm)T是決策變量，fi(i=1,2,...n)是目標(biāo)函數(shù)，D是可行區(qū)域。

1.2.1 Pareto支配

給定一個多目標(biāo)優(yōu)化問題，設(shè)X為多目標(biāo)優(yōu)化問題的可行解集，目標(biāo)向量為F(x)=(f1(x),f2(x),...fm(x))，xl∈X,xk∈X,若:

?i∈{1,2,…,m}fi(xi)≤fi(xk)

?j∈{1,2,…,m}fi(xi)≤fj(xk)

(6)

則稱xlPareto支配xk(記作xlxk)，Pareto支配關(guān)系如圖2所示，區(qū)域①為解S的Pareto支配區(qū)域。

圖2 Pareto支配關(guān)系

1.2.2 Lorenz支配

多目標(biāo)啟發(fā)式算法一般情況下都是基于Pareto支配關(guān)系找到一組非支配解集，但是Lorenz支配可以減少非支配平面的范圍，提高算法的搜索能力。F.Dugardin[13]等人在其文章中提到Lorenz 支配能夠提高解的質(zhì)量，它更擅長于雙目標(biāo)優(yōu)化問題解的比較。Lorenz 支配是1934年Hardy等人第一次提出,之后Kostreva 和Ogryczak將其應(yīng)用到對于解決多目標(biāo)優(yōu)化問題中。

基于Lorenz支配關(guān)系，如果解X支配解Y,記作XLY。如果解X的Lorenz矢量基于Pareto支配關(guān)系支配解Y的Lorenz矢量，記為L(x)pL(Y)。其中X的Lorenz矢量為：

L(x)=(f(1)(x),f(1)(x)+f(2)(x),f(1)(x)+

(7)

f(1)(x)=max(fi(x))?i∈{1,2,...n}，f(2)(x)是fi(x)所有目標(biāo)函數(shù)適應(yīng)度值中從大到小排列第二的適應(yīng)度值，依次類推。

根據(jù)Lorenz支配關(guān)系的定義，Lorenz支配將解的目標(biāo)函數(shù)值收斂到未修改前其中一個目標(biāo)函數(shù)值的附近。Lorenz支配關(guān)系如圖3所示。對于解S，基于Pareto支配，S的支配領(lǐng)域?yàn)閰^(qū)域①。而基于Lorenz支配，S的支配領(lǐng)域?yàn)閰^(qū)域①,②,③。顯然，Lorenz的支配區(qū)域要大于Pareto的支配區(qū)域,事實(shí)上Lorenz的非支配解是Pareto非支配解的子集。

圖3 Lorenz支配關(guān)系

1.2.3 CDAS支配

為了提高基于多目標(biāo)優(yōu)化進(jìn)化算法的Pareto支配的選擇壓力，提出了一種新的支配關(guān)系CDAS。CDAS支配利用一個用戶自定義參數(shù)S改變支配關(guān)系，是一種支配區(qū)域自適應(yīng)變化的方法，它是利用支配關(guān)系來提高收斂壓力。在多目標(biāo)優(yōu)化問題中，CDAS支配增強(qiáng)了解的搜索能力。經(jīng)過試驗(yàn)發(fā)現(xiàn)，當(dāng)S等于0.25時，尋求多目標(biāo)優(yōu)化問題最優(yōu)解的效果最佳。

對于一個解x，根據(jù)公式(8)通過改變一個參數(shù)Si的值來修改它的每一個目標(biāo)函數(shù)的適應(yīng)度值，圖4給出了解x經(jīng)CDAS準(zhǔn)則修改前后適應(yīng)度函數(shù)值的變化情況。

(8)

圖4 解x修改前后適應(yīng)度值

CDAS原本的方法是根據(jù)解x與原點(diǎn)兩點(diǎn)間改變參數(shù)Si來改變解x的支配區(qū)域，然而，在我們研究的問題中有很多個解，且我們沒有辦法確定解的位置，想要找一個合適的參數(shù)Si也很困難，在本文中我們的目標(biāo)值是最小化，我們對CDAS支配方法在算法應(yīng)用進(jìn)行改進(jìn)，在這里首先做如下定義，如式(9)：

(9)

圖5 CDAS的支配關(guān)系

2 算法

2.1 NSGA-II算法

NSGA-II非支配排序遺傳算法，2000年由K.Deb,S.Agrawal,A.Pratap等人提出。該算法是基于Pareto支配的多目標(biāo)進(jìn)化算法，被廣泛應(yīng)用在多目標(biāo)優(yōu)化問題求解中，尤其是目標(biāo)函數(shù)只有兩到三個的優(yōu)化問題。對于多目標(biāo)優(yōu)化問題，該算法得到的不是一個單獨(dú)的解，而是一個非支配解的集合。

在NSGA-II算法中，首先隨機(jī)生成一個初始種群f1(x)>f2(x)。在第t次迭代中子代f1(x)>f2(x)通過評估、選擇、交叉、變異因子被生成。將f1(x)>f2(x)和f1(x)>f2(x)中所有個體排序到不同的前端(第一前端被認(rèn)為包含所有的非支配解，為了找到下一個前端的解，之前已被排序的解不再考慮)。這個過程被重復(fù)，直到所有的解被排序，最好的解(擁有最優(yōu)序值和最佳擁擠距離)將被選擇作為下一次迭代中的父代種群f1(x)>f2(x)。當(dāng)滿足設(shè)定的停止標(biāo)準(zhǔn)時，整個迭代過程結(jié)束。

2.2 遺傳算法因子

交叉變異：本文采用Q.K.Pan[23]等(2008)一文中提到的two-cut points PTL交叉法。該交叉法的優(yōu)勢在于：即使兩個父代相同，經(jīng)過PTL交叉也可以產(chǎn)生出不同的子代。在PTL交叉過程中，隨機(jī)產(chǎn)生兩個交叉位置，將父代1中隨機(jī)產(chǎn)生的交叉位置上的基因作為子代1最左端和子代2最右端的基因，子代個體剩余部分的基因由父代2除去父代1交叉位置上的基因外剩余部分的基因填充，具體見表1。

表1 PTL交叉因子的一個例子

為了保證所得解的多樣性，交叉操作之后，對生成的子代進(jìn)行變異操作，本文采用單點(diǎn)變異法，變異位置是隨機(jī)生成的。

選擇：選擇是根據(jù)適應(yīng)度函數(shù)或者序值進(jìn)行交叉操作父代選擇的一個過程。在這個過程中本文應(yīng)用錦標(biāo)賽父代選擇法，這是遺傳算法所有選擇方法中的一種。錦標(biāo)賽選擇法是隨機(jī)選擇一些解，然后根據(jù)序值選擇其中最好的作為交叉操作的父代。

停止標(biāo)準(zhǔn)：本文中的停止標(biāo)準(zhǔn)是設(shè)定一個比較大的迭代次數(shù)。

2.3 L-NSGA算法

L-NSGA算法和NSGA-II算法結(jié)構(gòu)類似，唯一不同之處在于：L-NSGA算法是基于Lorenz支配關(guān)系的，而NSGA-II算法則是基于Pareto支配關(guān)系。對于本文，帶有機(jī)器人制造單元的作業(yè)車間調(diào)度最小化工件完工提前量和延遲量的總權(quán)重的一個雙目標(biāo)優(yōu)化問題，如果f1(x)>f2(x)，則X的Lorenz矢量為:

L(x)=(f1(x),f1(x)+f2(x))

(10)

2.4 CDAS-NSGA算法

同樣CDAS-NSGA算法和NSGA-II算法的結(jié)構(gòu)也類似，CDAS-NSGA算法是基于CDAS支配關(guān)系進(jìn)行解的排序。經(jīng)CDAS標(biāo)準(zhǔn)修改每一個目標(biāo)函數(shù)的適應(yīng)度值，從而擴(kuò)大或者縮小解的支配領(lǐng)域。

在CDAS-NSGA算法中，我們同樣也應(yīng)用了動態(tài)線性比例函數(shù)，具體和2.3節(jié)L-NSGA算法中提到的一樣。

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

3.1 仿真測試介紹

本文算法以Visual Studio 2017開發(fā)工具編程實(shí)現(xiàn)。選取了16組實(shí)例數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，其中實(shí)例1～8參考Caumond[22]論文中的數(shù)據(jù)，實(shí)例9～15自己生成的。每個實(shí)例包含不同數(shù)目的工件、機(jī)器與加工工序。參數(shù)aj和bj根據(jù)完工時間按照一定規(guī)律隨機(jī)產(chǎn)生。分別利用NSGA-II、L-NSGA、CDAS-NSGA算法對該問題進(jìn)行最優(yōu)解的尋求。其中交叉概率Pc設(shè)為0.9，變異概率Pm設(shè)為0.1，迭代次數(shù)設(shè)為20，種群大小設(shè)為40，CDAS-NSGA中的用戶自定義參數(shù)S設(shè)為0.45。每個實(shí)例數(shù)據(jù)測試20次，記錄每種支配方式最后找到的非支配解。

3.2 對比準(zhǔn)則

由于每一個Pareto 前端不是一個單獨(dú)的解，而是一個非支配解的集合，所以對于兩個不同的Pareto前端的比較是困難的。我們的目地是讓生成的解的多樣性最大化，Pareto優(yōu)化解之間的絕對距離最小化，包含前端的伸展性最大化。本文采用由Dugardin等人提出的μd距離法和Zitzler 和Thiele 提出的C比較準(zhǔn)則。

3.3 實(shí)驗(yàn)結(jié)果與分析

為了分析比較不同的支配關(guān)系對單機(jī)器搬運(yùn)的柔性作業(yè)車間調(diào)度問題求解的效果，我們分別通過μd距離法和C準(zhǔn)則對所得非支配解進(jìn)行比較分析。具體數(shù)據(jù)如表2，表3，表4所示：其中表2是L-NSGA算法與NSGA-II算法最優(yōu)解之間的比較，表3是CDAS-NSGA與NSGA-II最優(yōu)解之間的比較，表4是CDAS-NSGA算法與L-NSGA算法最優(yōu)解之間的比較。以表2第一行例LT155為例：機(jī)器數(shù)為5，加工工件數(shù)為3，μd為L-NSGA算法所得的“最優(yōu)解”相對于NSGA-II算法中所有“最優(yōu)解”比較后的平均μd距離，μd=-0.006 9<0,μd的最優(yōu)值代表L-NSGA所得的解大多數(shù)位于NSGA-II的下方，說明L-NSGA所得解更優(yōu)，分別代表該組最好的距離。C1代表L-NSGA算法所得的解被NSGA-II支配的概率，表中平均C1=0.15，代表L-NSGA中15%解被NSGA-II中的解支配，同理C2代表NSGA-II中的解被L-NSGA中的解支配的概率，C2=0.29,說明NSGA-II中29%的解被L-NSGA中的解支配。

從表2表3中，我們看到的值都是負(fù)的，而且大部分的C1值小于C2的值，說明基于lorenz支配關(guān)系和基于CDAS支配關(guān)系所得的解明顯優(yōu)于基于Pareto支配關(guān)系所得的解。

表4中的值大部分都是正的只有少數(shù)是負(fù)的，且在在這些事例中C1平均值基本大于C2的平均值值，說明在參數(shù)S為0.45時基于lorenz支配關(guān)系所得的解明顯優(yōu)于基于CDAS支配關(guān)系所得的解。

表2 L-NSGA算法與NSGA-II算法比較結(jié)果

表3 CDAS-NSGA算法與NSGA-II算法比較結(jié)果

表4 CDAS-NSGA算法與L-NSGA算法比較結(jié)果

4 結(jié)束語

本文我們研究了一個帶有單機(jī)器人制造單元的作業(yè)車間調(diào)度問題的優(yōu)化問題。大量研究表明，改變支配關(guān)系可以有效提高算法尋求最優(yōu)解的效率，Lorenz支配關(guān)系與CDAS支配關(guān)系的支配區(qū)域都比Pareto支配關(guān)系的支配區(qū)域大，則這兩種支配關(guān)系下找到的非支配平面的最優(yōu)解集是Pareto支配關(guān)系下找到的非支配平面的最優(yōu)解集的子集。文中我們將以NSGA-II為框架結(jié)合Lorenz支配關(guān)系和CDAS支配關(guān)系并與傳統(tǒng)的基于Pareto支配關(guān)系的NSGA-II3種算法去研究同一優(yōu)化調(diào)度問題，最后將3種算法所得的非支配解通過C準(zhǔn)則和準(zhǔn)則進(jìn)行比較分析，我們發(fā)現(xiàn)對于求解高維多目標(biāo)優(yōu)化問題，基于Lorenz支配關(guān)系和CDAS支配關(guān)系的優(yōu)化算法比基于傳統(tǒng)的Pareto支配關(guān)系的優(yōu)化算法的效果更佳。在CDAS支配關(guān)系中當(dāng)S值為0.45時，基于CDAS支配關(guān)系的優(yōu)化算法明顯比基于Lorenz支配關(guān)系的優(yōu)化算法差。