多目標(biāo)柔性作業(yè)車間穩(wěn)健性動(dòng)態(tài)調(diào)度研究

朱傳軍 邱 文 張超勇 金亮亮

1.湖北工業(yè)大學(xué)機(jī)械工程學(xué)院，武漢，4300682.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

多目標(biāo)柔性作業(yè)車間穩(wěn)健性動(dòng)態(tài)調(diào)度研究

朱傳軍1邱 文1張超勇2金亮亮2

1.湖北工業(yè)大學(xué)機(jī)械工程學(xué)院，武漢，4300682.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

研究了以調(diào)度穩(wěn)定性和魯棒性為優(yōu)化目標(biāo)的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題。建立了多目標(biāo)柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題模型；針對(duì)動(dòng)態(tài)事件特點(diǎn)，采用工件到達(dá)發(fā)生器和機(jī)器故障預(yù)維護(hù)發(fā)生器模擬動(dòng)態(tài)事件，提出了基于周期與事件驅(qū)動(dòng)的混合重調(diào)度策略，該策略在每個(gè)重調(diào)度點(diǎn)對(duì)工件進(jìn)行完全重調(diào)度或右移重調(diào)度；為克服傳統(tǒng)差分算法早熟的缺點(diǎn)，設(shè)計(jì)了一種改進(jìn)的多目標(biāo)差分進(jìn)化算法求解該調(diào)度問題；實(shí)例驗(yàn)證了提出策略和算法的有效性。

柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題；多目標(biāo)；動(dòng)態(tài)調(diào)度；穩(wěn)健性；差分進(jìn)化

0 引言

針對(duì)動(dòng)態(tài)作業(yè)車間調(diào)度問題，潘全科等[1]研究了作業(yè)車間動(dòng)態(tài)調(diào)度問題中待加工工件的選取原則及再調(diào)度方法，但沒有考慮機(jī)器柔性；ADIBI等[2]針對(duì)工件隨機(jī)到達(dá)和機(jī)器故障的動(dòng)態(tài)調(diào)度問題，提出了基于周期和事件驅(qū)動(dòng)的混合重調(diào)度策略，但是只考慮了完工時(shí)間和拖期這兩個(gè)時(shí)間指標(biāo)，沒考慮調(diào)度方案本身的穩(wěn)健性；HE等[3]針對(duì)機(jī)器故障這一類動(dòng)態(tài)調(diào)度問題，提出插入空閑時(shí)間、工件右移調(diào)度和變路徑調(diào)度等方法來提高調(diào)度方案的穩(wěn)定性和魯棒性，但忽略了其他動(dòng)態(tài)因素的影響；FANG等[4]研究了具有工件隨機(jī)到達(dá)、機(jī)器故障、機(jī)器維修和變交貨期等多變量的動(dòng)態(tài)環(huán)境，采用一種滾動(dòng)窗口機(jī)制求解該動(dòng)態(tài)問題，但沒考慮多目標(biāo)的情況；LI等[5]研究了機(jī)器預(yù)維護(hù)情況下的柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)，在加工過程中動(dòng)態(tài)加入機(jī)器維護(hù)，但只考慮了時(shí)間性能；FATTAHI等[6]針對(duì)工件隨機(jī)到達(dá)情況下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題，提出完整的動(dòng)態(tài)調(diào)度問題模型，并采用改進(jìn)遺傳算法求解，但沒有考慮機(jī)器故障的情況；XIONG等[7]研究了隨機(jī)機(jī)器故障情況下的FJSP，采用機(jī)器故障水平和機(jī)器平均維修時(shí)間描述機(jī)器故障，但沒有考慮其他動(dòng)態(tài)因素；AL-HINAI等[8]采用兩階段混合遺傳算法求解機(jī)器隨機(jī)故障情況下的FJSP，沒有考慮工件隨機(jī)到達(dá)的情況。實(shí)際生產(chǎn)中，既要考慮工件隨機(jī)到達(dá)，又要考慮機(jī)器故障等動(dòng)態(tài)因素，目前國內(nèi)對(duì)同時(shí)考慮兩種動(dòng)態(tài)因素的柔性作業(yè)車間調(diào)度的研究較少。

因此，筆者結(jié)合實(shí)際生產(chǎn)環(huán)境，深入研究工件隨機(jī)到達(dá)和機(jī)器故障預(yù)維護(hù)兩類動(dòng)態(tài)事件觸發(fā)的柔性作業(yè)車間動(dòng)態(tài)調(diào)度。以調(diào)度方案穩(wěn)定性和魯棒性為優(yōu)化目標(biāo)，建立動(dòng)態(tài)FJSP數(shù)學(xué)模型，采用工件隨機(jī)到達(dá)發(fā)生器和機(jī)器故障預(yù)維護(hù)發(fā)生器來模擬車間生產(chǎn)過程中發(fā)生的動(dòng)態(tài)事件，并提出基于周期與事件驅(qū)動(dòng)的混合重調(diào)度策略，將各工件劃分到對(duì)應(yīng)的調(diào)度區(qū)間。在各調(diào)度區(qū)間，運(yùn)用完全重調(diào)度和右移重調(diào)度策略，并采用改進(jìn)多目標(biāo)差分進(jìn)化算法對(duì)其進(jìn)行求解。最后驗(yàn)證了提出方法的有效性。

1 動(dòng)態(tài)FJSP

1.1 問題描述

本文主要考慮工件隨機(jī)到達(dá)和機(jī)器故障預(yù)維護(hù)兩類動(dòng)態(tài)因素對(duì)生產(chǎn)車間的影響。

(1)隨著時(shí)間的推移，不斷有一定數(shù)量的新工件動(dòng)態(tài)到達(dá)調(diào)度系統(tǒng)，針對(duì)工件的隨機(jī)到達(dá)，大多數(shù)研究均認(rèn)為工件的動(dòng)態(tài)到達(dá)近似服從泊松分布，且任意兩個(gè)相鄰到達(dá)工件的到達(dá)時(shí)間間隔近似服從指數(shù)分布[9-10]。

