改進NSGA-Ⅱ算法求解考慮運輸約束的柔性作業(yè)車間節(jié)能調(diào)度問題

王亞昆,劉應波,吳永明+,李少波,宗文澤

(1.貴州大學 公共大數(shù)據(jù)國家重點實驗室,貴州 貴陽 550025;2.貴州大學 現(xiàn)代制造技術(shù)教育部重點實驗室,貴州 貴陽 550025;3.云南財經(jīng)大學 云南省經(jīng)濟社會大數(shù)據(jù)研究院,云南 昆明 650231)

0 引言

隨著科學技術(shù)的發(fā)展以及先進制造技術(shù)的普及,制造業(yè)面臨著生存壓力,例如人工成本、設備更換、和先進制造觀念的更新。為降低生產(chǎn)成本,許多制造企業(yè)致力于提高能源利用率和加工效率。為實現(xiàn)這一目標,最高效且低成本的方法就是優(yōu)化調(diào)度。面對市場需求的多樣化和加工技術(shù)的更新,生產(chǎn)和制造模式也開始朝著方便和靈活的方向發(fā)展。在實際生產(chǎn)環(huán)境中,生產(chǎn)計劃系統(tǒng)往往受多種隨機動態(tài)事件影響,如車間里各個工件在加工機器之間的運輸需要時間、機器故障、意外處理時間、緊急訂單的隨機到達、訂單取消等[1-2]。這些動態(tài)事件將導致理想調(diào)度與實際加工存在偏差或者不可行。因此,企業(yè)要想更加適應于真實環(huán)境下的車間調(diào)度,考慮動態(tài)事件對公司收入和應對不斷變化的市場環(huán)境具有重要的意義。

多目標柔性作業(yè)車間調(diào)度是單目標車間調(diào)度的擴展,單目標通常以最小化最大制造時間為優(yōu)化目標[3]。目前,隨著客戶需求多樣化、全球化和環(huán)境壓力,車間加工過程中必須滿足對多個目標約束,例如必須按工期加工完成零件、減少能源消耗或環(huán)境影響、考慮加工過程中機器的負載。因此,近幾年大量的學者致力于車間調(diào)度的多目標研究。GAO等[4]考慮最小化制造時間、最大機器工作量、總工作量3個目標,提出了基于本地搜索改進的遺傳算法,并取得了較好的求解效果。李益兵等[5]為減少碳排放量、噪聲、和廢棄物建立優(yōu)化完工時間和環(huán)境污染程度的模型(Multi-objective Green Flexible Job-shop Scheduling Problem,MGFJSP),并提出改進的人工蜂群算法來求解該模型。DING等[6]提出一種改進的粒子群算法來解決流水車間調(diào)度問題(Flexible Job-shop Scheduling Problem,FJSP),并通過改進編碼/解碼方案、粒子間的通訊機制以及候選機器規(guī)則,得到了較優(yōu)調(diào)度方案。YIN等[7]針對靈活的作業(yè)車間環(huán)境,提出一種新的低碳數(shù)學調(diào)度模型,該模型可優(yōu)化生產(chǎn)率、能源效率和降噪。杜士卿等[8]為減少生產(chǎn)時間、保證工件的加工質(zhì)量、降低車間的能耗建立混合車間調(diào)度模型,提出一種最佳覓食算法來求解該模型。LI等[9]提出了能源意識型柔性作業(yè)車間調(diào)度問題,建立了該問題的數(shù)學模型,并使用改進的遷徙鳥算法求解該問題。王建華等[10]針對車間綠色調(diào)度問題,建立了優(yōu)化最大完工時間、機器總負荷、車間能耗3個目標的數(shù)學模型,并設計了一種自適應多目標Jaya算法求解該優(yōu)化問題。

