李曉輝,高 鐸,楊 晰,劉元東,趙 毅,董 媛

1(長安大學(xué) 電子與控制工程學(xué)院,西安 710054)

2(陜西航天時代導(dǎo)航設(shè)備有限公司,寶雞 721099)

由于機器人制造單元對制造行業(yè)的生產(chǎn)效率和生產(chǎn)質(zhì)量有很大提高,近30年來,生產(chǎn)調(diào)度問題[1]已成為國內(nèi)外自動控制領(lǐng)域、計算機科學(xué)等領(lǐng)域的研究熱點.現(xiàn)代智能制造市場的需求越來越個性化、多樣化,使傳統(tǒng)的量產(chǎn)模式受到了極大的挑戰(zhàn).機器人制造單元在實現(xiàn)量產(chǎn)的同時,能夠保持小批量定制生產(chǎn)的靈活性,能夠更好地適應(yīng)當(dāng)前智能制造發(fā)展的需求,而合理的優(yōu)化調(diào)度是機器人制造單元整體控制的一個重要方面.制造企業(yè)為了在激烈的競爭環(huán)境中生存和發(fā)展,需要提供能夠滿足客戶各種需求的資源調(diào)度方案.單一目標的尋優(yōu)已經(jīng)滿足不了人們?nèi)粘Ｉ畹男枰?工業(yè)上對于優(yōu)化目標個數(shù)增多的要求使得求解問題的難度顯著增加.目前,調(diào)度問題的理論和實踐方法研究,仍不能滿足現(xiàn)實生產(chǎn)需求.傳統(tǒng)的優(yōu)化算法在解決復(fù)雜多目標問題中[2–5]常常效率低下,難以達到預(yù)期.智能優(yōu)化算法[6–9]通常是基于非劣解概念基礎(chǔ)上的現(xiàn)代啟發(fā)式算法,具有更好的處理高維多目標問題的能力.因此,在經(jīng)典車間調(diào)整理論的基礎(chǔ)上,本文要針對Pareto 支配關(guān)系在高維多目標優(yōu)化中的支配能力不足,將另外兩種支配關(guān)系與NSGA-III 算法相結(jié)合去對生產(chǎn)調(diào)度問題進行求解去解決機器人制造單元優(yōu)化上的多目標協(xié)同調(diào)度優(yōu)化問題.

1 問題描述

本文主要研究的是有關(guān)job-shop 類型的機器人的智能制造車間的搬運問題.Job-shop 類型的機器人制造單元主要由加工站、搬運機器人和控制系統(tǒng)等組成.根據(jù)車間調(diào)度的工業(yè)路線特點,可將job-shop 類型的機器人制造單元調(diào)度過程描述為:有n個工件J={J1,J2,···,Jn} 將在m臺加工機器M={M1,M2,···,Mm}上進行加工,其中M0為裝載站兼卸載站.每個工件Ji有p道加工工序Oij={Oi1,Oi2,···,Oip},且每個工件都有預(yù)先設(shè)定好的工序加工順序,所有的工序都嚴格按照預(yù)定的加工工序順序在m臺機器上進行.現(xiàn)已知每道工序的加工時間、每道工序?qū)?yīng)的加工機器和任意兩臺機器之間的搬運時間.如圖1所示:調(diào)度基本過程可描述為,首先,n個 工件在M0上等待加工,當(dāng)加工任務(wù)開始時,機器手按照工序順序,當(dāng)工件處于裝載區(qū)或工件上一道工序已完成時,從該工件所在位置上取走工件并搬運到該工件下一道工序?qū)?yīng)加工機器上,根據(jù)當(dāng)前加工機器狀態(tài)決定是否開始加工.當(dāng)最后一道加工工序完成后并由機器手將該工件搬運至卸載站上時,則為加工任務(wù)結(jié)束.

圖1 以搬運機械人為中心的制造單元

