周爾民,馬 暢,劉 寧

(華東交通大學(xué)a.機電與車輛工程學(xué)院;b.交通運輸與物流學(xué)院,南昌 330013)

0 引言

動態(tài)的柔性車間調(diào)度問題是在柔性作業(yè)車間調(diào)度問題的基礎(chǔ)上延伸而來,因其考慮到車間實際加工生產(chǎn)過程中會受到緊急件插入、交貨期變更、機器故障、等各類不確定擾動的影響,所以是一種更符合實際生產(chǎn)環(huán)境的調(diào)度問題[1]。而機器故障作為加工車間常見擾動之一,具有隨機、離散分布的特點,故障發(fā)生前可能無法準(zhǔn)確預(yù)估其發(fā)生時刻點,以及需要的修復(fù)時間,因此當(dāng)機器故障發(fā)生時保證生產(chǎn)加工正常運行是關(guān)鍵,這就需要在故障發(fā)生時對當(dāng)前加工任務(wù)狀態(tài)和故障擾動程度進行評估分析,對原有的調(diào)度方案進行重新規(guī)劃。在故障發(fā)生后選擇合理的重調(diào)度方式,生成新的滿足既定目標(biāo)、偏離度小、響應(yīng)迅速的調(diào)度方案逐漸成為研究的重點[2]。

針對動態(tài)的柔性作業(yè)車間調(diào)度問題(dynamic flexible job-shop scheduling problem,DFJSP),學(xué)者們從問題的不同角度提出有效的動態(tài)調(diào)度方法[3-4]。SHAHGHOLI等[5]使用改進的人工蜂群算法通過在啟發(fā)式算法模型框架雙層編碼基礎(chǔ)上對工序編碼優(yōu)化,對機器編碼引入本地搜索進行優(yōu)化。GAO等[6]針對FJSP中存在的機器故障修復(fù)問題引入兩種新的局部搜索算子,有效地平衡重調(diào)度階段的穩(wěn)定性和完工時間。SHAHRABI等[7]提出了一種基于變量鄰域搜索的調(diào)度方法,在基于Q因子算法的強化學(xué)習(xí)框架中使用了新方法來計算學(xué)習(xí)過程中的獎勵值,并將該方法的實驗結(jié)果與常用調(diào)度規(guī)則進行對比。吳正佳等[8]構(gòu)建了機器故障發(fā)生后剩余工件約束數(shù)學(xué)模型,提出插入重調(diào)度的方式。劉壯等[9]考慮了不同的決策指標(biāo),以調(diào)度方案間的偏序關(guān)系為依據(jù)進行選取最優(yōu)重調(diào)度方案。尤一琛等[10]采用事件和周期混合驅(qū)動的方式設(shè)計組合重調(diào)度策略應(yīng)對機器故障的影響。

綜上所述,目前對機器故障動態(tài)調(diào)度的研究大部分針對算法層面的改進,或者在故障發(fā)生后直接采用事件和周期混合驅(qū)動的方式進行重調(diào)度。很少考慮周期重調(diào)度的驅(qū)動區(qū)間,以及機器故障概率不同對重調(diào)度方案的影響。本文采用事件和基于機器故障概率周期的混合驅(qū)動方式,通過求解加工機器發(fā)生故障的概率確定周期重調(diào)度驅(qū)動區(qū)間,即機器故障概率值越大則周期驅(qū)動區(qū)間越小。并采用熵值法確定引入評價指標(biāo)的權(quán)重系數(shù),設(shè)計了3種鄰域結(jié)構(gòu)提高算法局部搜索能力,利用改進的遺傳變鄰域算法對最優(yōu)重調(diào)度方案進行求解,最后通過案例分析驗證了該方法的有效性。

1 問題描述