車間加工的環(huán)境是復雜的,越來越多的學者關(guān)注于車間動態(tài)環(huán)境,例如：CHEN等[11]研究了帶有機器故障的多目標車間調(diào)度,建立了以最小化制造時間和總機器工作量的多目標動態(tài)調(diào)度模型,根據(jù)故障機器的處理情況提出一種重調(diào)度策略,并采用非支配遺傳算法求解該模型。SAHAR等[12]研究了具有隨機機器故障的兩階段柔性作業(yè)車間調(diào)度,同時考慮制造時間和魯棒性兩個目標,并提出帝國主義競爭算法、遺傳算法與模擬技術(shù)混合解決該問題。GONG等[13]提出一種具有工人靈活性的節(jié)能車間調(diào)度模型,同時考慮了機器和工人的靈活性以及處理時間、能耗、和工人成本的相關(guān)因素,然后提出一種混合進化算法(Hybrid Evolutionary Algorithm,HEA)來解決該模型。LEI等[14]研究了具有間隔處理時間和異構(gòu)資源的雙資源約束的車間調(diào)度問題,以最小化碳排放量和最大完工時間為優(yōu)化目標,提出一種動態(tài)鄰域搜索算法解決該問題。吳秀麗等[15]提出考慮裝卸車間調(diào)度問題,以最小化完工時間與裝卸時間建立該問題的數(shù)學模型,并使用非支配遺傳算法求解該問題。GAO等[16]研究了具有模糊處理時間和新作業(yè)的插入兩個約束條件車間調(diào)度模型,并提出一種改進的兩階段人工蜂群算法求解該模型。

在現(xiàn)實的加工環(huán)境中,零件的相鄰工序不在同一個機器加工,需要車間的運輸系統(tǒng)將工件在機器間運輸,并且需要一定時間,然而傳統(tǒng)的車間調(diào)度問題往往忽略工件在機器間的運輸約束,近年來,越來越多的學者關(guān)注該問題。DAI等[17]提出了一種考慮運輸時間的節(jié)能作業(yè)車間調(diào)度問題,最大程度地降低綜合能耗和制造期,并設計了一種增強的分布估計算法來解決該問題。HUANG等[18]研究了考慮運輸時間的多目標車間調(diào)度問題,并混合遺傳算法與模擬退火算法求解該問題。ZHANG等[19]以運輸時間和處理時間作為獨立時間,建立具有運輸時間的車間調(diào)度模型,并使用改進的遺傳算法解決該問題。李香怡等[20]考慮工件在車間加工過程中,運輸時間對調(diào)度結(jié)果的影響,建立最小化完工時間、碳排放量、機器負載的調(diào)度模型,并用改進粒子群算法求解該模型。HOMAYOUNI等[21]考慮到車間加工過程中,工件的運輸問題常被忽略,提出混合整數(shù)線性規(guī)劃模型來解決該問題,并展示它在求解小型實例最優(yōu)解的效率。

對考慮運輸約束節(jié)能柔性作業(yè)車間調(diào)度問題(Transportation constraint Energy-saving FJSP,TEFJSP)研究處于起步階段,目前存在如下問題：①關(guān)于車間調(diào)度研究大多數(shù)是多目標優(yōu)化問題,目標通常為最小化最大完工時間、車間能耗、機器總工作量、碳排放量,但是這些研究中通常忽略工件在不同機器之間的運輸這一實際約束,導致求解的調(diào)度方案與實際的加工環(huán)境有很大的偏差。②目前文獻對具有運輸約束的車間調(diào)度研究缺少相關(guān)的通用數(shù)學模型、缺少考慮運輸約束之后對車間能耗的影響。本文在以上文獻研究成果的基礎上,提出考慮運輸約束車間調(diào)度問題,并建立該問題的數(shù)學模型,該模型優(yōu)化最大完工時間、延期、設備總負載、車間總能耗4個目標。③在求解考慮運輸約束的柔性作業(yè)車間調(diào)度問題,傳統(tǒng)的編碼、解碼方法不適用。因此,本文針對該問題建立了考慮運輸約束的節(jié)能柔性作業(yè)車間調(diào)度模型,同時設計了新的編碼、解碼方法。

1 問題描述和數(shù)學模型

1.1 TEFJSP問題描述

