多目標柔性作業車間穩健性動態調度研究

朱傳軍 邱 文 張超勇 金亮亮

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

多目標柔性作業車間穩健性動態調度研究

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

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

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

柔性作業車間動態調度問題；多目標；動態調度；穩健性；差分進化

0 引言

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

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

1 動態FJSP

1.1 問題描述

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

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

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

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

1.2 問題模型

為較好地適應車間動態環境，文中將完工時間T定義為調度區間內所有工件的最大完工時間：

(1)

調度方案的魯棒性指標R表示調度方案對動態環境的免疫程度，用重調度產生的新調度方案與初始調度方案中參與調度但還未執行的所有工件的完工時間差值的絕對值之和表示：

(2)

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

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

(3)

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

(4)

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

(5)

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

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

(6)

(7)

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

(8)

(9)

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

(10)

(11)

各工序在機器上的先后約束關系如下：

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

(12)

(13)

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

2 動態重調度方法

2.1 動態重調度流程

文中所提動態重調度流程包括預調度方案、發生器、問題條件更新和重調度算法[9]，具體流程如圖1所示。

圖1 柔性作業車間重調度方法流程圖Fig.1 Flow chart of flexible job shop scheduling methods

2.2 發生器

在調度的初始時刻，所有工件和機器的相關參數已預先確定。在每個重調度時刻點，調度系統將重新產生新的預調度方案并執行該方案直至下一個重調度時刻點，保證車間生產的連續性。發生器的主要作用是在生產過程中不斷產生動態擾動直到調度結束。與工件相關的參數和與機器相關的參數是發生器的兩個主要參數，其參數的產生過程及有關符號說明如下：tJAEL為工件到達時間間隔；tMTBF為每臺機器的預維護發生時間均值；tMTTR為每臺機器預維護的時間均值；tFEL為每臺機器預維護發生的時間點，當該機器進行預防性維護時，tFEL歸零；tLife為每臺機器上的累積負荷，當機器進行預防性維護時，tLife歸零；trepair為每臺機器的預維護時間。

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

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

2.3 問題條件更新

3 重調度算法

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

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

3.1 種群初始化

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

3.2 編碼與解碼

3.2.1 染色體編碼

由于工件隨機到達、機器故障等動態事件的出現，本文將每個重調度時刻點的所有未加工工件和新到達工件歸入重調度工件集中。例如，當一個重調度觸發時，未加工工件集為{O12, O13, O23}，新工件集為{O31, O32, O33}，則重調度工件集為{O12, O13, O23, O31, O32, O33}。以重調度工件集{O12, O13, O23, O31, O32, O33}為例，對每道工序進行編號，得到工序染色體向量S，如表1所示。在進化過程中，當向量S=(3,4,1,5,2,6)時，則工序對應的加工順序為O2,3?O3,1?O1,2?O3,2?O1,3?O3,3，即首先安排工序O2,3加工，然后安排工序O3,1，后面依次類推。

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

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

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

(14)

其中，round(·)為取整函數，xj為實數序列X1中的第j個實數。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(如果它們存在)。在重調度時刻t1，某些工件正在被加工，由于加工的延續性，正在加工這些工件的機器只能等該工件加工結束后才能參與重調度，因此在解碼過程中應對其分開進行考慮。

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

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

(15)

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

tsi=max(t1,tsmpi+pmpi)

(16)

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

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

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

3.3 Pareto排序

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

3.4 變異操作

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

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

3.5 交叉操作

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

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

3.6 局部搜索

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

機器部分的鄰域結構Nr僅對機器染色體進行鄰域更新[13]。如圖5所示，鄰域結構Nr1表示隨機選擇機器染色體上的基因1，則與該機器染色體對應的工序染色體中，基因1所對應工序的可選機器集中的機器碼2、3均為此基因位的鄰域，隨機選擇機器碼2代替機器碼1形成新的鄰域結構Nr1[17]。鄰域結構Nr2主要考慮機器負荷平衡，為平衡機器負荷，從待加工工序的所有可選機器集中，選擇加工時間最短的機器3替換機器1，得到鄰域結構Nr2。該方法可以有效減小機器總負荷和關鍵機器負荷，有助于提高調度穩定性[5]。

圖5 鄰域結構Nr1、Nr2示意圖Fig.5 Schematic diagram of neighborhood structure Nr1 and Nr2