(2)機(jī)器故障預(yù)維護(hù)。假設(shè)每臺(tái)機(jī)器故障預(yù)維護(hù)發(fā)生的時(shí)間間隔近似服從指數(shù)分布[9]。故障維護(hù)間隔時(shí)間均值(mean time between failure,MTBF)和故障維護(hù)時(shí)間均值(mean time to repair,MTTR)是與機(jī)器故障預(yù)維護(hù)相關(guān)的兩個(gè)參數(shù)。

在周期與事件驅(qū)動(dòng)的混合重調(diào)度中，一旦機(jī)器的累計(jì)加工時(shí)間超過一定閾值或到達(dá)固定重調(diào)度周期就會(huì)觸發(fā)一次重調(diào)度。

1.2 問題模型

為較好地適應(yīng)車間動(dòng)態(tài)環(huán)境，文中將完工時(shí)間T定義為調(diào)度區(qū)間內(nèi)所有工件的最大完工時(shí)間：

(1)

調(diào)度方案的魯棒性指標(biāo)R表示調(diào)度方案對(duì)動(dòng)態(tài)環(huán)境的免疫程度，用重調(diào)度產(chǎn)生的新調(diào)度方案與初始調(diào)度方案中參與調(diào)度但還未執(zhí)行的所有工件的完工時(shí)間差值的絕對(duì)值之和表示：

(2)

式中，cpi、cri分別為工件i在預(yù)調(diào)度方案和重調(diào)度方案中的完工時(shí)間；n′為新調(diào)度方案與初始調(diào)度方案中參與調(diào)度但還未被加工的工件總數(shù)。

由于工件預(yù)調(diào)度在某一機(jī)器上加工時(shí)，動(dòng)態(tài)事件的發(fā)生將導(dǎo)致該工件的開始加工時(shí)間發(fā)生變化，進(jìn)而引起生產(chǎn)資源重新分配。初始調(diào)度中各機(jī)器上分配的工序數(shù)在重調(diào)度時(shí)也可能存在差異，因此本文的調(diào)度穩(wěn)定性主要由工序偏離度do和機(jī)器偏離度dm兩個(gè)基本穩(wěn)定性指標(biāo)表示[11]。工序偏離度定義為重調(diào)度方案與初始調(diào)度方案中在重調(diào)度時(shí)刻所有未加工完成的工序的開始時(shí)間總偏差：

(3)

文獻(xiàn)[8]在求解多目標(biāo)動(dòng)態(tài)FJSP時(shí)，為簡化計(jì)算復(fù)雜度，取pj=1，本文同樣取pj=1。柔性作業(yè)車間動(dòng)態(tài)調(diào)度中，每道工序可在多臺(tái)機(jī)器加工，發(fā)生重調(diào)度時(shí)，分到每臺(tái)機(jī)器上的工序可能會(huì)增加或減少，而工序的增加或減少將導(dǎo)致機(jī)器夾具或道具等發(fā)生變化，因此，在考慮穩(wěn)定性時(shí)同樣要考慮到機(jī)器的偏離度dm[11]。機(jī)器偏離度表示重調(diào)度方案與初始調(diào)度方案中所有機(jī)器上加工工序數(shù)的總偏差：

(4)

其中，pk為初始調(diào)度中工序在重調(diào)度時(shí)刻發(fā)生變化引起的機(jī)器懲罰系數(shù)，為簡化計(jì)算復(fù)雜度，同樣可參考文獻(xiàn)[11]取pk=1；yk為機(jī)器k上從初始調(diào)度增加和減少的總工序數(shù)。

(5)

實(shí)際生產(chǎn)中，工序間存在一定的加工約束條件，下面分析具體的約束條件。

機(jī)器分配約束條件，即每道工序需且僅需分配給一臺(tái)機(jī)器：

(6)

(7)

每道工序一旦開始，加工就不能中斷，除非機(jī)器故障，可用下式表示：

(8)

(9)

工序加工順序約束條件，即各工件的前任工序完工后才能安排其后續(xù)工序加工：

(10)

(11)

各工序在機(jī)器上的先后約束關(guān)系如下：

Ch,l,k-ph,l,k+M(1-Yijhlk)≥Ci,j,k

(12)

(13)

其中，M為足夠大的正實(shí)數(shù)；Yijhlk為0-1變量，Yijhlk=1表示工序Oi,j先于工序Oh,l在機(jī)器k上加工，反之亦然。

2 動(dòng)態(tài)重調(diào)度方法

2.1 動(dòng)態(tài)重調(diào)度流程

文中所提動(dòng)態(tài)重調(diào)度流程包括預(yù)調(diào)度方案、發(fā)生器、問題條件更新和重調(diào)度算法[9]，具體流程如圖1所示。

圖1 柔性作業(yè)車間重調(diào)度方法流程圖Fig.1 Flow chart of flexible job shop scheduling methods

2.2 發(fā)生器

在調(diào)度的初始時(shí)刻，所有工件和機(jī)器的相關(guān)參數(shù)已預(yù)先確定。在每個(gè)重調(diào)度時(shí)刻點(diǎn)，調(diào)度系統(tǒng)將重新產(chǎn)生新的預(yù)調(diào)度方案并執(zhí)行該方案直至下一個(gè)重調(diào)度時(shí)刻點(diǎn)，保證車間生產(chǎn)的連續(xù)性。發(fā)生器的主要作用是在生產(chǎn)過程中不斷產(chǎn)生動(dòng)態(tài)擾動(dòng)直到調(diào)度結(jié)束。與工件相關(guān)的參數(shù)和與機(jī)器相關(guān)的參數(shù)是發(fā)生器的兩個(gè)主要參數(shù)，其參數(shù)的產(chǎn)生過程及有關(guān)符號(hào)說明如下：tJAEL為工件到達(dá)時(shí)間間隔；tMTBF為每臺(tái)機(jī)器的預(yù)維護(hù)發(fā)生時(shí)間均值；tMTTR為每臺(tái)機(jī)器預(yù)維護(hù)的時(shí)間均值；tFEL為每臺(tái)機(jī)器預(yù)維護(hù)發(fā)生的時(shí)間點(diǎn)，當(dāng)該機(jī)器進(jìn)行預(yù)防性維護(hù)時(shí)，tFEL歸零；tLife為每臺(tái)機(jī)器上的累積負(fù)荷，當(dāng)機(jī)器進(jìn)行預(yù)防性維護(hù)時(shí)，tLife歸零；trepair為每臺(tái)機(jī)器的預(yù)維護(hù)時(shí)間。