考慮運輸約束的節(jié)能柔性作業(yè)車間調(diào)度問題可以描述為：存在n個待加工工件J={J1,J2,...,Jn},需要在m臺機器上進行加工M={M1,M2,...,Mn},每個工件Ji有Ni個工序Oi={Oi,1,Oi,2,...,Oi,Ni}需按順序加工,每個工序Oi,j可以由該工序的備選加工機器Mi,j?M唯一確定的加工。每個工序備選集中的機器加工該工序消耗的加工時間、加工能耗、運輸時間均不同。工件Ji的Oj,Ni-1工序在機器Mp上加工完成后,若工序Oj,Ni不在同一臺機器上加工,則需要車間的運輸系統(tǒng)AGV將該工件運輸?shù)较乱还ば蚣庸さ臋C器Mq加工,并且AGV需要消耗能量。AGV在不同的機器之間運輸工件花費的時間不同,消耗的能耗也不同。TEFJSP為每個工序選擇唯一的機器加工和確定每個機器加工各個工序的開始時間和結(jié)束時間,并確定每個工件相鄰加工工序在各個機器間的運輸時間,TEFJSP約束條件如表1所示。

表1 TEFJSP約束條件

1.2 TEFJSP符號定義

TEFJSP符號及意義如表2所示。

表2 TEFJSP符號定義

1.3 TEFJSP數(shù)學模型

該模型中變量定義以下：

Cj,h為工序Oj,h完工時間的連續(xù)變量。

車間調(diào)度的數(shù)學模型表示如下：

(1)

式中：ML為機器負載,TE為車間總耗。

車間在加工這批零件時需要消耗的總能量主要包括機器加工能耗(Ebusy)、機器空轉(zhuǎn)能耗(Eidle)、運輸能耗(Etran)和其他能耗(Eother)4個部分。

(2)

(3)

Etran=∑T×Wtran;

(4)

Eother=Cmax×Wother。

(5)

其他約束：

(6)

(7)

(8)

Yj,1,0,k≤ej,1,k,j∈1,2,...,n,k∈1,2,...,m;

(9)

(10)

Yj,2,i,k≤Yj,1,0,i,j∈1,2,...,n,k,i∈1,2,...,m;

(11)

(12)

(13)

Cmax≥Cj,nj,j∈1,2,...,n;

(14)

Ti,j,h≥0,i∈1,2,...,m,j∈1,2,...,n,h∈1,2,...,nj;

(15)

Cj,h≥0,Cl,z≥0,j,l∈1,2,...,n,h,z∈1,2,...,nj;

(16)

Xi,j,h,Yj,h,i,k,Xl,z,j,h∈{0,1},i,k∈1,2,...,m,j,l∈1,2,...,n,h∈1,2,...,nj。

(17)

其中：式(6)約束每一個工序僅分配給一臺機器加工;式(7)約束任意工件的第一個工序Oj,1由虛擬機器0運輸?shù)焦ば騉j,1的加工機器Mi加工;式(8)和式(9)約束工序Oj,h的加工機器必須在該工序備選機器中選擇;式(10)和式(11)約束工序Oj,h在機器Mi上加工,工序Oj,h+1在機器Mk上無干擾加工;式(12)和式(13)約束工序Oj,h完工時間不小于Oj,h-1的完工時間與Oj,h的運輸時間、加工時間之和;式(14)約束最大完工時間不小于每個零件的完工時間;式(15)約束工序在每個機器之間的運輸時間不小于0;式(16)約束每個工序的完工時間不小于0;式(17)約束相關(guān)變量為二進制變量。

2 改進NSGA-Ⅱ求解TEFJSP

2.1 編碼

圖1 染色體編碼

如圖1所示,染色體長度L=8,工序編碼層順序為“2 1 3 3 3 1 2 1”,其中第1個位置數(shù)字“2”表示工序O2,1,第2個位置數(shù)字“1”表示工序O1,1,第4個位置數(shù)字“3”表示工序O3,2。基于機器編碼為“2 1 3 4 4 2 1 3”,第1個位置“2”表示工序O2,1在機器M2上加工,第2個位置數(shù)字“1”表示工序O1,1在機器M1加工,第4個位置上“4”表示工序O3,2在機器M4加工。運輸時間層編碼為“0.8 0.5 0.6 1 0 0.9 1.3 1.4”,第一個位置數(shù)字“0.8”表示加工工序O2,1從虛擬機器M0運輸0.8到機器M2加工,第2個位置數(shù)字“0.5”表示加工工序O1,1從虛擬機器M0運輸0.5到機器M1加工,第4個位置數(shù)字“1”表示加工完成工序O3,1需要運輸1運輸?shù)焦ば騉3,2的加工機器M4。該染色體所對應工序的加工順序為：O2,1(M2,0.8)-O1,1(M1,0.5)-O3,1(M3,0.6)-O3,2(M4,1)-O3,3(M4,0)-O1,2(M2,0.9)-O2,2(M1,1.3)-O3,1(M1,1.4),括號中為該工序使用機器和運輸時間。

