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

楊俊茹 李 賀 李瑞川 劉長(zhǎng)譽(yù) 荊本雨③ 李 寧③ 張 建④

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

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

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

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

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

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

1.1 問(wèn)題描述

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

同時(shí)需滿足以下約束條件：

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

(3)零件的工藝路線預(yù)先設(shè)定，零件的加工必須嚴(yán)格遵守工藝路線，不能跨工序進(jìn)行加工。

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

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

1.2 數(shù)學(xué)模型

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

表1 參數(shù)定義

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

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

(1)

1.2.1 最大完成加工時(shí)間

在一批生產(chǎn)計(jì)劃中加工完成最后零部件的時(shí)間最短，此評(píng)價(jià)指標(biāo)對(duì)產(chǎn)品的加工周期與生產(chǎn)所用的總時(shí)間有重大影響，其數(shù)學(xué)表達(dá)如式(2)所示：

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

(2)

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

(3)

完工時(shí)間點(diǎn)如式(4)所示：

(4)

1.2.2 設(shè)備總負(fù)荷率

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

(5)

1.2.3 加工總成本

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

(6)

2 NSGA-Ⅱ算法求解MOFJSP

2.1 NSGA-Ⅱ算法

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

其具體的運(yùn)行步驟如下：

步驟1：隨機(jī)生成個(gè)體的初始化種群P0，判斷對(duì)所有個(gè)體的分級(jí)排序完成情況，并對(duì)未完成的個(gè)體進(jìn)行非支配排序，計(jì)算個(gè)體非支配前端中的擁擠長(zhǎng)度，直到遍布所有個(gè)體。

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

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

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

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

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

2.2 編碼與解碼

2.3 交叉操作

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

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

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

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

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

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

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

2.4 變異操作

變異的目標(biāo)是提高種群多變性，用來(lái)阻斷算法早期收斂。也需交叉一樣需要對(duì)工序和設(shè)備染色體進(jìn)行變異。

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

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

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

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

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

2.5 選擇策略

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

3 實(shí)例

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

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

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

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

4 結(jié)語(yǔ)

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