近年來,在生產(chǎn)過程中人們越來越關(guān)注能夠使多項決策目標都能得到滿足的生產(chǎn)調(diào)度方案.通?？紤]多個目標共同優(yōu)化的方案.同時,由于對環(huán)境問題的重視,本文又引入了加工總能耗,生產(chǎn)總成本等一系列的綠色調(diào)度目標.以下是本文要優(yōu)化的5 個目標:

1)最大完工時間:

2)加工總能耗:

3)交貨期提前量:

4)交貨期延遲量:

5)生產(chǎn)總成本:

其中,最大完工時間指所有工件完成加工后的總加工時間,N為工序總數(shù);Ci為第i個工件的完工時間.加工總能耗指調(diào)度過程中機器加工總功率與機器手搬運總功率之和.M為機器總個數(shù);Ni為第i個機器上的加工工序數(shù);tij為第i個機器上第j道工序的加工時間;Pm,i為第i個機器的加工功率;ti,idle為第i臺機器空載時間;Pi,idle為第i臺機器空載功率;Nb為機器手搬運次數(shù);tb,i為第i次 搬運所花費的時間;Pb為機器手拌搬運功率;tb,idle為機器手空載時間;Pb,idle為機器手空載功率.交貨期為制造企業(yè)交付加工產(chǎn)品的時間.若工件在理想交貨時間前完成生產(chǎn)則為提前,在理想交貨時間后完成則為延遲.N為工件個數(shù);DTj為第j工件的理想交貨時間;RTj為第j工件的實際交貨時間.生產(chǎn)總成本為加工所需電費與機床使用成本之和.coste為電價(單位能耗成本);Etotal為加工總能耗;Cu,i為第i臺機器單位時間的使用成本.

2 算法描述

NSGA-III[10]是Deb和Jain 在2014年提出來的用于處理多個優(yōu)化目標的進化優(yōu)化算法.其主要思路是在NSGA-II的基礎(chǔ)上引入了參考點機制,對于那些非支配并且接近參考點的種群個體進行保留,相比NSGAII 擁有優(yōu)秀的處理更高維度目標的能力.

2.1 NSGA-III 基本算法流程

本文以NSGA-III的算法基本框架,全局搜索以遺傳算法為基礎(chǔ),使用了一種符合調(diào)度問題特點的交叉變異策略,并提出了兩種更改支配關(guān)系的改進措施.改進后的NSGA-III 將具有更好的處理高維數(shù)據(jù)的能力,用于解決本文所提出的機器人制造單元的高維多目標調(diào)度問題.NSGA-III的算法流程如下.

Step 1.初始化,隨機產(chǎn)生大小為N的父代種群Pt.更新操作,父代通過交叉、變異產(chǎn)生大小為N的子代種群Qt,合并為大小為2N的種群Rt=Pt+Qt.

Step 2.計算目標值,通過非支配排序,將Rt劃分為不同的非支配層(F1,F2,···).

Step 3.選擇優(yōu)先級高的非支配子集保留到下一代,用S t來保留.設(shè)Fl為臨界層,臨界層為加上該層解數(shù)目大于等于N時的非支配層.若數(shù)目等于N則S t=S t∪Fi,i=1,2,···,l,否則S t=S t∪Fi,i=1,2,···,l?1. 令Pt+1=S t.用K=N?|Pt+1|來 記錄需要從Fl中補充的解的個數(shù).

Step 4.每一維度最大值作為極值點,最小值作為理想點,對每個解的目標值做歸一化處理.

Step 5.以極值點構(gòu)造超平面,產(chǎn)生均布的C(M+H?1,H)個參考點,M為維度數(shù),H為每維分割份數(shù).

Step 6.對S t中和Fl層中每個解找出距離最近的參考點分別進行關(guān)聯(lián).

Step 7.對于S t中關(guān)聯(lián)少的參考點,找出Fl層對應(yīng)參考點關(guān)聯(lián)的一個最近的解進行補充.每添加一個解,就將該解從Fl中刪除,并將S t中關(guān)聯(lián)解的個數(shù)更新排序.重復(fù)Step 7 直至補充K個解.