2.2 解碼

解碼是將編碼轉(zhuǎn)化成調(diào)度方案,傳統(tǒng)插入式貪婪解碼方法不再適用于求解TEFJSP[22],本文設計一種考慮運輸約束插入式貪婪解碼方法。具體解碼方法如下：

(1)工序Oj,1是工件J的第一個工序,且工序Oj,1對應的加工機器Mi是首次使用,則工序Oj,1從虛擬機器“0”運輸?shù)焦ば騉j,1加工機器Mi后直接開始加工。

(2)工序Oj,h非工件J第一個工序,且工序Oj,h對應的加工機器Mi是第一次使用,則工序Oj,h -1加工完成后運輸?shù)綑C器Mi即刻開始加工。

(3)工序Oj,h非工件J第一個工序,且工序Oj,h加工使用機器Mi也非第一次使用,在使用可插入式解碼時必須考慮工序在機器加工時產(chǎn)生的空閑時間,例如機器Mi加工k個工序,則會產(chǎn)生k個空閑時間,考慮這些空閑時間是否滿足工序Oj,h插入加工分為以下幾種情況：

1)滿足可插入式解碼第1種情況如圖2所示。

圖2 工序Oj,h可插入式解碼第1種情況

Cj,h-1+Tj,k,i≤Cl,z-1;Cl,z-1+Pj,h,i≤Sl,z。

(18)

該種情況工序Oj,h在機器Mi加工,Mi空閑時間與工序Oj,h加工時間和運輸時間滿足約束式(18),此時工序Oj,h在機器Mi的開始加工時間Sj,h=Cl,z-1。

2)滿足可插入式解碼的第2種情況如圖3所示。

圖3 工序Oj,h可插入式解碼第2種情況

Cj,h-1≤Cl,z-1;Cj,h-1+Tj,k,i≥Cl,z-1;Cj,h-1+Tj,k,i≤Sl,z。

(19)

該種情況工序Oj,h在機器Mi加工,Mi空閑時間與工序Oj,h加工時間和運輸時間滿足約束式(19),此時工序Oj,h在機器Mi開始加工時間Sj,h=Cj,h-1+Tj,k,i。

3)滿足插入式解碼的第3種情況如圖4所示。

圖4 工序Oj,h可插入式解碼第3種情況

Cj,h-1≥Cl,z-1;Cj,h-1+Tj,k,i+Pj,h,i≤Sl,z。

(20)

該種情況工序Oj,h在機器Mi加工,Mi空閑時間與工序Oj,h加工時間和運輸時間滿足約束式(20),此時工序Oj,h在機器Mi開始加工時間Sj,h=Cj,h-1+Tj,k,i。

4)不滿足插入式解碼的情況如圖5所示。

圖5 工序Oj,h不滿足可插入式解碼

Cj,h-1+Tj,k,i+Pj,h,i>Sl,z。

(21)

這種情況機器Mi的空閑時間不足以滿足工序Oj,h插入加工,因此工序Oj,h安排在機器還未使用時間段,工序Oj,h開始加工時間Sj,h=Cl,z。

2.3 帕累托分級排序

非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithms,NSGA)是由SRINIVASAN等[23]在1994年提出,該算法采用分級選擇算法選擇出優(yōu)秀個體,在迭代過程中采用小生境法維持優(yōu)秀個體的穩(wěn)定性。NSGA-II算法的非支配排序是根據(jù)種群內(nèi)各個個體的支配關(guān)系劃分為不同的支配前端,支配關(guān)系反映了個體的優(yōu)劣程度,通過支配關(guān)系和擁擠度篩選出種群中優(yōu)秀個體。非支配排序后得到X個非劣前沿(用P1,P2,...,PX表示),各個非劣前沿滿足以下性質(zhì)：

(1)?h,f∈{1,2,...,X},且h≠f,Ph∩Pf=?,非支配排序后種群中各個個體相互獨立。