很多研究顯示，工件的隨機(jī)到達(dá)近似服從指數(shù)分布，本文工件到達(dá)發(fā)生器包括以下三個(gè)步驟：初始化工件到達(dá)時(shí)間間隔；計(jì)算新工件的到達(dá)時(shí)間；判斷是否觸發(fā)重調(diào)度，具體參見文獻(xiàn)[12]。

機(jī)器預(yù)維護(hù)是根據(jù)機(jī)器故障的統(tǒng)計(jì)規(guī)律制定出長遠(yuǎn)的維修計(jì)劃，相比于機(jī)器故障后維護(hù)，從經(jīng)濟(jì)成本和實(shí)用性來看，預(yù)防性維護(hù)更加經(jīng)濟(jì)、有效，且可在一定程度上提高系統(tǒng)對(duì)動(dòng)態(tài)擾動(dòng)的免疫程度。機(jī)器預(yù)維護(hù)發(fā)生器的實(shí)施具體參見文獻(xiàn)[12]。

2.3 問題條件更新

3 重調(diào)度算法

差分進(jìn)化(differential evolution,DE)算法是一種基于實(shí)數(shù)編碼和差分思想的隨機(jī)并行優(yōu)化算法。本文設(shè)計(jì)的帶局部搜索的多目標(biāo)差分算法(multi-objective differential evolution algorithm with local search，MODE_L)流程如圖2所示。MODE_L算法與基本多目標(biāo)差分(multi-objective differential evolution algorithm with no local search，MODE_NL)算法的關(guān)鍵區(qū)別是：①M(fèi)ODE_L算法提出了新的種群初始化策略；②在交叉和變異之后增加變鄰域局部搜索操作，針對(duì)機(jī)器部分和工序部分分別設(shè)計(jì)了鄰域結(jié)構(gòu)；③在算法的最后加入了Pareto決策。

圖2 MODE_L算法流程Fig.2 Flow chart of MODE_L algorithm

3.1 種群初始化

本文采用文獻(xiàn)[13]提出的混合初始化策略，在每個(gè)重調(diào)度時(shí)刻，為保證初始種群的多樣性和解的有效性，針對(duì)機(jī)器部分和工序部分分別設(shè)計(jì)初始化方法。

3.2 編碼與解碼

3.2.1 染色體編碼

由于工件隨機(jī)到達(dá)、機(jī)器故障等動(dòng)態(tài)事件的出現(xiàn)，本文將每個(gè)重調(diào)度時(shí)刻點(diǎn)的所有未加工工件和新到達(dá)工件歸入重調(diào)度工件集中。例如，當(dāng)一個(gè)重調(diào)度觸發(fā)時(shí)，未加工工件集為{O12, O13, O23}，新工件集為{O31, O32, O33}，則重調(diào)度工件集為{O12, O13, O23, O31, O32, O33}。以重調(diào)度工件集{O12, O13, O23, O31, O32, O33}為例，對(duì)每道工序進(jìn)行編號(hào)，得到工序染色體向量S，如表1所示。在進(jìn)化過程中，當(dāng)向量S=(3,4,1,5,2,6)時(shí)，則工序?qū)?yīng)的加工順序?yàn)镺2,3?O3,1?O1,2?O3,2?O1,3?O3,3，即首先安排工序O2,3加工，然后安排工序O3,1，后面依次類推。

表1 工序染色體編碼表Tab.1 Process of chromosome coding

用整數(shù)序列R=(r1，r2，…，rd)表示機(jī)器染色體，其中，rj(j=1，2，…，d)表示第j個(gè)工件選擇其可選機(jī)器集中第rj個(gè)機(jī)器安排加工。

表1所示問題的一個(gè)機(jī)器分配序列如圖3所示。由圖3可知，工序O3,2選擇的是第2個(gè)可加工機(jī)器，即機(jī)器M3。設(shè)整數(shù)序列L=(l1，l2，…，ld)，其中，lj表示工序j的可選機(jī)器數(shù)，按照下式進(jìn)行轉(zhuǎn)換，確定每道工序的加工機(jī)器：

(14)

其中，round(·)為取整函數(shù)，xj為實(shí)數(shù)序列X1中的第j個(gè)實(shí)數(shù)。lj=1表示工序j只有一個(gè)機(jī)器可供加工，此時(shí)不論xj取何值，rj始終等于1。

圖3 機(jī)器染色體示意圖Fig.3 Schematic diagram of machine chromosome

3.2.2 染色體解碼

設(shè)工序Oi的開工時(shí)間、加工時(shí)間分別為tsi、pi，則工序Oi的完工時(shí)間為tsi+pi；設(shè)工序Oi的工件緊前工序、機(jī)器緊前工序分別為Oji和Omi(如果它們存在)。在重調(diào)度時(shí)刻t1，某些工件正在被加工，由于加工的延續(xù)性，正在加工這些工件的機(jī)器只能等該工件加工結(jié)束后才能參與重調(diào)度，因此在解碼過程中應(yīng)對(duì)其分開進(jìn)行考慮。

對(duì)于正在加工工件，該工序在機(jī)器上的后續(xù)工序的開始加工時(shí)間取該工序的工件前任工序Oji和機(jī)器前任工序Omi的完工時(shí)間中的較大值：

tsi=max(tsjpi+pjpi,tsmpi+pmpi)

(15)