FJSP可概括為:有i個工件,每個工件有j道工序,工件按照指定加工路線安排在在k個設(shè)備上,并使調(diào)度方案指標(biāo)最優(yōu)[11]。機器故障下的柔性作業(yè)車間調(diào)度是在初始化調(diào)度的基礎(chǔ)上,當(dāng)機器故障發(fā)生時,對未完成工件的加工設(shè)備、工序加工順序重新調(diào)整。

1.1 符號說明

本文的變量及符號定義如表1所示。

表1 模型參數(shù)符號及定義

決策變量:重調(diào)度方案中,如果第i個工件的第j道工序在機器k上加工,aijk則為1;否則為0。

原調(diào)度方案中,如果第i個工件的第j道工序在機器k上加工,aijko則為1;否則為0。

如果操作aij在重調(diào)度方案和原調(diào)度方案選擇的加工機器不同,aij則為1;否則為0。

1.2 重新調(diào)度約束條件

右移重調(diào)度約束條件如下:

(1)

式(1)表示右移重調(diào)度中受故障影響工件開始時間等于故障時刻加上故障設(shè)備修復(fù)時間;一個工件的一道工序只能在一臺機器上加工;一道工序的開始時間與加工時間之和等于結(jié)束時間。

完全重調(diào)度約束條件:

(2)

部分重調(diào)度約束條件:

(3)