(2)U∈{P1,P2,...,PX}P=Pop,非支配排序前后種群規(guī)模不變。

(3)P1>P2>…>PX,非支配排序后種群分成X個非劣前沿。

種群中每個個體進行非支配排序后對應兩個參數(shù),個體h所支配個數(shù),用sh表示;支配個體h個數(shù),用nh表示。則有：

nh=|{z|z?h,h,z∈Pop}|;

sh=|{f|h?f,h,f∈Pop}|。

種群中nh=0的個體記為非支配前沿F1,記F1中的個體rank值為1;將F1中的其他個體按nz=nz-1=0的規(guī)則分配至下一等級非劣前沿,每次迭代均遍歷種群中所有個體,為每個個體分配對應非劣前沿。

2.4 選擇

經(jīng)過帕累托分級排序后,種群中每個個體都分配一個非劣前沿等級號。個體適應度值越優(yōu),非劣前沿等級號越小,可以通過比較非劣前沿等級號來選擇較優(yōu)個體。本文采用錦標賽法,設置兩名選手進行參賽,比較兩個參賽選手的非劣前沿等級號,值較小的個體獲勝直接遺傳到下一代。如果兩個參賽選手非劣前沿等級號相同,采用小生境技術(shù)選擇較小擁擠度個體保留到下一代。迭代l代第t個目標函數(shù)最佳小生境計算方法[24]如下：

(22)

式中：flt為迭代l代第t個目標的函數(shù)值,n為目標個數(shù),Pop為種群規(guī)模。

2.5 交叉與變異

本文染色體的編碼方式采用三層矩陣編碼,一條染色體包含工序加工順序信息、機床選擇信息、運輸時間信息。染色體在進行交叉、變異操作時,工序的加工順序發(fā)生變化或工序加工選擇的機器發(fā)生變化時,運輸時間編碼層的基因可能會發(fā)生變化,而工序?qū)泳幋a和機器層編碼確定后運輸時間編碼層的基因就已經(jīng)確定,因此工序編碼和機器編碼為顯性基因參與交叉、變異操作,運輸時間編碼為隱形基因不參與交叉、變異操作,但是該基因隨顯性基因的變化自我調(diào)整。因此本文的交叉和變異操作主要有工序編碼層的交叉和變異操作和機器編碼層交叉和變異操作。

(1)工序編碼層交叉操作 染色體執(zhí)行工序的交叉操作,只改變工序的加工順序,不改變每個工序加工使用機器。例如有N個工件,隨機生成集合n,滿足n?{1,2,...,N},n中元素為染色體的穩(wěn)定基因,父代P1、P2找出集合n中表示的工件在染色體上的位置和順序,直接遺傳給后代,未被選中的父代基因交換后按順序的插入到子代中,運輸時間編碼層重新調(diào)整后生成新的子代。3個工件8個工序兩條有效染色體,隨機生成的集合n={1},工序編碼層交叉過程如圖6所示。

圖6 工序編碼層交叉操作示意圖

(2)機器編碼層交叉操作 染色體執(zhí)行機器的交叉操作,只改變工序使用的加工機器,不改變工序的加工順序。例如有N個工件,隨機生成一個集合n,滿足n?{1,2,...,N},父代P1、P2找出集合n中表示的工序?qū)募庸C器,將對應工序加工機器互換,調(diào)整運輸時間生成新的個體。這種機器編碼層交叉操作簡單、易于實現(xiàn),并且能夠保證染色體的有效性。3個工件8個工序的兩條有效染色體,隨機生成的集合n={1},機器編碼層交叉操作過程如圖7所示。

圖7 機器編碼層交叉操作

NSGA-Ⅱ算法在求解多目標優(yōu)化問題時很容易陷入局部最優(yōu),為解決該問題,算法在跌代過程中,迭代前期希望變異率較小有利于保留較優(yōu)的個體,迭代后期希望變異率較大有利于避免“早熟”。因此本文采用自適應變異率。迭代l代的變異率如式(23)所示：

(23)

式中：l為迭代次數(shù),lmax為最大迭代次數(shù),k1設置變異率最小值,k2設置變異率最大值。

