不同支配關系的多目標算法的柔性作業調度

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

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

0 引言

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

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

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

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

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

多目標優化問題和調度問題現在都是我們研究的熱點，本文的目的就是通過不同的方法求得優化問題的最優解，應用不同的支配方式去求解帶有機器人搬運的柔性作業車間調度問題，以傳統的NSGA-II為框架，分別基于Lorenz支配關系和CDAS支配關系對問題進行求解，并將所得的解通過[13]距離準則和C[20]準則進行比較分析。

1 問題描述

1.1 研究問題

參數定義如下：

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

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

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

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

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

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

H為一個很大的正整數;

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

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

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

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

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

本文研究問題數學模型引用Caumond[22]論文中的數學模型，假設條件為：

1)同一工件根據加工順序執行不同工序；

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

3)同一時刻搬運機器人執行一個搬運操作；

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

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

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

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

目標函數：

(1)

minimizeα∑Ej+β∑Tj

(2)

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

Ej=max(0,aj-Cj)

(3)

Tj=max(0,Cj-bj)

(4)

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

1.2 解的支配關系

本節介紹了三種支配關系：Pareto支配關系、Lorenz支配關系和CDAS支配關系。下面以一個最小化的多目標遺傳優化問題為研究對象闡述這三種支配關系：

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

(5)

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

1.2.1 Pareto支配

給定一個多目標優化問題，設X為多目標優化問題的可行解集，目標向量為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支配關系如圖2所示，區域①為解S的Pareto支配區域。

圖2 Pareto支配關系

1.2.2 Lorenz支配

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

基于Lorenz支配關系，如果解X支配解Y,記作XLY。如果解X的Lorenz矢量基于Pareto支配關系支配解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)所有目標函數適應度值中從大到小排列第二的適應度值，依次類推。

根據Lorenz支配關系的定義，Lorenz支配將解的目標函數值收斂到未修改前其中一個目標函數值的附近。Lorenz支配關系如圖3所示。對于解S，基于Pareto支配，S的支配領域為區域①。而基于Lorenz支配，S的支配領域為區域①,②,③。顯然，Lorenz的支配區域要大于Pareto的支配區域,事實上Lorenz的非支配解是Pareto非支配解的子集。

圖3 Lorenz支配關系

1.2.3 CDAS支配

為了提高基于多目標優化進化算法的Pareto支配的選擇壓力，提出了一種新的支配關系CDAS。CDAS支配利用一個用戶自定義參數S改變支配關系，是一種支配區域自適應變化的方法，它是利用支配關系來提高收斂壓力。在多目標優化問題中，CDAS支配增強了解的搜索能力。經過試驗發現，當S等于0.25時，尋求多目標優化問題最優解的效果最佳。

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

(8)

圖4 解x修改前后適應度值

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

(9)

圖5 CDAS的支配關系

2 算法

2.1 NSGA-II算法

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

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

2.2 遺傳算法因子

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

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

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

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

停止標準：本文中的停止標準是設定一個比較大的迭代次數。

2.3 L-NSGA算法

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

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

(10)

2.4 CDAS-NSGA算法

同樣CDAS-NSGA算法和NSGA-II算法的結構也類似，CDAS-NSGA算法是基于CDAS支配關系進行解的排序。經CDAS標準修改每一個目標函數的適應度值，從而擴大或者縮小解的支配領域。

在CDAS-NSGA算法中，我們同樣也應用了動態線性比例函數，具體和2.3節L-NSGA算法中提到的一樣。

3 實驗結果與分析

3.1 仿真測試介紹

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

3.2 對比準則

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

3.3 實驗結果與分析

為了分析比較不同的支配關系對單機器搬運的柔性作業車間調度問題求解的效果，我們分別通過μd距離法和C準則對所得非支配解進行比較分析。具體數據如表2，表3，表4所示：其中表2是L-NSGA算法與NSGA-II算法最優解之間的比較，表3是CDAS-NSGA與NSGA-II最優解之間的比較，表4是CDAS-NSGA算法與L-NSGA算法最優解之間的比較。以表2第一行例LT155為例：機器數為5，加工工件數為3，μd為L-NSGA算法所得的“最優解”相對于NSGA-II算法中所有“最優解”比較后的平均μd距離，μd=-0.006 9<0,μd的最優值代表L-NSGA所得的解大多數位于NSGA-II的下方，說明L-NSGA所得解更優，分別代表該組最好的距離。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中，我們看到的值都是負的，而且大部分的C1值小于C2的值，說明基于lorenz支配關系和基于CDAS支配關系所得的解明顯優于基于Pareto支配關系所得的解。

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

表2 L-NSGA算法與NSGA-II算法比較結果

表3 CDAS-NSGA算法與NSGA-II算法比較結果

表4 CDAS-NSGA算法與L-NSGA算法比較結果

4 結束語

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