Step 8.返回Step 2,直至迭代次數(shù)達到預(yù)設(shè)值,對當(dāng)前解集進行非支配排序找出第一非支配層的解作為最終解集.

2.2 改進的NSGA-III

隨著目標數(shù)量的增加,算法對解的選擇壓力變小,基于Pareto 支配,解之間很難存在支配關(guān)系,這導(dǎo)致解集中很大部分的解都是非支配的.而算法本身就強調(diào)保留種群中的非支配解,所以在每一代種群中,就沒有太多的空間來保留新解.這樣就減緩了算法的搜索過程,使算法效率變得低下.使用改變支配關(guān)系的方法,將解的目標值進行調(diào)整,可以擴大每個解的支配空間,從而提高解之間的區(qū)分度.本文分別將Lorenz 支配和CDAS 支配與NSGA-III 結(jié)合來進行優(yōu)化.第2.2.1 節(jié)和第2.2.2 節(jié)分別介紹了 Lorenz 支配和CDAS 支配.

2.2.1 Lorenz 支配

Lorenz 支配(式(6))是將標準化后的每一個解的目標值,按照從小到大進行排列,之后在一個新列表里,第i個位置存放前i個目標值的和(i=1,2,···,m),m為維度數(shù).所有解的目標值f(x)都用Lorenz 修改過后,用此新的目標值f′(x)來進行非支配排序,修改過支配關(guān)系后,每個解的支配空間將會變大,每個解之間就有更好的區(qū)分度.

如圖2所示是一個雙目標的例子,對于解S,基于Pareto 支配區(qū)域為(a),經(jīng)Lorenz 支配S的支配空間增加到(a)、(b)、(c).圖2中,X是一個解序列所求出對應(yīng)的目標值的坐標.

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

2.2.2 CDAS 支配

CDAS 支配(式(7))如圖3所示,式中,r為該解的目標值點與原點之間的距離;ωi為該點與原點連線和第i維的夾角;φi為該點與第i維上一個可控的夾角,其大小由系數(shù)S控制.當(dāng)S=0.5時,CDAS 支配與Pareto支配效果相同;當(dāng)S<0.5時,CDAS 支配將使原目標值點的支配區(qū)域擴大;當(dāng)S>0.5時,CDAS 支配將使原目標值點的支配區(qū)域變小.圖3中,X是一個解序列所求出對應(yīng)的目標值的坐標.

圖3 解x 修改前后第i 維目標值

通過試驗發(fā)現(xiàn),當(dāng)S取0.25 時,求解多目標優(yōu)化問題的效果最佳.此時根據(jù)CDAS 支配將原目標值f(x)修改為f′(x),擴大該解的支配區(qū)域.

以雙目標優(yōu)化問題為例,如圖4所示,當(dāng)S=0.5,即Pareto 支配關(guān)系下解A、B、C 是互不支配的.取S=0.25,增大擴張角,從圖中虛線部分可以看到每個解的支配區(qū)域都有所擴大,解之間出現(xiàn)了更細微的序值分布,此時,3 個解從互不支配變?yōu)榻釨 支配解C.

圖4 CDAS 修改后解支配關(guān)系

3 實驗分析

為了驗證本文提出的改進算法的有效性,通過對本文算法與傳統(tǒng)的NSGA-Ⅲ算法進行對比.并從以下3 個方面來測試算法性能.

1)收斂性:反映解集與真實Pareto 前沿趨近程度.

2)多樣性:反映是否所得的Pareto 最優(yōu)解集中的解都分布在 Pareto 前沿上.

3)均勻性:反映所得的Pareto 最優(yōu)解集中的解在目標空間中分布的均勻程度.

本次實驗采用世代距離GD (generational distance)、反向世代距離IGD (inverted generational distance)和間距Spacing 作為評價算法性能的指標.其中,GD 用于評價解集收斂性,IGD 用于評價解集收斂性和多樣性的綜合性能,Spacing 評價解集均勻程度.