(3)工序編碼層變異 染色體的工序編碼發(fā)生變異時,對應工序使用的加工機器不變。為保證染色體的有效性,本文采用兩點互換式變異。操作過程如下：

步驟1隨機生成在染色體范圍內(nèi)的兩個位置點。

步驟2將兩個位置工件對應的加工機器編碼存儲在兩個變量variable1,variable2中。

步驟3將兩個位置的工序互換。

步驟4兩個工件加工機器編碼按照var1、var2機器的順序?qū)迦搿?/p>

步驟5調(diào)整染色體的運輸時間,生成新的染色體。

工序編碼層操作過程如圖8所示。

(4)機器編碼層變異 隨機選擇染色體上的一個位置,將該位置機器編碼層基因突變,突變方式為從該工序的備選機器中選擇一個機器替換原機器。如圖9所示,3個工件8個工序的兩條有效染色體,隨機生成的突變位置為4,該染色體位置對應的工序為O2,2,可以加工該工序的機器為M1M2M3M4,目前加工該工序的機器為M1,從該工序的備選機器中選擇新的加工機器為M3。

圖9 機器編碼層變異操作

圖10 學習生成后代示意圖

2.6 學習

NSGA-Ⅱ隨機生成染色體、交叉、變異都有一定的盲目性,大多情況下陷入局部最優(yōu)解不能跳出,為解決該問題本文引入的學習機制改進NSGA-Ⅱ。學習機制是子代學習前代最優(yōu)解染色體優(yōu)良基因,提升子代個體的良率。最優(yōu)解在工序編碼、機器編碼均屬于較優(yōu)基因,后代對最優(yōu)解的學習,繼承了最優(yōu)解的這些信息,加快算法求得全局最優(yōu)解的速度。學習機制執(zhí)行過程如下：

步驟1從最優(yōu)解染色體長度范圍內(nèi)隨機選擇兩個位置。

步驟2將兩個位置之間的基因段直接復制給子代對應染色體位置。

步驟3剩余左側(cè)的基因段打亂順序后賦值給子代左側(cè)基因段,剩余右側(cè)基因段打亂順序后賦值給子代右側(cè)基因段,根據(jù)工件在機器之間的運輸時間,調(diào)整運輸時間編碼層生成新的子代染色體。

引入學習機制的NSGA-Ⅱ算法記為(Learning-NSGA-Ⅱ,L-NSGA-Ⅱ),每代學習操作生成個體數(shù)記為Lc。采用子代學習父代優(yōu)良信息改進的NSGA-Ⅱ,加快算法獲得全局最優(yōu)解的速度,改善NSGA-Ⅱ算法的性能。

2.7 選擇最優(yōu)加工方案

由于最大完工時間、能耗、總延期、設備總負載各目標之間存在對立,在多目標優(yōu)化問題中不存在單一的最優(yōu)解決方案[25],眾多最優(yōu)方案之間相互非支配,組成帕累托前沿。從帕累托前沿中決策出最優(yōu)方案的方法有很多,其中最流行的就是歸一化加權(quán)法,該方法具有簡單性和高效探索能力,常用于生產(chǎn)調(diào)度多目標決策問題。具有t個目標歸一化加權(quán)法定義為：

(24)

(25)

式中fs,max與fs,min分別為目標fs的最大值和最小值。

求解多目標決策問題時,決策者往往針對各個目標的重視程度不同,而賦予各個目標不同權(quán)重,以示對該目標的重視程度。但是多目標問題中往往對一些目標有一些特殊的要求,例如在多目標車間調(diào)度問題中,多目標包含總延期時,如果訂單不能如期完成,不但會對工廠有很嚴重的懲罰,而且會影響工廠的信譽,因此車間調(diào)度的多目標問題涉及到總延期的目標,通常該目標約束為0。為了適應對多目標問題選擇出最優(yōu)加工方案對某一目標有特殊要求,本文采用從帕累托前沿剔除法,先從帕累托前沿剔除不符合要求的方案,再采用歸一化加權(quán)法選出最優(yōu)的加工方案。L-NSGA-Ⅱ算法執(zhí)行過程如圖11所示。

圖11 L-NSGA-Ⅱ算法的執(zhí)行過程

3 仿真實驗分析

