基于NSGA-Ⅱ算法的液壓元件多目標柔性作業(yè)調(diào)度研究*

楊俊茹 李 賀 李瑞川 劉長譽 荊本雨③ 李 寧③ 張 建④

(①山東科技大學機械電子工程學院，山東 青島 266590; ②齊魯工業(yè)大學機械與汽車工程學院，山東 濟南 250301;③山東海卓電液控制工程技術(shù)研究院，山東 日照 276800;④日照海卓液壓有限公司，山東 日照 276800)

液壓元件制造業(yè)作為國家工業(yè)體系的基礎產(chǎn)業(yè)之一，影響著我國制造業(yè)發(fā)展水平的高低。液壓元件的生產(chǎn)模式由原來的種類少、訂單大逐步向種類多、訂單小轉(zhuǎn)變，并逐漸成為一種常態(tài)化的成產(chǎn)模式，該生產(chǎn)模式的極大地增加了生產(chǎn)管理的復雜性與難度[1-2]。

生產(chǎn)調(diào)度作為液壓元件制造車間管理的核心環(huán)節(jié)，是指將生產(chǎn)任務轉(zhuǎn)化為切實可行的生產(chǎn)計劃，同時對生產(chǎn)計劃進行實時的監(jiān)督和反饋，對制造效率、生產(chǎn)周期等都具有較大的影響[3-4]。液壓元件的生產(chǎn)模式為離散型、柔性化的生產(chǎn)模式，所以液壓生產(chǎn)車間調(diào)度問題為多目標柔性作業(yè)車間調(diào)度問題(MOFJSP)[5]。

設計合適的生產(chǎn)調(diào)度算法可以實現(xiàn)原材料、加工設備等的最優(yōu)利用，常用的智能調(diào)度優(yōu)化方法有遺傳算法(GA)[6]、模擬退火算法(SA)[7]、蟻群算法(ACO)[8]、粒子群算法(PSO)[9]和禁忌搜索法(TS)[10]等。其中，遺傳算法因運行簡單，隨機性強、易拓展、魯棒性強以及全局搜索迅速等優(yōu)勢在車間調(diào)度問題中應用廣泛[11]。但是，傳統(tǒng)的遺傳算法存在很多不足，如收斂時間長、部分范圍搜尋力低、缺乏標準等，因此，許多學者基于改進的GA算法對調(diào)度問題進行了研究。李耀華等[12]提出了一種基于自適應GA算法的航材優(yōu)化調(diào)度方法,能夠?qū)崟r解決民用飛機不同維修任務，優(yōu)化物料調(diào)度。張立果等[13]提出了一種求解多目標問題的雙層改進遺傳算法，基于完工時間、機器負載和機器總負載三因素完成了實例驗證，表明算法具有很高的可靠性。王召陽等[14]以遺傳算法為基礎，提出了一種帶有權(quán)重的生產(chǎn)調(diào)度算法，根據(jù)同一機器不同零件和同一零件不同工序分為多種情況，分別得出對應的加工和等待時間，根據(jù)零件加工權(quán)重，得到調(diào)度最優(yōu)解。

本文針對目前的研究現(xiàn)狀，采用帶精英策略的非支配排序改進遺傳算法來解決液壓生產(chǎn)車間內(nèi)的多目標柔性作業(yè)車間調(diào)度問題，運用工序和設備組合式進行編碼的辦法，充分表示工件的制造過程，基于工序和設備分別制定交叉和變異策略。通過實例分析，從最大完成加工時間、設備負荷率和生產(chǎn)成本3個指標對調(diào)度優(yōu)化結(jié)果進行評價，驗證了本改進算法的實用性和有效性。

1 車間調(diào)度模型

1.1 問題描述

以某企業(yè)液壓元件制造車間為平臺，進行生產(chǎn)調(diào)度問題的描述。該液壓元件多目標柔性化車間調(diào)度問題可表達為：n個零件{J1,J2,…,Jn}、q臺設備{M1,M2,…,Mq}，每個零件包括mn(m≥1)道工序，每道工序Oij可在設備Mp(p∈[1,q])上進行加工，需要對n個零件選擇加工裝備和制定加工順序，保證加工效率的最優(yōu)化。

同時需滿足以下約束條件：

(2)工序Oij在設備Mk上加工過程不能中止。

(3)零件的工藝路線預先設定，零件的加工必須嚴格遵守工藝路線，不能跨工序進行加工。

(4)每個零件只在某一指定設備上加工一次，同種零件加工優(yōu)先級相同。

選擇不同的生產(chǎn)調(diào)度方案，往往使得車間加工設備負荷率、加工成本及加工時間等指標差異巨大，極大地影響車間加工效率。選擇合適的調(diào)度方案，對于指導現(xiàn)場生產(chǎn)具有重大的意義。

1.2 數(shù)學模型

本文中的調(diào)度問題是指在滿足約束條件的前提下，基于加工時間、設備總負荷與成本3個指標進行多目標液壓元件生產(chǎn)車間調(diào)度的模型評價，其中參數(shù)定義如表1所示。

表1 參數(shù)定義

構(gòu)建適應度函數(shù)，如式(1)所示[15]：

f=min{g(Tmax,L,C)}

(1)

1.2.1 最大完成加工時間

在一批生產(chǎn)計劃中加工完成最后零部件的時間最短，此評價指標對產(chǎn)品的加工周期與生產(chǎn)所用的總時間有重大影響，其數(shù)學表達如式(2)所示：

Tt=min (max(Tti)),i=1,2,3,…,n

(2)

作業(yè)車間調(diào)度的結(jié)果是具體的生產(chǎn)計劃，即確定工件i的第j批的l工序在第m臺設備上的開工時刻如式(3)所示：

