周爾民,馬 暢,劉 寧

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

0 引言

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

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

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

1 問(wèn)題描述

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

1.1 符號(hào)說(shuō)明

本文的變量及符號(hào)定義如表1所示。

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

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

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

(4)

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

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

2.1 機(jī)器故障概率

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

(5)

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

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

針對(duì)何時(shí)進(jìn)行重調(diào)度和如何進(jìn)行重調(diào)度,采用異常事件和基于機(jī)器故障頻率的周期混合驅(qū)動(dòng)策略,根據(jù)機(jī)器故障頻率設(shè)置合理的重調(diào)度周期區(qū)間,在保證加工車間調(diào)度穩(wěn)定性的同時(shí),也能夠快速響應(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)度針對(duì)故障機(jī)器上未開始加工工序,重新安排其加工機(jī)器,沒(méi)發(fā)生故障的機(jī)器上加工工序保持不變,加工時(shí)間和加工順序均有變化,機(jī)器故障恢復(fù)時(shí)間未知時(shí)大多采用此調(diào)度方式。

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

機(jī)器故障下重調(diào)度方案評(píng)價(jià)模型表達(dá)式為:

(6)

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

2.5 重調(diào)度流程

在整個(gè)調(diào)度過(guò)程中,原調(diào)度方案以最小化最大完成時(shí)間為目標(biāo),機(jī)器發(fā)生故障時(shí),采用事件和基于故障概率的周期混合驅(qū)動(dòng)策略,綜合使用右移重調(diào)度、完全重調(diào)度、部分重調(diào)度3種組合方式。在重調(diào)度方案優(yōu)選階段中,考慮到方案變動(dòng)必然帶來(lái)額外成本增加以及加工生產(chǎn)穩(wěn)定性降低的問(wèn)題,因而引入最大完工時(shí)間差值、工序結(jié)束時(shí)間差值和機(jī)器偏離成本作為評(píng)價(jià)指標(biāo),評(píng)價(jià)指標(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è)計(jì)了自適應(yīng)交叉算子和變異算子,以及基于VNS關(guān)鍵路徑的3種鄰域結(jié)構(gòu)。

3.1 染色體編碼與解碼

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

3.2 交叉、變異操作

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

3.2.1 交叉算子

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

(7)

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

3.2.2 變異算子

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

(8)

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

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

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

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

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

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

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

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

3.4 外部精英庫(kù)保留策略

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

3.5 GAVNS算法流程圖

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

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

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

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

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

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

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

圖3 GAVNS算法流程圖

4 算例分析

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

表2 操作設(shè)備表

表3 加工時(shí)間表

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

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

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

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

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

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

4.2 試驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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