對(duì)于未加工工件，其第一道工序的開始加工時(shí)間取重調(diào)度時(shí)刻t1和該工序的機(jī)器前任工序Omi的完工時(shí)間中的較大值：

tsi=max(t1,tsmpi+pmpi)

(16)

對(duì)于正在加工工件和未加工工件的非第一道工序，其開始加工時(shí)間仍依據(jù)式(8)、式(9)計(jì)算。

為保證解碼產(chǎn)生的調(diào)度為主動(dòng)調(diào)度，本文采用插入式貪婪解碼算法，將每道工序插入到所分配機(jī)器上的最佳可加工時(shí)刻加工。

需要說明的是，基于實(shí)數(shù)的編碼中，按實(shí)數(shù)序列降序排列后得到的工序染色體S中可能存在同一工件的相鄰工序間加工順序相互沖突的情況，如S=(5,1,3,6,4,2)，序號(hào)5、6、4分別表示工件3的第2道、第3道和第1道工序，此時(shí)無法解碼出可行調(diào)度解。當(dāng)出現(xiàn)這種情況時(shí)，應(yīng)對(duì)S做相應(yīng)的調(diào)整，保證各工件相鄰工序間的加工順序約束條件得到滿足[14]。

3.3 Pareto排序

本文采用一種快速排序方法構(gòu)造非支配集，該方法在進(jìn)化個(gè)體之間定義一種新的關(guān)系：?X,Y∈P，如果X支配Y或者X和Y不相關(guān)，則X?dY?？焖倥判蚍椒看握覇蝹€(gè)個(gè)體X作為比較對(duì)象，按照支配關(guān)系“?d”進(jìn)行判斷，接著進(jìn)行逐輪排序。

3.4 變異操作

在XUE等[15]提出的多目標(biāo)差分算法的變異操作中，參與變異的2個(gè)個(gè)體是在種群中隨機(jī)選擇的2個(gè)互不相同的個(gè)體，該方法在查找全局非支配解時(shí)具有隨機(jī)性。本文依據(jù)變異個(gè)體的穩(wěn)定性和魯棒性，選擇穩(wěn)定性指標(biāo)較高的個(gè)體參與變異操作。

測(cè)試發(fā)現(xiàn)，依據(jù)兩種評(píng)價(jià)指標(biāo)選擇的個(gè)體進(jìn)行變異操作時(shí)不僅可以在一定程度上提高解的質(zhì)量，還能提高算法找到全局非支配解的速度。

3.5 交叉操作

式中，vj,i,G表示變異操作后產(chǎn)生的新個(gè)體，xj,i,G表示原始種群中的個(gè)體。

圖4 交叉操作示意圖Fig.4 Schematic diagram of crossover operation

3.6 局部搜索

局部搜索可以有效地提高算法解的質(zhì)量和算法的收斂速度。本文針對(duì)FJSP特性提出兩類鄰域結(jié)構(gòu)：機(jī)器部分的鄰域結(jié)構(gòu)Nr和工件部分的鄰域結(jié)構(gòu)Ns。

機(jī)器部分的鄰域結(jié)構(gòu)Nr僅對(duì)機(jī)器染色體進(jìn)行鄰域更新[13]。如圖5所示，鄰域結(jié)構(gòu)Nr1表示隨機(jī)選擇機(jī)器染色體上的基因1，則與該機(jī)器染色體對(duì)應(yīng)的工序染色體中，基因1所對(duì)應(yīng)工序的可選機(jī)器集中的機(jī)器碼2、3均為此基因位的鄰域，隨機(jī)選擇機(jī)器碼2代替機(jī)器碼1形成新的鄰域結(jié)構(gòu)Nr1[17]。鄰域結(jié)構(gòu)Nr2主要考慮機(jī)器負(fù)荷平衡，為平衡機(jī)器負(fù)荷，從待加工工序的所有可選機(jī)器集中，選擇加工時(shí)間最短的機(jī)器3替換機(jī)器1，得到鄰域結(jié)構(gòu)Nr2。該方法可以有效減小機(jī)器總負(fù)荷和關(guān)鍵機(jī)器負(fù)荷，有助于提高調(diào)度穩(wěn)定性[5]。

圖5 鄰域結(jié)構(gòu)Nr1、Nr2示意圖Fig.5 Schematic diagram of neighborhood structure Nr1 and Nr2

工件部分的鄰域結(jié)構(gòu)Ns1、Ns2、Ns3是通過對(duì)工序染色體進(jìn)行位置調(diào)整產(chǎn)生的。三種鄰域結(jié)構(gòu)分別通過對(duì)工序碼中隨機(jī)選擇的基因進(jìn)行交換、反轉(zhuǎn)和插入操作獲得[9]，圖6為這三種鄰域結(jié)構(gòu)的示意圖。

圖6 鄰域結(jié)構(gòu)Ns1、Ns2、Ns3示意圖Fig.6 Schematic diagram of neighborhood structure Ns1，Ns2 and Ns3

3.7 Pareto解決策

在調(diào)度區(qū)間中，采用基于Pareto優(yōu)化的方法進(jìn)行求解后最終會(huì)得到一個(gè)非支配解集，而每次調(diào)度只能選出一個(gè)可行方案安排加工，因此，需從當(dāng)前的非支配集合中選擇一個(gè)滿意的調(diào)度方案作為下一個(gè)調(diào)度區(qū)間的基準(zhǔn)。在對(duì)非支配解進(jìn)行決策選擇時(shí)，本文采用一種有效的TOPSIS方法，該方法依據(jù)眾多評(píng)價(jià)對(duì)象與理想化目標(biāo)的接近程度對(duì)解進(jìn)行排序，使最終解在一定程度上逼近于理想解。

4 實(shí)例結(jié)果與分析