式(2)表示在故障時刻點針對未加工工序?qū)嵤┩耆卣{(diào)度,生成新的加工列表下加工機器和加工工序、加工時間的約束關(guān)系。式(3)表示部分重調(diào)度條件下故障機器上未加工工件工序重新安排至剩余的加工機器,但不改變剩余機器上原有的工件工序,只改變加工時間和加工順序。

1.3 目標(biāo)函數(shù)

式(4)表示t時刻機器發(fā)生故障時對應(yīng)的最小化最大完工時間的數(shù)學(xué)模型:

(4)

式中:r表示發(fā)生故障機器數(shù)。

2 機器故障下的重調(diào)度方法

2.1 機器故障概率

生產(chǎn)加工過程中機器發(fā)生故障的概率Mfr由質(zhì)量參數(shù)、機器開動率和已工作時間共同決定。

(5)

式中:g1(g1>1)表示質(zhì)量參數(shù),值越大表示該類機器質(zhì)量越好;g2(0

2.2 組合重調(diào)度策略

針對何時進行重調(diào)度和如何進行重調(diào)度,采用異常事件和基于機器故障頻率的周期混合驅(qū)動策略,根據(jù)機器故障頻率設(shè)置合理的重調(diào)度周期區(qū)間,在保證加工車間調(diào)度穩(wěn)定性的同時,也能夠快速響應(yīng)突發(fā)的設(shè)備故障事件,從而更加有效地提高了系統(tǒng)的穩(wěn)定性。

2.3 重調(diào)度方式

重調(diào)度方案結(jié)合部分重調(diào)度、完全重調(diào)度[12]、右移重調(diào)度[13]3種重調(diào)度方式。部分重調(diào)度針對故障機器上未開始加工工序,重新安排其加工機器,沒發(fā)生故障的機器上加工工序保持不變,加工時間和加工順序均有變化,機器故障恢復(fù)時間未知時大多采用此調(diào)度方式。

2.4 重調(diào)度方案評價指標(biāo)

機器故障下重調(diào)度方案評價模型表達式為:

(6)

把最大完工時間偏差α、工序結(jié)束時間累積偏差值β和機器偏離成本γ作為評價指標(biāo),μ1、μ2、μ3為權(quán)重系數(shù),重調(diào)度評價指標(biāo)越小越好。

2.5 重調(diào)度流程

在整個調(diào)度過程中,原調(diào)度方案以最小化最大完成時間為目標(biāo),機器發(fā)生故障時,采用事件和基于故障概率的周期混合驅(qū)動策略,綜合使用右移重調(diào)度、完全重調(diào)度、部分重調(diào)度3種組合方式。在重調(diào)度方案優(yōu)選階段中,考慮到方案變動必然帶來額外成本增加以及加工生產(chǎn)穩(wěn)定性降低的問題,因而引入最大完工時間差值、工序結(jié)束時間差值和機器偏離成本作為評價指標(biāo),評價指標(biāo)權(quán)重系數(shù)采用熵值法確定,在3者生成方案中選擇生成的最優(yōu)方案。重調(diào)度流程如圖1所示。

圖1 重調(diào)度流程圖

3 遺傳變鄰域算法

在遺傳(genetic algorithm,GA)算法[14]的基礎(chǔ)上綜合使用變鄰域搜索(variable neighborhood search,VNS)算法,并設(shè)計了自適應(yīng)交叉算子和變異算子,以及基于VNS關(guān)鍵路徑的3種鄰域結(jié)構(gòu)。

3.1 染色體編碼與解碼

針對FJSP2個子問題工序排列和機器選擇,采用雙層編碼結(jié)構(gòu)對染色體完成編碼[15]。解碼時采用文獻[16]給出的插入式貪婪解碼。

3.2 交叉、變異操作

遺傳算子包括交叉算子和變異算子。染色體有機器字符串和操作字符串兩個字符串,為了避免在遺傳重組后產(chǎn)生不可行的解,對交叉算子和變異算子設(shè)計不同的方法。

3.2.1 交叉算子

針對編碼方式采用OS層染色體的IPOX交叉[17]。交叉概率隨迭代次數(shù)在(pcmin,pcmax)之間變化。

(7)

式中:pc表示交叉概率,pcmax表示最大概率,pcmin表示最小概率,genNum、iterNum分別表示生成次數(shù)和算法當(dāng)前迭代次數(shù)。

3.2.2 變異算子

變異算子用于保持種群的多樣性。變異概率也是自適應(yīng)的從pmmax更改為pmmin。開始時大的突變概率可以增強搜索空間以提高搜索能力,隨著變異概率的降低開發(fā)能力逐漸提高。

(8)

式中:pm表示突變概率,pmmax表示最大概率,pmmin表示最小概率,genNum、iterNum表示與式(7)相同。

3.3 鄰域結(jié)構(gòu)

在局部搜索中改變初始解周圍的有效鄰域結(jié)構(gòu)非常重要。圖2虛線部分展示了為4個工件在3個機器加工的關(guān)鍵路徑。

圖2 關(guān)鍵路徑圖

設(shè)計了3種基于關(guān)鍵路徑的鄰域結(jié)構(gòu),一是更換關(guān)鍵操作的加工機器;另外兩個是更改關(guān)鍵操作以生成相鄰的解決方案。

鄰域結(jié)構(gòu)1將操作分配給替代機器集合的機器生成解決方案,所選操作必須是關(guān)鍵操作。在這種鄰域結(jié)構(gòu)中,機器上的操作順序不會改變。步驟如下:首先隨機選擇關(guān)鍵操作;然后選擇備選機器集中的最短機器來分配以處理操作。

鄰域結(jié)構(gòu)2通過插入改變操作順序,任務(wù)分配不會更改。這些步驟可以描述如下:隨機獲得兩個數(shù)字,一個用于確定要插入的基因,另一個用于確定基因插入位置。如果關(guān)鍵塊只有一個或兩個操作則插入取消。如果關(guān)鍵塊包含兩個以上的操作,則在每個關(guān)鍵塊中第一個(最后一個)操作被插入到關(guān)鍵塊內(nèi)的內(nèi)部操作中,并且內(nèi)部操作被移動到關(guān)鍵塊的開始或結(jié)束。

鄰域結(jié)構(gòu)3通過交換操作順序。基于關(guān)鍵塊的任意兩個隨機選擇的操作順序都會被交換。交換關(guān)鍵路徑上的兩個操作順序規(guī)則如下:如果關(guān)鍵塊只有一個操作則不進行交換,如果關(guān)鍵塊有兩個操作直接交換順序,如果關(guān)鍵塊包含兩個以上的操作則隨機選擇兩個操作進行交換。

3.4 外部精英庫保留策略

對于柔性車間調(diào)度問題可能存在相同目標(biāo)值,但不同的機器加工甘特圖。為了讓調(diào)度人員有更多選項,對這些解決方案要進行保存。因此在本研究中,采用外部精英庫來保存解決方案,在外部庫中根據(jù)目標(biāo)值有序地保存解決方案。在更新過程中首先比較目標(biāo)值,如果值相等則比較機器字符串,如果兩個機器字符串不相同則保存解決方案。

3.5 GAVNS算法流程圖

步驟1:輸入調(diào)度任務(wù)參數(shù),使用文獻[17]GLR初始化方法;

步驟2:判斷當(dāng)前迭代次數(shù)N是否達到終止條件。是則輸出最優(yōu)解;否則繼續(xù)執(zhí)行步驟3;

步驟3:計算個體適應(yīng)度同時執(zhí)行輪盤賭算子選擇優(yōu)化操作,生成子代種群;

步驟4:根據(jù)自適應(yīng)變異率選取交叉變異個體;

步驟5:對全部個體執(zhí)行3種鄰域結(jié)構(gòu)搜索,對劣勢解集進行一定數(shù)量替換;

步驟6:選取當(dāng)代種群中的一定比例較優(yōu)個體儲存,保留精英個體;

步驟7:每代以隨機選擇的方式生成一定比例的新個體,對當(dāng)前種群最差的一部分個體進行替代,基本流程如圖3所示。

圖3 GAVNS算法流程圖

4 算例分析

實驗算例來自某汽車變速器零部件加工車間,簡化為6×6×8的柔性作業(yè)調(diào)度問題,表2、表3分別為工件工序的可選操作設(shè)備以及對應(yīng)的加工時間。

表2 操作設(shè)備表

表3 加工時間表

4.1 參數(shù)設(shè)置及生成預(yù)調(diào)度方案

算法具體參數(shù)設(shè)置如下:整體種群規(guī)模100;初始調(diào)度迭代次數(shù)200;重調(diào)度迭代次數(shù)50;優(yōu)解儲存庫容量20;GLR的比例分別為0.6,0.3,0.1;交叉概率pcmax=0.7;pcmin=0.5;變異概率pmmin=0.05;pmmax=0.1;通過遺傳變鄰域算法求得初始調(diào)度方案。

圖4可以得到各道工序?qū)?yīng)的機器設(shè)備,以及對應(yīng)的開始、結(jié)束時間。在未發(fā)生機器故障擾動的情況下,車間生產(chǎn)依照圖中調(diào)度方案執(zhí)行,圖5為初始調(diào)度方案適應(yīng)度值變化曲線。