本文提出的改進優(yōu)化算法以 PyCharm Python 3.8為開發(fā)工具編程實現(xiàn),其中相關(guān)參數(shù)設(shè)置如下:實驗設(shè)計環(huán)境和配置為Intel(R)Core(TM) i5-7300HQ CPU@2.50、8.00 GB RAM、Windows 10 64 位操作系統(tǒng).交叉概率設(shè)為1.0,變異概率設(shè)為0.5,迭代次數(shù)設(shè)為50,種群大小設(shè)為40.表1中,Ind表示案例編號,J表示該案例工件個數(shù),M表示加工機器臺數(shù),S表示加工工序總數(shù),上標1為C-NSGA-III 算法測試結(jié)果,上標2為L-NSGA-III 算法測試結(jié)果,上標3為NSGA-III 算法測試結(jié)果,下標AVG為均值,SD為標準差,MIN為最小值.本文挑選了由小到中到大型的案例共10 個進行了實驗,用來測試本文所提出的算法的性能,各案例均按照一定規(guī)則隨機生成.每個案例運行10 次,取均值作為測試結(jié)果.

為了更好的描述最優(yōu)方案的調(diào)度過程,可以通過甘特圖來分析工件的加工順序與機器人的搬運順序,如圖5為案例CS-3-16-5的甘特圖.該案例包含3 個工件,5 臺加工機器,16 道工序.圖中,橫坐標為時間軸,縱坐標為加工機器序號,M0為裝載卸載站.純色矩形代表加工過程,虛線矩形代表工件在當(dāng)前機器上的等待時間,實線代表機器人帶載過程,虛線代表空載過程.“J00”代表工件0的第0 道工序,之后以此類推.則案例CS-3-16-5的加工過程可描述為:機器人將工件2 從M0 搬出至M3 進行工序J20的加工,搬運后機器人返回至M0 開始搬運工件0 至M1 進行工序J00的加工,隨后返回M0 搬運工件1 至M5 加工工序J10.隨后機器人轉(zhuǎn)至M3 取走在M3 上完成加工的且已在輸出緩沖區(qū)上等待的工件2,搬運至M2 加工工序J21.以此類推,直到所有工件加工結(jié)束.

圖5 案例CS-3-16-5 甘特圖

表1、表2、表3分別為C-NSGA-III、L-NSGAIII和NSGA-III 算法在GD、IGD、Spacing 上的對比結(jié)果.通過對比可以得出,C-NSGA-III和L-NSGAIII 都在GD 上表現(xiàn)良好,在絕大部分案例上數(shù)值都小于NSGA-III,且標準差不大,說明改進算法較為穩(wěn)定.在GD 最小值上,C-NSGA-III 始終為0,總體可得兩種改進算法在收斂性上都要優(yōu)于NSGA-III.但在IGD 值上,NSGA-III 幾乎始終占優(yōu),說明C-NSGA-III和LNSGA-III 在多樣性上會變差,分析原因是兩算法均加大了支配空間,它們的解相當(dāng)于Pareto 關(guān)系下的解的子集,所以解的多樣性會變差.比較Spacing 值可知,兩改進算法在解集均勻程度上,較優(yōu)于NSGA-III.總體來說,C-NSGA-III和L-NSGA-III 算法有效地提升了解集的收斂性和均勻性,在多樣性上表現(xiàn)一般.

表1 C-NSGA-III、L-NSGA-III 與NSGA-III 算法GD 指標對比表

表2 C-NSGA-III、L-NSGA-III 與NSGA-III 算法IGD 指標對比表

表3 C-NSGA-III、L-NSGA-III 與NSGA-III 算法Spacing 指標對比表

4 結(jié)論與展望

本文針對研究機器人制造單元的多目標協(xié)同調(diào)度問題,同時優(yōu)化5 個目標:最大完工時間,加工總能耗,交貨期提前量,交貨期延遲量及生產(chǎn)總成本.針對job-shop的特點,分別將Lorenz 支配和CDAS 支配與NSGAIII 結(jié)合來進行優(yōu)化并將結(jié)果與NSGA-III 進行比較,證明該算法有效.