本文算法用C++語言編程，運(yùn)行環(huán)境為P4 CPU，主頻3.2G Hz，內(nèi)存3 GB。實(shí)例測(cè)試分為兩部分，第一部分為了評(píng)估和比較提出算法的性能，對(duì)相同問題采用不同調(diào)度算法和調(diào)度規(guī)則進(jìn)行測(cè)試；第二部分通過模擬實(shí)際生產(chǎn)車間數(shù)據(jù)的實(shí)例進(jìn)行測(cè)試，得出工件到達(dá)率和工件到達(dá)數(shù)量對(duì)調(diào)度性能的影響。經(jīng)測(cè)試，本文多目標(biāo)差分進(jìn)化算法運(yùn)行的參數(shù)設(shè)置如下：種群規(guī)模N=100，交叉概率Pc=0.3，縮放因子F=0.1，貪婪算子λ=0.5，局部搜索概率Pl=0.5，局部搜索迭代次數(shù)g=20，最大進(jìn)化代數(shù)G=80。由于每個(gè)重調(diào)度時(shí)刻參與重調(diào)度的工件數(shù)可能不一樣(新工件到達(dá)，舊工件加工完成)，為了測(cè)試方便，各個(gè)調(diào)度區(qū)間的種群規(guī)模和進(jìn)化代數(shù)均取相同值。

4.1 算法性能分析

為了驗(yàn)證本文提出的重調(diào)度方法和策略在求解動(dòng)態(tài)FJSP上的可行性與有效性，使用文獻(xiàn)中通用的一些調(diào)度規(guī)則[18]和方法求解本文的動(dòng)態(tài)調(diào)度問題，并將求解結(jié)果進(jìn)行對(duì)比分析。本文對(duì)比的重調(diào)度方法包括最短加工時(shí)間(SPT)規(guī)則、最長加工時(shí)間(LPT)規(guī)則、人工蜂群(ABC)算法[5]、先進(jìn)先出(FIFO)規(guī)則、混合粒子群(HPSO)算法[19]、后進(jìn)先出(LIFO)規(guī)則、多目標(biāo)進(jìn)化算法(MOEA)[20]、MODE_NL算法。MODE_NL與MODE_L的不同之處在于沒有考慮局部搜索。

假設(shè)所有的機(jī)器具有相同的tMTBF和tMTTR。車間機(jī)器故障水平Ag=tMTTR/(tMTBF+tMTTR)，當(dāng)Ag=0.05，tMTTR=5時(shí)，tMTBF=45，表示每臺(tái)機(jī)器故障間隔時(shí)間為45個(gè)時(shí)間單位，修復(fù)時(shí)間為5個(gè)時(shí)間單位。

定義參數(shù)γ為每單位時(shí)間到達(dá)的新工件數(shù)量(工件到達(dá)率)，且是服從泊松分布的隨機(jī)變量。γ=1/4表示每隔4個(gè)單位時(shí)間就有一個(gè)新工件到達(dá)。

本文研究了4種不同的工件到達(dá)率和6種不同的新工件數(shù)量Jn對(duì)調(diào)度性能的影響情況。為了保證實(shí)驗(yàn)對(duì)比的公正性，本文的調(diào)度周期和機(jī)器故障水平等均不變，加工機(jī)器數(shù)量根據(jù)工件規(guī)模的不同分別取不同值。機(jī)器平均故障時(shí)間 tMTTR和平均修復(fù)時(shí)間tMTBF均服從指數(shù)分布，機(jī)器和工件的到達(dá)時(shí)間間隔均服從指數(shù)分布，新工件加工時(shí)間服從均勻分布。調(diào)度的性能指標(biāo)為makespan、完工時(shí)間偏差、開始時(shí)間偏差和機(jī)器偏差。表2給出了具體的實(shí)驗(yàn)數(shù)據(jù)。

表2 實(shí)驗(yàn)數(shù)據(jù)Tab.2 Experimental data

表3給出了不同工件到達(dá)率下不同方法的makespan，其中新工件數(shù)量取20、40、60、80、100、200，γ取1/8、1/4、1/2、1，S、M、L分別表示新工件為小規(guī)模、中規(guī)模、大規(guī)模，不同的新工件規(guī)模對(duì)應(yīng)不同的加工機(jī)器數(shù)。表3中的粗體數(shù)據(jù)表示求解同類問題時(shí)得到的最優(yōu)解。分析表3數(shù)據(jù)可知，調(diào)度算法比兩種調(diào)度規(guī)則產(chǎn)生的解較好。在所有調(diào)度算法中，MODE_NL算法解的質(zhì)量最差，MODE_L算法解最優(yōu)，VNS和MOEA算法次之。此外，VNS算法在工件稀疏到達(dá)(γ=1/8，1/4)時(shí)的求解性能與MODE_L算法比較接近，優(yōu)于MOEA算法；工件密集到達(dá)(γ=1/2，1)時(shí)，VNS算法的求解結(jié)果明顯差于MODE_L算法，但與MOEA算法接近。此外，隨著新工件數(shù)量的增加，4種調(diào)度規(guī)則的makespan迅速增大，GA算法得到的最大完工時(shí)間隨著新工件數(shù)量增加有所增長，但其增長速度較為緩慢，說明結(jié)果魯棒性較好。將MOEA算法與MODE_L算法進(jìn)行對(duì)比，發(fā)現(xiàn)MODE_L算法所得結(jié)果與MOEA算法所得結(jié)果相近。以上分析可以說明MODE_L算法能有效求解動(dòng)態(tài)FJSP。

在調(diào)度問題求解過程中，算法的運(yùn)行時(shí)間直接影響著動(dòng)態(tài)調(diào)度性能的優(yōu)劣。表4列出了所有方法求解同一動(dòng)態(tài)調(diào)度問題所需的CPU時(shí)間(取每個(gè)調(diào)度周期的平均值)。

表3 不同工件到達(dá)率下對(duì)應(yīng)的makespanTab.3 Makespan under different arrival rate of jobs

表4 不同工件到達(dá)率下不同算法的CPU時(shí)間Tab.4 CPU time of different algorithms under different jobs arrival rates s

