朱傳軍 邱 文 張超勇 金亮亮

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

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

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

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

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

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

0 引言

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

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

1 動態(tài)FJSP

1.1 問題描述

本文主要考慮工件隨機到達和機器故障預維護兩類動態(tài)因素對生產(chǎn)車間的影響。

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

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

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

1.2 問題模型

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

機器分配約束條件，即每道工序需且僅需分配給一臺機器：

(6)

(7)

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

(8)

(9)

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

(10)

(11)

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

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

(12)

(13)

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

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

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

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

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

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

2.3 問題條件更新

3 重調(diào)度算法

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

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

3.1 種群初始化

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

3.2 編碼與解碼

3.2.1 染色體編碼

由于工件隨機到達、機器故障等動態(tài)事件的出現(xiàn)，本文將每個重調(diào)度時刻點的所有未加工工件和新到達工件歸入重調(diào)度工件集中。例如，當一個重調(diào)度觸發(fā)時，未加工工件集為{O12, O13, O23}，新工件集為{O31, O32, O33}，則重調(diào)度工件集為{O12, O13, O23, O31, O32, O33}。以重調(diào)度工件集{O12, O13, O23, O31, O32, O33}為例，對每道工序進行編號，得到工序染色體向量S，如表1所示。在進化過程中，當向量S=(3,4,1,5,2,6)時，則工序?qū)募庸ろ樞驗镺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)表示機器染色體，其中，rj(j=1，2，…，d)表示第j個工件選擇其可選機器集中第rj個機器安排加工。

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

(14)

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

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

3.2.2 染色體解碼

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

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

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

(15)

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

tsi=max(t1,tsmpi+pmpi)

(16)

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

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

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

3.3 Pareto排序

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

3.4 變異操作

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

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

3.5 交叉操作

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

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

3.6 局部搜索

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

機器部分的鄰域結(jié)構(gòu)Nr僅對機器染色體進行鄰域更新[13]。如圖5所示，鄰域結(jié)構(gòu)Nr1表示隨機選擇機器染色體上的基因1，則與該機器染色體對應的工序染色體中，基因1所對應工序的可選機器集中的機器碼2、3均為此基因位的鄰域，隨機選擇機器碼2代替機器碼1形成新的鄰域結(jié)構(gòu)Nr1[17]。鄰域結(jié)構(gòu)Nr2主要考慮機器負荷平衡，為平衡機器負荷，從待加工工序的所有可選機器集中，選擇加工時間最短的機器3替換機器1，得到鄰域結(jié)構(gòu)Nr2。該方法可以有效減小機器總負荷和關(guān)鍵機器負荷，有助于提高調(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是通過對工序染色體進行位置調(diào)整產(chǎn)生的。三種鄰域結(jié)構(gòu)分別通過對工序碼中隨機選擇的基因進行交換、反轉(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)化的方法進行求解后最終會得到一個非支配解集，而每次調(diào)度只能選出一個可行方案安排加工，因此，需從當前的非支配集合中選擇一個滿意的調(diào)度方案作為下一個調(diào)度區(qū)間的基準。在對非支配解進行決策選擇時，本文采用一種有效的TOPSIS方法，該方法依據(jù)眾多評價對象與理想化目標的接近程度對解進行排序，使最終解在一定程度上逼近于理想解。

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

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

4.1 算法性能分析

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

假設所有的機器具有相同的tMTBF和tMTTR。車間機器故障水平Ag=tMTTR/(tMTBF+tMTTR)，當Ag=0.05，tMTTR=5時，tMTBF=45，表示每臺機器故障間隔時間為45個時間單位，修復時間為5個時間單位。

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

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

表2 實驗數(shù)據(jù)Tab.2 Experimental data

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

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

表3 不同工件到達率下對應的makespanTab.3 Makespan under different arrival rate of jobs

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

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

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

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

表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，說明工件到達率和新工件數(shù)量對調(diào)度魯棒性和調(diào)度穩(wěn)定性存在顯著影響，驗證了本文前面的設想。

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

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

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

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

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

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

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

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

[1] 潘全科，朱劍英. 作業(yè)車間動態(tài)調(diào)度研究[J]. 南京航空航天大學學報,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] 張超勇，李新宇，王曉娟，等.基于滾動窗口的多目標動態(tài)調(diào)度優(yōu)化研究[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è)車間預反應式動態(tài)調(diào)度理論與方法研究[D].武漢：華中科技大學，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] 劉煒琪, 劉瓊，張超勇，等. 基于混合粒子群算法求解多目標混流裝配線排序[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] 張超勇，董星，王曉娟，等. 基于改進非支配遺傳算法的多目標柔性作業(yè)車間調(diào)度[J]. 機械工程學報，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年度“中國機械工業(yè)科學技術(shù)獎”申報、推薦工作的通知2017年度中國機械工業(yè)科學技術(shù)獎采用網(wǎng)絡推薦、申報項目的方式(網(wǎng)址：http://www.cmiao.com.cn)?，F(xiàn)將有關(guān)事項通知如下：

一、獎勵范圍1.機械行業(yè)發(fā)明類成果；2.機械行業(yè)技術(shù)進步類成果；3.機械行業(yè)軟科學、標準和檢測類成果及科技圖書。

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

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

四、公報格式文件要求申報單位請認真按照申報平臺公報格式文件要求填寫，并上傳申報平臺。內(nèi)容包括單位基本情況、項目簡介和能體現(xiàn)項目內(nèi)容的彩色圖片2張?！绊椖亢喗椤敝饕糜讷@獎項目的公開宣傳，不得涉及保密內(nèi)容，字數(shù)應控制在800～1000字以內(nèi)；圖片格式為JPG或者PDF，單張圖片大小不超過3 MB。

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

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

七、聯(lián)系方式

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

地 址：中國機械工業(yè)科學技術(shù)獎勵工作辦公室北京市西城區(qū)百萬莊大街22號(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

國家自然科學基金國際(地區(qū))合作與交流項目(51561125002)；國家自然科學基金資助項目(51275190, 51575211)；中央高?；究蒲袠I(yè)務費專項資金資助項目(HUST：2014TS038)

TP18

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

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