工件部分的鄰域結構Ns1、Ns2、Ns3是通過對工序染色體進行位置調整產生的。三種鄰域結構分別通過對工序碼中隨機選擇的基因進行交換、反轉和插入操作獲得[9]，圖6為這三種鄰域結構的示意圖。

圖6 鄰域結構Ns1、Ns2、Ns3示意圖Fig.6 Schematic diagram of neighborhood structure Ns1，Ns2 and Ns3

3.7 Pareto解決策

在調度區間中，采用基于Pareto優化的方法進行求解后最終會得到一個非支配解集，而每次調度只能選出一個可行方案安排加工，因此，需從當前的非支配集合中選擇一個滿意的調度方案作為下一個調度區間的基準。在對非支配解進行決策選擇時，本文采用一種有效的TOPSIS方法，該方法依據眾多評價對象與理想化目標的接近程度對解進行排序，使最終解在一定程度上逼近于理想解。

4 實例結果與分析

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

4.1 算法性能分析

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

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

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

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

表2 實驗數據Tab.2 Experimental data

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

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

表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中數據可知，4種調度規則所需的CPU時間遠遠小于GA算法、MODE_NL算法和MODE_L算法所需CPU時間。同時，表4中數據顯示，調度規則雖大大節省了CPU時間，但其最大完工時間較大，在一定程度上降低了調度的魯棒性和穩定性，尤其在工件密集到達(γ=1/2，1)和大規模工件到達(Jn=100，200)情況下。MODE_NL算法沒有考慮局部搜索，所需CPU時間與GA算法接近，均小于MODE_L算法。對比4種調度規則和其他調度算法可知，MODE_L算法的CPU時間較長，但該算法在提高調度魯棒性和穩定性上具有明顯優勢。綜合考慮可知，在實際制造系統中，MODE_L的CPU時間是可接受的。

4.2 工件到達率和新工件數量對調度性能的影響

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

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

表6 調度穩定性雙因素方差分析Tab.6 Two-factor variance analysis of scheduling stability

表5、表6表明，各因素分析的P-value均小于0.05，說明工件到達率和新工件數量對調度魯棒性和調度穩定性存在顯著影響，驗證了本文前面的設想。

圖7、圖8所示為不同工件到達率對調度穩定性和調度魯棒性的影響。

圖7 不同工件到達率下的調度穩定性結果Fig.7 Result of schedule stability under different arrival rates of jobs

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

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

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

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

(b)穩定性目標函數值-新工件數量曲線圖9 不同新工件數下的調度穩定性與魯棒性結果Fig.9 Result of schedule stability and robustness under different number of new jobs

5 結語

提出了柔性作業車間動態調度問題的框架，為了保證車間生產效率與生產穩定，建立了基于調度穩健性的動態調度模型，結合完全重調度策略和混合周期調度與關鍵事件驅動重調度方法，提出了差分變領域算法和動態事件發生器來對多目標柔性作業車間動態調度問題進行求解。實例驗證了本文提出的模型與求解方法的有效性與優越性。

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

[1] 潘全科，朱劍英. 作業車間動態調度研究[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] 張超勇，李新宇，王曉娟，等.基于滾動窗口的多目標動態調度優化研究[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] 張利平. 作業車間預反應式動態調度理論與方法研究[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]. 計算機集成制造系統, 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]. 機械工程學報，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年度“中國機械工業科學技術獎”申報、推薦工作的通知2017年度中國機械工業科學技術獎采用網絡推薦、申報項目的方式(網址：http://www.cmiao.com.cn)。現將有關事項通知如下：

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

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

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

四、公報格式文件要求申報單位請認真按照申報平臺公報格式文件要求填寫，并上傳申報平臺。內容包括單位基本情況、項目簡介和能體現項目內容的彩色圖片2張。“項目簡介”主要用于獲獎項目的公開宣傳，不得涉及保密內容，字數應控制在800～1000字以內；圖片格式為JPG或者PDF，單張圖片大小不超過3 MB。

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

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

七、聯系方式

申報網址：http://www.cmiao.com.cn

地 址：中國機械工業科學技術獎勵工作辦公室北京市西城區百萬莊大街22號(100037)

聯系人：席 敏 牛 芳

電 話：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

國家自然科學基金國際(地區)合作與交流項目(51561125002)；國家自然科學基金資助項目(51275190, 51575211)；中央高校基本科研業務費專項資金資助項目(HUST：2014TS038)

TP18

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

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