分析表4中數(shù)據(jù)可知，4種調(diào)度規(guī)則所需的CPU時(shí)間遠(yuǎn)遠(yuǎn)小于GA算法、MODE_NL算法和MODE_L算法所需CPU時(shí)間。同時(shí)，表4中數(shù)據(jù)顯示，調(diào)度規(guī)則雖大大節(jié)省了CPU時(shí)間，但其最大完工時(shí)間較大，在一定程度上降低了調(diào)度的魯棒性和穩(wěn)定性，尤其在工件密集到達(dá)(γ=1/2，1)和大規(guī)模工件到達(dá)(Jn=100，200)情況下。MODE_NL算法沒有考慮局部搜索，所需CPU時(shí)間與GA算法接近，均小于MODE_L算法。對(duì)比4種調(diào)度規(guī)則和其他調(diào)度算法可知，MODE_L算法的CPU時(shí)間較長，但該算法在提高調(diào)度魯棒性和穩(wěn)定性上具有明顯優(yōu)勢(shì)。綜合考慮可知，在實(shí)際制造系統(tǒng)中，MODE_L的CPU時(shí)間是可接受的。

4.2 工件到達(dá)率和新工件數(shù)量對(duì)調(diào)度性能的影響

為分析工件到達(dá)率和新工件數(shù)量對(duì)調(diào)度性能的影響，參考文獻(xiàn)[13]，首先采用方差分析(analysis of variance，ANOVA)方法判斷以上2個(gè)因素是否對(duì)調(diào)度性能產(chǎn)生顯著影響。ANOVA用于統(tǒng)計(jì)顯著性實(shí)驗(yàn)，研究諸多控制變量中的哪些變量是對(duì)觀測(cè)變量有顯著影響的變量，一般情況下，P-value小于0.05表示影響是顯著的。表5、表6所示為統(tǒng)計(jì)顯著性分析結(jié)果，其中，因素A表示工件到達(dá)率，B表示新工件數(shù)量，AB表示二者之間存在相互影響，SS表示方差，MS表示均方差，F(xiàn)表示顯著性差異的水平，P-value表示檢驗(yàn)水平。

表5 調(diào)度魯棒性的雙因素方差分析Tab.5 Two-factor variance analysis of scheduling robustness

表6 調(diào)度穩(wěn)定性雙因素方差分析Tab.6 Two-factor variance analysis of scheduling stability

表5、表6表明，各因素分析的P-value均小于0.05，說明工件到達(dá)率和新工件數(shù)量對(duì)調(diào)度魯棒性和調(diào)度穩(wěn)定性存在顯著影響，驗(yàn)證了本文前面的設(shè)想。

圖7、圖8所示為不同工件到達(dá)率對(duì)調(diào)度穩(wěn)定性和調(diào)度魯棒性的影響。

圖7 不同工件到達(dá)率下的調(diào)度穩(wěn)定性結(jié)果Fig.7 Result of schedule stability under different arrival rates of jobs

圖8 不同工件到達(dá)率下的調(diào)度魯棒性結(jié)果Fig.8 Result of schedule robustness under different arrival rates of jobs

穩(wěn)定性目標(biāo)為各個(gè)調(diào)度區(qū)間中參與重調(diào)度工件的開始加工時(shí)間偏差和機(jī)器偏差的累積和，隨著工件到達(dá)率γ的增大，單位時(shí)間內(nèi)參與重調(diào)度的工件增加，開始加工時(shí)間偏差累積和增大，機(jī)器偏差的累積和也增大，從而使得調(diào)度穩(wěn)定性值隨著增大，經(jīng)過簡單計(jì)算得出，調(diào)度穩(wěn)定性增幅在2%～15%之間，說明增幅不是很明顯。由圖8可知，γ<1/4時(shí)，工件較少，此時(shí)新工件導(dǎo)致的擾動(dòng)對(duì)調(diào)度的影響較小，完工時(shí)間變動(dòng)值呈遞減趨勢(shì)，調(diào)度方案魯棒程度增大；γ>1/4時(shí)，工件較多，完工時(shí)間變動(dòng)量成遞增趨勢(shì)，調(diào)度方案魯棒性減小。

不同的工件到達(dá)率下，新工件數(shù)量與調(diào)度性能之間的關(guān)系如圖9所示。調(diào)度穩(wěn)定性和調(diào)度魯棒性曲線均隨著新工件數(shù)量的增加近似呈直線增長。對(duì)于調(diào)度穩(wěn)定性，當(dāng)新工件數(shù)量從20增加到40時(shí)，調(diào)度穩(wěn)定性以3%的增幅增長，增長十分緩慢；當(dāng)新工件數(shù)量從40增加到100時(shí)，曲線斜率變化比較明顯，其增大率近似為新工件數(shù)量Jn=40時(shí)的26%；新工件數(shù)量從100增加到200時(shí)，由于工件密集到達(dá)，分配到各機(jī)器上加工的工件增加，機(jī)器負(fù)荷增大，調(diào)度穩(wěn)定性和魯棒性降低，曲線斜率增大。以上分析說明新工件數(shù)量的增大對(duì)調(diào)度魯棒性和穩(wěn)定性有較大影響。

(a)魯棒性目標(biāo)函數(shù)值-新工件數(shù)量曲線

(b)穩(wěn)定性目標(biāo)函數(shù)值-新工件數(shù)量曲線圖9 不同新工件數(shù)下的調(diào)度穩(wěn)定性與魯棒性結(jié)果Fig.9 Result of schedule stability and robustness under different number of new jobs

5 結(jié)語

提出了柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題的框架，為了保證車間生產(chǎn)效率與生產(chǎn)穩(wěn)定，建立了基于調(diào)度穩(wěn)健性的動(dòng)態(tài)調(diào)度模型，結(jié)合完全重調(diào)度策略和混合周期調(diào)度與關(guān)鍵事件驅(qū)動(dòng)重調(diào)度方法，提出了差分變領(lǐng)域算法和動(dòng)態(tài)事件發(fā)生器來對(duì)多目標(biāo)柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題進(jìn)行求解。實(shí)例驗(yàn)證了本文提出的模型與求解方法的有效性與優(yōu)越性。