為了測試L-NSGA-Ⅱ算法的性能,在處理器為Intel(R) Core(TM) i5-6500 CPU @ 3.20 GHz,基帶RAM 8.00 GB,64位Win 10操作系統(tǒng),安裝MATLAB R2018a的實驗環(huán)境,測試Kacem算例[26]、Brandimarte算例[27],這兩組算例包含的工件數(shù)從3～15不等,機器從5～10不等,測試該算法在求解小型算例、中型算例、大型算例的性能。這兩組算例中僅包含工件在各個機器的加工信息,本文隨機生成運輸時間,15臺機器間的運輸時間如表3所示,機器的能耗信息如表4所示,經(jīng)多次實驗最優(yōu)組合參數(shù)設置為：種群數(shù)量Pop=100、迭代次數(shù)lmax=200,最小變異率k1=0.1,最大變異率k2=0.8,交叉率px=0.8,學習生成子代個數(shù)Lc=20。目標權(quán)重參數(shù)為：總延期為0,最大完工時間權(quán)重w1=0.5,設備總負載權(quán)重w3=0.2,車間總能耗權(quán)重w4=0.3。

表3 機器之間的運輸時間 s

表4 加工機器的能耗信息 kW/h

Kacem與Brandimarte算例求解結(jié)果如表5所示,TEFJSP相較于FJSP在完工時間、總能耗均有明顯增多,并隨著算例規(guī)模的增大,完工時間和總能耗偏差更大。采用L-NAGA-Ⅱ算法求解TEFJSP相比于NAGA-Ⅱ算法有明顯優(yōu)勢,兩組算例中有13個算例在最大完工時間求解的目標值較優(yōu)、9個算例在設備總負載求解的目標值較優(yōu),13個算例在車間總能耗求解的目標值較優(yōu),11個算例在求得最優(yōu)解體現(xiàn)出更高的效率。體現(xiàn)出L-NAGA-Ⅱ算法在求解TEFJSP時的優(yōu)越性能。

表5 Kacem與Brandimarte算例求解結(jié)果

Brandimarte組第4個算例KM04不考慮運輸約束調(diào)度甘特圖如圖12所示,該算例考慮運輸約束車間調(diào)度甘特圖如圖13所示,NSGA-Ⅱ與L-NSGA-Ⅱ求解該算例TEFJSP問題迭代過程圖如圖14所示。KM04算例FJSP調(diào)度方案求解結(jié)果為：最大完工時間72,總延期0,設備總負載343,能耗總量99.31 kW,TEFJSP問題的求解結(jié)果為：最大完工時間72.6,總延期0,設備總負載344,能耗總量119.34 kW。從兩問題的求解結(jié)果可以看出,TEFJSP問題的調(diào)度方案最大完工時間延后0.6,能耗總量增加20.03 kW。NSGA-Ⅱ與L-NSGA-Ⅱ算法求解TEFJSP問題迭代過程圖如圖14所示,實線的迭代過程為L-NSGA-Ⅱ算法的迭代過程,該算法迭代49代時求得最優(yōu)權(quán)重適應度140.901,虛線迭代過程為NSGA-Ⅱ算法的迭代過程,在迭代至48代時陷入局部最優(yōu)解。

圖12 MK04算例不考慮運輸約束調(diào)度甘特圖

圖13 MK04算例考慮運輸約束調(diào)度甘特圖

圖14 KM04算例NSGA-Ⅱ與L-NSGA-Ⅱ迭代過程圖

4 結(jié)束語

本文針對傳統(tǒng)柔性作業(yè)車間調(diào)度通常忽略加工過程中工件在各個機器之間的運輸時間等約束問題,提出了考慮運輸約束的節(jié)能柔性作業(yè)車間調(diào)度問題并建立該問題的數(shù)學模型,該模型優(yōu)化車間加工過程中最大完工時間、總延期、設備總負載、車間總能耗4個目標,并提出了更優(yōu)性能的L-NSGA-Ⅱ算法求解算法,即染色體四層矩陣編碼與可插入式解碼方法能更好地反映具有運輸約束的車間調(diào)度問題,同時獲得了更優(yōu)的車間調(diào)度方案。最后,未來研究希望探索一種更優(yōu)性能的多目標算法解決考慮運輸約束的柔性作業(yè)車間節(jié)能調(diào)度問題。