(3)

完工時間點如式(4)所示：

(4)

1.2.2 設備總負荷率

設備負荷率是指制造裝備在工作過程中主軸所承受的負載率，如果負載率過高會對設備造成損害，從而影響加工進程，所以設備負荷率是輔助調(diào)度方案合理性指標，其數(shù)學表達如式(5)所示：

(5)

1.2.3 加工總成本

加工制造一批產(chǎn)品所需要的所有成本稱為總成本，其中包括加工成本和原材料成本等主要成本，總成本是企業(yè)加工過程中的一個重要因素，所以成本因素是作為調(diào)度方案的一個參考和基礎，其數(shù)學表達如式(6)所示：

(6)

2 NSGA-Ⅱ算法求解MOFJSP

2.1 NSGA-Ⅱ算法

針對多目標問題，采用非支配排序和精英儲備策略，實現(xiàn)多目標定位制造，必須在多個目標上達成相對妥協(xié),使得總目標優(yōu)化。其總體流程圖如圖1所示。

其具體的運行步驟如下：

步驟1：隨機生成個體的初始化種群P0，判斷對所有個體的分級排序完成情況，并對未完成的個體進行非支配排序，計算個體非支配前端中的擁擠長度，直到遍布所有個體。

步驟2：對父代種群Pt執(zhí)行選擇、交叉、變異遺傳操作，產(chǎn)生子代種群Qt。

步驟3：將Pt與Qt合并產(chǎn)生種群大小為2N的新種群Rt，對Rt執(zhí)行快速非支配排序操作，得到各級非支配前端F1,F2,...,Fi。

步驟4：計算每級非支配前端Fi中個體的擁擠距離，按照錦標賽選擇機制優(yōu)選出N個個體，組成新父代種群Pt+i。

步驟5：判斷進化代數(shù)是否大于最大代數(shù)，滿足終止條件則循環(huán)結(jié)束，否則Gen=Gen+1然后轉(zhuǎn)到步驟2。

步驟6：結(jié)束整個流程，得到Pareto最優(yōu)的解集。

2.2 編碼與解碼

2.3 交叉操作

交叉是隨機將兩條染色體上的幾個基因交叉變換得到新染色體的過程。根據(jù)上述編碼方法，本文采取工序及裝備染色體差異交叉，以保障調(diào)度解適用性。本文采用兩種交叉策略，即基于工序的POX交叉策略和基于設備的MPX交叉策略。

工序染色體基因串POX交叉實施，如圖4所示。

(1)根據(jù)部件集合分散出非空互補子集H1和H2。

(2)將基因串P1中包含在H1中的工序復制到B1，基因串P2中包含在H2中的工序復制到B2，確?；蛭恢貌蛔儭?/p>

(3)將基因串P2中包含在H2的工序復制到B1，基因串P1中包含在H1的工序復制到B2，確保相對位置不變。

設備染色體基因串MPX交叉實施，如圖5所示：

(1)隨機生成基因串R，R的元素只能為0或1，且與設備基因串P1和P2的元素個數(shù)相同。

2.4 變異操作

變異的目標是提高種群多變性，用來阻斷算法早期收斂。也需交叉一樣需要對工序和設備染色體進行變異。

工序染色體基因串變異操作，如圖6所示：

指定一條工序染色體上的某一個基因，無規(guī)則與另一個染色體上的一個基因進行替換。

設備染色體基因串變異操作，如圖7所示：

(1)隨機的在一條染色體上挑選單個設備基因，如圖7陰影部分所示。

(2)將挑選的基因變異成別的基因完成基因串的變異。

2.5 選擇策略

NSGA-II算法同時對多個任務優(yōu)化處理，在單任務時，常用的選擇方法有輪盤賭、錦標賽等，但是對于多任務進行一起選擇時，則根據(jù)單體等級差別和同一級別非支配解排列結(jié)合法進行選擇。對于同等級非支配解排序的個體聚集距離可以用式(7)計算：

3 實例

本文基于某企業(yè)液壓元件制造車間，利用MATLAB R2016b進行仿真，以11個零件、6臺設備為例進行分析。采用NSGA-Ⅱ算法，算法主要參數(shù)如表2所示。

表2 算法主要參數(shù)

最大完工時間、設備的總負荷率、總成本的最優(yōu)值的進化過程如圖8所示， 實線和虛線分別代表NSGA-Ⅱ算法和GA算法的迭代結(jié)果。從優(yōu)化結(jié)果可以得到隨著迭代次數(shù)的增大，基于NSGA-Ⅱ算法的最大加工時間、設備總負荷以及總成本迭代優(yōu)化結(jié)果明顯低于基于GA算法的迭代優(yōu)化結(jié)果，收斂速度快、分布性好。

根據(jù)NSGA-Ⅱ算法的優(yōu)化結(jié)果，利用MATLAB 2016仿真軟件對生產(chǎn)調(diào)度計劃進行處理，生成對應的甘特圖如圖9所示。

4 結(jié)語

基于液壓元件生產(chǎn)車間實際生產(chǎn)調(diào)度狀況分析，提出了加工約束條件，建立了多目標柔性作業(yè)車間調(diào)度問題數(shù)學模型。采用帶精英策略的非支配排序改進遺傳算法(NSGA-Ⅱ)，對液壓車間進行了生產(chǎn)調(diào)度分析，從最大完成加工時間、設備負荷率及生產(chǎn)成本3個指標對調(diào)度結(jié)果進行評價，仿真結(jié)果與傳統(tǒng)遺傳算法的比較，結(jié)果顯示其性能比傳統(tǒng)遺傳算法更加優(yōu)異。