李曉輝,刁林倩,張 秀2,趙 毅,李 杰
(1.長安大學(xué) 電子與控制工程學(xué)院, 西安 710064; 2.陜西汽車集團(tuán)有限責(zé)任公司,西安 710119)
隨著大批量連續(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)行比較分析。
參數(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的最早到期日和最晚到期日。
本節(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)系
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é)束。
交叉變異:本文采用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ù)。
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)
同樣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算法中提到的一樣。
本文算法以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次,記錄每種支配方式最后找到的非支配解。
由于每一個Pareto 前端不是一個單獨(dú)的解,而是一個非支配解的集合,所以對于兩個不同的Pareto前端的比較是困難的。我們的目地是讓生成的解的多樣性最大化,Pareto優(yōu)化解之間的絕對距離最小化,包含前端的伸展性最大化。本文采用由Dugardin等人提出的μd距離法和Zitzler 和Thiele 提出的C比較準(zhǔn)則。
為了分析比較不同的支配關(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é)果
本文我們研究了一個帶有單機(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)化算法差。