值得注意的是，當(dāng)工件密集到達(dá)時(shí)，較小的調(diào)度周期可以適當(dāng)提高調(diào)度穩(wěn)定性；當(dāng)工件稀疏到達(dá)時(shí)，較長的調(diào)度周期在一定程度上能增強(qiáng)調(diào)度魯棒性。因此在整個(gè)調(diào)度過程中采用相同的調(diào)度周期勢(shì)必會(huì)影響調(diào)度性能的優(yōu)劣，以后的工作是進(jìn)一步研究不同調(diào)度周期對(duì)調(diào)度魯棒性和調(diào)度穩(wěn)定性的影響。

[1] 潘全科，朱劍英. 作業(yè)車間動(dòng)態(tài)調(diào)度研究[J]. 南京航空航天大學(xué)學(xué)報(bào),2005，37(2):262-268. PAN Quanke, ZHU Jianying. Rolling Time Horizon Job-Shop Scheduling Strategy in Dynamic Environment[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2005, 37(2): 262-268.

[2] ADIBI M A, ZANDIEH M, AMIRI M. Multi-objective Scheduling of Dynamic Job Shop Using Variable Neighborhood Search[J]. Expert Systems with Applications, 2010, 37(1):282-287.

[3] HE W, SUN D H. Scheduling Flexible Job Shop Problem Subject to Machine Breakdown with Route Changing and Right-shift Strategies[J]. Int. J. Adv. Manuf. Technol., 2013, 66 (1):501-514.

[4] FANG J, XI Y. A Rolling Horizon Job Shop Rescheduling Strategy in the Dynamic Environment[J]. Int. J. Adv. Manuf. Technol., 1997, 13(3): 227-232.

[5] LI J Q, PAN Q K, FATIH TASGETIREN M. A Discrete Artificial Bee Colony Algorithm for Multi-objective Flexible Job Shop Scheduling Problems with Maintenance Activities[J]. Applied Mathematical Modelling, 2014, 38: 1111-1132.

[6] FATTAHI P, FALLAHI A. Dynamic Scheduling in Flexible Job Shop Systems by Considering Simultaneously Efficiency and Stability[J] .CIRP Journal of Manufacturing Science and Technology, 2010, 2(2): 114-123.

[7] XIONG J, XING L N, CHEN Y W. Robust Scheduling for Multi-objective Flexible Job-shop Problems with Random Machine Breakdowns[J]. Int. J. Production Economics, 2013, 141: 112-126.

[8] AL-HINAI N, ELMEKKAWY T Y. Robust and Stable Flexible Job Shop Scheduling with Random Machine Breakdowns Using a Hybrid Genetic Algorithm[J]. Int. J. Production Economics, 2011, 132: 279-291.

[9] ZHANG L P, GAO L, LI X Y. A Hybrid Genetic Algorithm and Tabu Search for a Multi-objective Dynamic Job Shop Scheduling Problem[J].International Journal of Production Research,2013,51(12): 3516-3531.

[10] CHURCH L K, UZSOY R. Analysis of Periodic and Event-driven Rescheduling Policies in Dynamic Shops[J]. International Journal of Computer Integrated Manufacturing, 1992, 5(3): 153-163.

[11] 張超勇，李新宇，王曉娟，等.基于滾動(dòng)窗口的多目標(biāo)動(dòng)態(tài)調(diào)度優(yōu)化研究[J].中國機(jī)械工程，2009, 20(18): 2190-2197. ZHANG Chaoyong, LI Xinyu, WANG Xiaojuan, et al. Multi-objective Dynamic Scheduling Optimization Strategy Based on Rolling-horizon Procedure[J]. China Mechanical Engineering, 2009, 20(18): 2190-2197.

[12] 張利平. 作業(yè)車間預(yù)反應(yīng)式動(dòng)態(tài)調(diào)度理論與方法研究[D].武漢：華中科技大學(xué)，2013. ZHANG Liping. Research on Theories and Methods for Dynamic Job Shop Scheduling Based on Predictive-reactive Scheduling[D].Wuhan：Huazhong University of Science and Technology，2013.

[13] LI J Q, PAN Q K,SUGANTHAN P N, et al. A Hybrid Tabu Search Algorithm with an Efficient Neighborhood Structure for the Flexible Job Shop Scheduling Problem[J]. Int. J. Adv. Manuf. Technol., 2011, 52: 683-697.

[14] KARSITI M N, CRUZ J B, MULLIGAN J H. Simulation Studies of Mutilevel Dynamic Job Shop Scheduling Using Heuristic Dispatching Rules[J]. Journal of Manufacturing Systems, 1992,11(5):346-358.

[15] XUE F, SANDERSON A C, GRAVES R J. Pareto-based Multi-objective Differential Evolution[C]//Proceedings of the Congress on Evolutionary Computation. Washington D C, 2003: 862-869.

[16] YUAN Y, XU H. Flexible Job Shop Scheduling Using Hybrid Differential Algorithms[J]. Journal of Intelligent Manufacturing, 2007, 18(3):331-342.

[17] LI J Q, PAN Q K, LIANG Y C. An Effective Hybrid Tabu Search Algorithm for Multi-objective Flexible Job Shop Scheduling Problems[J]. Comput. Int. Eng., 2010, 59: 647-662.

[18] 劉煒琪, 劉瓊，張超勇，等. 基于混合粒子群算法求解多目標(biāo)混流裝配線排序[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2011, 17(12): 2590-2598. LIU Weiqi, LIU Qiong, ZHANG Chaoyong, et al.Hybrid Particle Swarm Optimization for Multy-objective Sequencing Problem in Mixed Model Assembly Lines[J]. Computer Intergraded Manufacturing Systems, 2011, 17(12): 2590-2598.

[19] ZHANG G H, SHAO X Y, LI P G, et al. An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-objective Flexible Job-shop Scheduling Problem[J]. Computers & Industrial Engineering, 2009, 56: 1309-1318.

[20] 張超勇，董星，王曉娟，等. 基于改進(jìn)非支配遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J]. 機(jī)械工程學(xué)報(bào)，2010, 46(11):156-164. ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-II for the Multi-objective Flexible Job Shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2010, 46(11): 156-164.

(編輯 張 洋)

2017年度“中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)”申報(bào)、推薦工作的通知2017年度中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)采用網(wǎng)絡(luò)推薦、申報(bào)項(xiàng)目的方式(網(wǎng)址：http://www.cmiao.com.cn)?，F(xiàn)將有關(guān)事項(xiàng)通知如下：

一、獎(jiǎng)勵(lì)范圍1.機(jī)械行業(yè)發(fā)明類成果；2.機(jī)械行業(yè)技術(shù)進(jìn)步類成果；3.機(jī)械行業(yè)軟科學(xué)、標(biāo)準(zhǔn)和檢測(cè)類成果及科技圖書。

二、推薦、申報(bào)辦法和要求各中國機(jī)械工業(yè)專業(yè)協(xié)會(huì)、各省(自治區(qū)、直轄市)機(jī)械工業(yè)協(xié)會(huì)(聯(lián)合會(huì))、中國機(jī)械工程學(xué)會(huì)專業(yè)分會(huì)和各省(自治區(qū)、直轄市)機(jī)械工程學(xué)會(huì)等為各行業(yè)、領(lǐng)域和地區(qū)的推薦單位。中國機(jī)械工業(yè)聯(lián)合會(huì)會(huì)員單位、機(jī)械工業(yè)領(lǐng)域科研院所、勘察設(shè)計(jì)院、相關(guān)大專院校、出版單位可直接申報(bào)(僅限本單位的申報(bào)項(xiàng)目或作為第一完成單位申報(bào)的項(xiàng)目)。除“直接申報(bào)單位”外，原則上其他單位均需經(jīng)過推薦單位推薦。

三、推薦材料《中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)推薦書》是中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)勵(lì)評(píng)審的主要依據(jù)，推薦書包括主件部分(第一至第十一項(xiàng))、附件部分(第十二項(xiàng))二部分內(nèi)容。