圖4 預(yù)調(diào)度方案

圖5 加工總耗時尋優(yōu)曲線

采用熵值法確定3個子評價指標(biāo)的權(quán)重系數(shù)。使用熵值判斷子目標(biāo)的離散程度,依據(jù)離散程度判斷該子目標(biāo)對總目標(biāo)的影響程度。確定3個參數(shù)分別為μ1=0.21,μ2=0.32,μ3=0.47。針對變速器零部件加工車間故障頻率較高的設(shè)備7,設(shè)置故障參數(shù):故障發(fā)生時間(15,30 (h)),故障修復(fù)時間分別為(3,6 (h))。在4種故障狀態(tài)下分別進行10次仿真實驗,重調(diào)度評價指標(biāo)數(shù)值取平均值。

4.2 試驗結(jié)果分析

根據(jù)圖6中預(yù)調(diào)度方案,加工到30 h時機器7出現(xiàn)故障,工序P63中斷,故障修復(fù)時間為6 h。對受影響工序執(zhí)行重調(diào)度策略得到如圖6所示的最優(yōu)重調(diào)度方案以及圖7所示的重調(diào)度評價指標(biāo)收斂曲線。

圖6 最優(yōu)重調(diào)度方案

圖7 重調(diào)度評價指標(biāo)

重調(diào)度方案中部分工序操作機器發(fā)生變化,且故障機器恢復(fù)后部分工序仍在已修復(fù)的故障機器加工。由此可以判斷,該故障條件下最優(yōu)重調(diào)度方式為完全重調(diào)度。為了驗證該結(jié)果,對右移重調(diào)度和部分重調(diào)度得到對應(yīng)的圖8、圖9調(diào)度方案,圖8中右移重調(diào)度只針對部分受影響的工序進行右移,右移量不光取決于故障修復(fù)所需要的時間,而且還需要參考剩余機器和對應(yīng)工序間隙時間。

圖8 右移重調(diào)度方案

圖9 部分重調(diào)度方案

對圖8和圖9方案進行相應(yīng)的重調(diào)度評價指標(biāo)計算。右移重調(diào)度和部分重調(diào)度的評價指標(biāo)值分別為4.74和4.46,高于完全重調(diào)度對應(yīng)的評價指標(biāo)值4.37,驗證了選擇完全重調(diào)度方式的合理性。不同故障狀態(tài)下幾種重調(diào)度方式評價值如表4所示。

表4 仿真結(jié)果對比

從仿真結(jié)果中可以看出在不同生產(chǎn)時期、機器故障修復(fù)時間不同的情況下,最優(yōu)重調(diào)度方式也在發(fā)生改變,且同一種重調(diào)度方式不同時期效果差距很大。而在生產(chǎn)初期15 h、機器故障時間長3 h的情況下,右移重調(diào)度表現(xiàn)的更為優(yōu)越,但隨著機器故障修復(fù)時間的延長,同樣的故障時刻機器故障時間長6 h的情況下,完全重調(diào)度最優(yōu),評價指標(biāo)提升16.9%。在故障時間節(jié)點30 h,修復(fù)時間3 h時修復(fù)時右移重調(diào)度表現(xiàn)遠遠超過完全重調(diào)度;從表4可以看出完全重調(diào)度適合前期故障時間較長的情況;右移重調(diào)度適合后期故障時間較短的情況;部分重調(diào)度更適合處理特定時間點故障發(fā)生時間以及故障持續(xù)時間未知的情況。因此機器故障下加工車間依靠單一右移重調(diào)度方式無法滿足車間加工需求。只有結(jié)合多種重調(diào)度方式建立綜合的評價指標(biāo)在不同時期選擇最優(yōu)的重調(diào)度方式,才能降低任意時刻機器故障對生產(chǎn)車間帶來的負(fù)面影響。

5 結(jié)論

本文針對機器故障下的柔性作業(yè)車間動態(tài)調(diào)度問題提出了一種考慮機器故障概率的重調(diào)度方法。綜合使用3種重調(diào)度方式并建立了相應(yīng)約束條件下的數(shù)學(xué)模型,設(shè)計了重調(diào)度方案評價模型用于最優(yōu)重調(diào)度方式的選擇。利用機器故障概率明確了混合驅(qū)動中周期驅(qū)動的區(qū)間,設(shè)計了3種鄰域結(jié)構(gòu)對遺傳變鄰域算法進行改進,用于調(diào)度方案的求解,提高了整體搜索效率。

通過對不同故障情況下的組合仿真實驗,對3種重調(diào)度方式的評價指標(biāo)進行對比分析,得到如下結(jié)論:不同生產(chǎn)時期機器故障下不同重調(diào)度方式表現(xiàn)存在差異,同一種重調(diào)度方式在不同時期的表現(xiàn)差距也較大;右移重調(diào)度方式在機器故障時間短、加工末期具有優(yōu)越性,完全重調(diào)度在早期,故障修復(fù)時間較長表現(xiàn)更好。