四、公報(bào)格式文件要求申報(bào)單位請(qǐng)認(rèn)真按照申報(bào)平臺(tái)公報(bào)格式文件要求填寫，并上傳申報(bào)平臺(tái)。內(nèi)容包括單位基本情況、項(xiàng)目簡介和能體現(xiàn)項(xiàng)目內(nèi)容的彩色圖片2張。“項(xiàng)目簡介”主要用于獲獎(jiǎng)項(xiàng)目的公開宣傳，不得涉及保密內(nèi)容，字?jǐn)?shù)應(yīng)控制在800～1000字以內(nèi)；圖片格式為JPG或者PDF，單張圖片大小不超過3 MB。

五、申報(bào)的其他注意事項(xiàng)1.涉及國防、國家安全領(lǐng)域的保密項(xiàng)目和汽車類項(xiàng)目不屬于中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)評(píng)審范圍；2.申報(bào)項(xiàng)目必須是整體技術(shù)應(yīng)用一年以上(2015年12月31日前)；3.2016年度推薦申報(bào)未授獎(jiǎng)的項(xiàng)目不再受理；4.推薦申報(bào)項(xiàng)目一經(jīng)受理不得撤銷。

六、推薦時(shí)間推薦截止時(shí)間為二○一七年三月三十日，逾期網(wǎng)站項(xiàng)目申報(bào)平臺(tái)關(guān)閉不再受理；紙質(zhì)材料請(qǐng)于四月五日前報(bào)送或快遞至中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)勵(lì)工作辦公室，逾期將不再受理。

七、聯(lián)系方式

申報(bào)網(wǎng)址：http://www.cmiao.com.cn

地 址：中國機(jī)械工業(yè)科學(xué)技術(shù)獎(jiǎng)勵(lì)工作辦公室北京市西城區(qū)百萬莊大街22號(hào)(100037)

聯(lián)系人：席 敏 牛 芳

電 話：010-68351688 010-68326820

傳 真：010-68351688

電子郵箱：chinajixiekjj@163.com

Multi-objective Flexible Job Shop Dynamic Scheduling Strategy Aiming at Scheduling Stability and Robustness

ZHU Chuanjun1QIU Wen1ZHANG Chaoyong2JIN Liangliang2

1.School of Mechanical Engineering，Hubei University of Technology，Wuhan，430068 2.State Key Laboratory of Digital Manufacturing Equipment and Technology，Huazhong University of Science and Technology，Wuhan，430074

A dynamic FJSP aiming at scheduling stability and robustness was studied. Firstly, an optimization mathematical model was proposed based on scheduling stability and robustness. Secondly, by analyzing characteristics of dynamic FJSP, a job arrival generator and a predictive maintenance generator of machine breakdown were presented. In each rescheduling points, periodic and event driven rescheduling strategies were employed, and a complete rescheduling strategy combined with right-shift rescheduling strategy was proposed. In order to preserve the good characteristics of paternal generations, an improved differential evolution algorithm was designed to solve the dynamic FJSP. The validity of the proposed strategies and algorithm was verified by instances.

flexible job-shop scheduling problem(FJSP); multi-objective; dynamic schedule; robustness; differential evolution algorithm

2016-03-18

國家自然科學(xué)基金國際(地區(qū))合作與交流項(xiàng)目(51561125002)；國家自然科學(xué)基金資助項(xiàng)目(51275190, 51575211)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(HUST：2014TS038)

TP18

10.3969/j.issn.1004-132X.2017.02.009

朱傳軍，男，1971年生。湖北工業(yè)大學(xué)機(jī)械工程學(xué)院副教授。主要研究方向?yàn)橹圃煨畔?、智能調(diào)度算法、決策分析等。E-mail:zcj2579@126.com。邱 文(通信作者)，女，1989年生。湖北工業(yè)大學(xué)機(jī)械工程學(xué)院碩士研究生。張超勇，男，1972年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院副教授。金亮亮，男，1986年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院博士研究生。