加工時間不確定的柔性作業(yè)車間魯棒調(diào)度方法

汪俊亮　張　潔　秦　威　銀　莉　陳定方

1.上海交通大學(xué)，上海，200240　　2.武漢理工大學(xué)，武漢，430063

加工時間不確定的柔性作業(yè)車間魯棒調(diào)度方法

汪俊亮1張潔1秦威1銀莉2陳定方2

1.上海交通大學(xué)，上海，2002402.武漢理工大學(xué)，武漢，430063

針對中小批量環(huán)境下加工時間不確定的柔性作業(yè)車間調(diào)度問題，采用冗余處理方法構(gòu)建了以最大完工時間為目標(biāo)的魯棒調(diào)度模型。為降低算法的搜索規(guī)模和提高算法的求解速度，提出了順序搜索機(jī)制，并設(shè)計兩階段遺傳算法，分階段獲取冗余狀態(tài)和最優(yōu)結(jié)果。采用某柔性生產(chǎn)線的數(shù)據(jù)進(jìn)行正交試驗(yàn)，優(yōu)化了算法關(guān)鍵參數(shù)，并構(gòu)建了柔性生產(chǎn)線仿真模型，對調(diào)度結(jié)果的魯棒性和優(yōu)化目標(biāo)性能進(jìn)行了分析。結(jié)果表明，該算法在目標(biāo)性能和魯棒性上都顯著優(yōu)于標(biāo)準(zhǔn)遺傳算法，能有效處理加工時間不確定的柔性作業(yè)車間調(diào)度問題。

加工時間擾動；柔性作業(yè)車間；魯棒性；順序搜索

0　引言

不確定因素作用下的柔性作業(yè)車間調(diào)度問題是在柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)的基礎(chǔ)上，考慮車間環(huán)境的隨機(jī)性和動態(tài)性，處理不確定因素對調(diào)度目標(biāo)影響的一類調(diào)度算法，是車間調(diào)度領(lǐng)域的一類關(guān)鍵問題。實(shí)際的生產(chǎn)環(huán)節(jié)中，由于生產(chǎn)環(huán)境具有動態(tài)性和隨機(jī)性，導(dǎo)致加工時間、工件到達(dá)時間和機(jī)床故障率等因素很難用一個確定的值來描述[1]，因此，建立在調(diào)度參數(shù)確定情況下的柔性作業(yè)車間調(diào)度方案已經(jīng)難以滿足生產(chǎn)的需求。與此同時，不確定因素擾動下的柔性作業(yè)車間調(diào)度問題受到越來越多研究者的關(guān)注，成為目前FJSP領(lǐng)域的研究熱點(diǎn)之一[2]。

對于不確定因素擾動下的作業(yè)車間調(diào)度方法主要分為動態(tài)重調(diào)度和靜態(tài)預(yù)調(diào)度兩類[3]。采用動態(tài)重調(diào)度方法會反復(fù)產(chǎn)生重調(diào)度方案[4]，對擾動因素進(jìn)行處理時，雖然方案具有較好的時效性，但是頻繁地修正生產(chǎn)計劃，對物料計劃、人員派遣會產(chǎn)生連鎖反應(yīng)，從而造成生產(chǎn)混亂。靜態(tài)預(yù)調(diào)度方法是提前考慮不確定因素對于調(diào)度結(jié)果的影響，提前對調(diào)度結(jié)果作出修正，但是如何對不確定因素的擾動進(jìn)行描述和預(yù)測，是預(yù)調(diào)度中的一大難題。

制造過程中不確定因素的處理方法主要有隨機(jī)數(shù)學(xué)方法、模糊數(shù)學(xué)方法、冗余處理方法等。Xia等[5]采用隨機(jī)數(shù)學(xué)方法處理加工時間不確定的單機(jī)調(diào)度問題，設(shè)計懲罰函數(shù)對超期和提前問題進(jìn)行處理。但是隨機(jī)數(shù)分布往往通過大量歷史數(shù)據(jù)的分析獲得，而大量生產(chǎn)數(shù)據(jù)的統(tǒng)計在中小批量的生產(chǎn)模式中難以實(shí)現(xiàn)。李平等[6]采用三角模糊數(shù)來處理加工時間不確定的Job Shop問題時，運(yùn)用隸屬度函數(shù)將連續(xù)的大數(shù)據(jù)量問題轉(zhuǎn)化為離散的小數(shù)據(jù)量問題來處理。但是其隸屬函數(shù)的構(gòu)造對歷史數(shù)據(jù)具有較強(qiáng)的依賴性，并不適用于產(chǎn)品種類多、變化快的中小批量生產(chǎn)模式。Zhang[7]采用冗余處理方法中的最小最大遺憾方法對批量生產(chǎn)環(huán)境下，需求不確定的調(diào)度問題進(jìn)行求解。但是該方法計算規(guī)模較大，在處理大型問題時難以實(shí)時求解。

國內(nèi)外學(xué)者大多對大批量作業(yè)車間的不確定因素處理進(jìn)行研究。魯建廈等[8]針對加工時間不確定的批量混合裝配車間調(diào)度問題進(jìn)行研究，運(yùn)用隨機(jī)數(shù)學(xué)理論對實(shí)際作業(yè)時間的波動情況進(jìn)行處理； Ponsich等[9]對加工時間不確定情況下的大批量生產(chǎn)調(diào)度問題，采用了遺傳算法進(jìn)行求解。Hufner等[10]針對大批量產(chǎn)品生產(chǎn)調(diào)度問題，采用了隨機(jī)整數(shù)規(guī)劃方法進(jìn)行處理。綜上可知，學(xué)者們對于大批量問題的研究較為充分，而對于多品種小批量生產(chǎn)模式下的研究較少。但是，多品種小批量的作業(yè)模式因?yàn)槠洚a(chǎn)品覆蓋廣、作業(yè)柔性高，被廣泛應(yīng)用于我國中小型制造業(yè)中，因此，針對多品種小批量環(huán)境下，不確定因素擾動的作業(yè)車間魯棒調(diào)度問題具有重要意義。

本文針對多品種小批量生產(chǎn)模式下，加工時間不確定的柔性作業(yè)車間調(diào)度問題進(jìn)行研究，采用基于冗余處理的方法處理加工時間不確定的波動問題，并建立了魯棒預(yù)調(diào)度模型。設(shè)計了兩階段遺傳算法，依次獲取了問題冗余解和最優(yōu)解，為縮小搜索規(guī)模，設(shè)計了順序搜索機(jī)制，簡化了搜索方式，使復(fù)雜環(huán)境下的魯棒調(diào)度算法具有了較大的應(yīng)用潛力。

1　問題描述與模型建立

多品種小批量環(huán)境中，加工時間不確定的柔性作業(yè)車間調(diào)度問題具有如下特點(diǎn)：加工柔性高，零件種類多樣多變、數(shù)量較少，工序加工時間的變化規(guī)律難以通過歷史數(shù)據(jù)的統(tǒng)計分析得到但其大致的區(qū)間可以通過預(yù)估確定。

對于三種常用的不確定因素處理方法(隨機(jī)數(shù)學(xué)方法、模糊數(shù)學(xué)方法、冗余處理方法)進(jìn)行分析和對比可知：隨機(jī)數(shù)學(xué)方法需要大量歷史數(shù)據(jù)來構(gòu)建分布函數(shù)，模糊數(shù)學(xué)方法需要?dú)v史數(shù)據(jù)來構(gòu)建隸屬度函數(shù)，這兩種方法對歷史數(shù)據(jù)依賴性大，不適用于柔性作業(yè)車間的生產(chǎn)模式，因此采用冗余處理方法建立數(shù)學(xué)模型。

加工時間不確定的冗余處理方法通過對加工時間進(jìn)行抽樣，取樣本中的目標(biāo)函數(shù)值和最優(yōu)情況偏離最大的情況，即最大冗余情況作為調(diào)度求解中不確定因素的擾動狀態(tài)，并在此狀態(tài)下，對調(diào)度問題進(jìn)行求解，其原理如圖1所示。冗余調(diào)度方法是在最劣的時間樣本下求取最優(yōu)調(diào)度方案，確保在各種加工時間場景下，最優(yōu)方案具有魯棒性和性能指標(biāo)的優(yōu)勢。

圖1　加工時間不確定的冗余處理方法

1.2基于冗余機(jī)制的魯棒預(yù)調(diào)度模型建立

以柔性作業(yè)車間為對象，采用冗余調(diào)度方法，以最大完工時間為目標(biāo)，構(gòu)建考慮加工時間不確定變化的魯棒調(diào)度模型：

為了進(jìn)一步證明本文提出的行為識別方法的可行性,本文還在MSRC-12數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),動態(tài)行為最終平均識別準(zhǔn)確率為78%。文獻(xiàn)[15]采用隨機(jī)森林算法進(jìn)行動作分類,同樣在MSRC-12數(shù)據(jù)集上進(jìn)行測試,平均識別準(zhǔn)確率為67.3%,對比可知本文方法識別準(zhǔn)確率更高。

(1)

i=1,2,…,n;j=1,2,…,m

約束函數(shù)：

Ci1≥Pi1

(2)

|Ci1j1k-Ci2j2k|≥(1-Qi1i2k)Pi2j2+xi1i2kPi1j1

(3)

i1,i2=1,2,…,n;j1,j2=1,2,…,m;k=1,2,…

Cij-Ci(j-1)≥Pij

(4)

S={P11P21…Pn1P12P22…

Pn2…P1mP2m…Pnm}

(5)

(6)

式(1)表示目標(biāo)函數(shù)為在最大冗余情況下最大完工時間達(dá)到最小時所對應(yīng)的調(diào)度方案，式中X為工序調(diào)度方案的集合，S為每一道工序加工時間的集合，Cij為第i個工件、第j個工序的完工時間；式(2)表示工件的起始加工約束，表示任何工件都要求在0時刻以后開始加工；式(3)表示同一時刻同一機(jī)器只能加工一個零件，Ci1j1k表示機(jī)器k上加工的零件i1的第j1道工序的完工時間，Pi1j1表示零件i1的第j1道工序的加工時間，Qi1i2k表示機(jī)器上工序的排列順序，其取值情況如下：

(7)

2　基于順序搜索機(jī)制的兩階段遺傳算法

2.1基于冗余調(diào)度模型的順序搜索機(jī)制

目前，常采用兩層次嵌套的方法求解基于冗余處理的魯棒調(diào)度[3]。對于n個工件m道工序p個機(jī)器的柔性制造系統(tǒng)調(diào)度問題而言，共需計算qkn×mpn×m次，其中k為加工時間樣本數(shù)量，q為一次方案求解需要的計算次數(shù)，該遍歷方法隨問題規(guī)模增長呈指數(shù)增長，難以適應(yīng)復(fù)雜問題的求解。

為提高魯棒調(diào)度算法的求解速度，根據(jù)下述引理[11]，采用順序搜索結(jié)構(gòu)搜索最優(yōu)解。

由引理1和引理2可知，當(dāng)f(x,s)取得可行解時，F(xiàn)JSP種群的最優(yōu)解x1，可以同時和加工時間進(jìn)化種群的最優(yōu)解s1、s2配套實(shí)現(xiàn)最優(yōu)，即兩個種群的搜索進(jìn)化可以互為依托，同步進(jìn)行?；诖?，本文采用基于順序搜索的方式，實(shí)現(xiàn)快速求解。2.2兩階段遺傳算法設(shè)計

基于順序搜索機(jī)制設(shè)計兩階段遺傳算法對問題進(jìn)行快速求解，其流程見圖2。在第一階段算法中，在FJSP種群空間中對加工時間種群進(jìn)行搜索獲取最大冗余狀態(tài)；在第二階段算法中，在加工時間種群中對FJSP種群進(jìn)行搜索優(yōu)化，獲取最優(yōu)調(diào)度結(jié)果。兩階段算法互為依托，反復(fù)搜索進(jìn)化，得到最優(yōu)解。

圖2　采用順序搜索的快速求解算法流程圖

對于采用順序搜索機(jī)制的算法，對其效率分析如下：假設(shè)染色體種群數(shù)均為N，每一次解碼需要計算p次，遺傳算法總共迭代計算M次，則總共需要計算機(jī)計算2MpN次。通過對比可知，采用順序搜索的求解方式在搜索速度上達(dá)到了乘數(shù)級別，相比傳統(tǒng)的嵌套求解方式在求解速度上具有巨大的優(yōu)勢。

3　案例分析

采用某公司柔性生產(chǎn)線實(shí)際案例對算法進(jìn)行正交試驗(yàn)，優(yōu)化算法關(guān)鍵參數(shù)。同時為分析算法輸出方案的魯棒性和目標(biāo)性能，將標(biāo)準(zhǔn)遺傳算法與本文的魯棒調(diào)度算法輸出結(jié)果進(jìn)行比較，并在eM-Plant環(huán)境下建立仿真調(diào)度模型，對算法輸出方案魯棒性進(jìn)行評價。

3.1參數(shù)優(yōu)化和求解

采用武漢某柔性生產(chǎn)線10個工件、3步工序、4臺機(jī)器的實(shí)際完全柔性作業(yè)案例作為源數(shù)據(jù)，采用正交試驗(yàn)法對遺傳算法中的POX交叉概率、雙點(diǎn)交叉概率、均勻交叉概率進(jìn)行優(yōu)化。對POX交叉概率的三個水平分別為A1=0.3、A2=0.5、A3=0.7，雙點(diǎn)交叉概率的三個水平分別為B1=0.4、B2=0.6、B3=0.8，均勻交叉概率的三個水平分別為C1=0.4、C2=0.6、C3=0.8三種情況下的算法運(yùn)行結(jié)果依次進(jìn)行正交測試，測試結(jié)果見表1。

表1　正交試驗(yàn)結(jié)果

為了直觀顯示測試結(jié)果，將數(shù)據(jù)經(jīng)過處理之后以圖的形式表示，如圖3所示。

圖3　算法參數(shù)正交試驗(yàn)結(jié)果

圖4　本文魯棒調(diào)度算法FJSP實(shí)例預(yù)調(diào)度方案

通過參數(shù)測試結(jié)果發(fā)現(xiàn)，POX交叉概率為0.5，雙點(diǎn)交叉概率為0.8，均勻交叉概率為0.8時，算法性能表現(xiàn)較好。在此基礎(chǔ)上，設(shè)置其他參數(shù)如下：重調(diào)度種群規(guī)模為20，變異概率都設(shè)置為0.005，循環(huán)次數(shù)設(shè)置為100，調(diào)度結(jié)果見圖4。程序在CPU:CORETMi7-2.0 GHz,RAM:4GB的環(huán)境下運(yùn)行。

采用標(biāo)準(zhǔn)遺傳算法和本文提出的魯棒算法進(jìn)行對比，采用相同的算法參數(shù)并在相同環(huán)境下對同一問題進(jìn)行計算，其輸出方案見圖5。

圖5　標(biāo)準(zhǔn)遺傳算法求解FJSP實(shí)例調(diào)度方案

3.2調(diào)度方案仿真與分析

在完成算法的求解之后，對方案的魯棒性進(jìn)行評價。常見的魯棒性評價方式有：隨機(jī)數(shù)學(xué)計算法、離散事件仿真法。Rahmani等[12]采用隨機(jī)數(shù)學(xué)原理模擬不確定因素發(fā)生，從而計算方案的魯棒性。但是其參數(shù)的數(shù)值根據(jù)經(jīng)驗(yàn)設(shè)定，在復(fù)雜因素影響下欠缺數(shù)據(jù)的真實(shí)性。因此，本文采用離散事件仿真的方法，評價方案的魯棒性。首先定義車間調(diào)度方案的魯棒性如下：

R(s)=r·E(M(s))+(1-r)·E(δ(s))

(8)

其中，M(s)是一個隨機(jī)變量表示不確定因素影響下實(shí)際的最大完工時間；δ(s)=|M(s)-Mo(s)|表示預(yù)期最大完工時間和實(shí)際最大完工時間之間的差值；r是權(quán)重函數(shù),其值在(0,1)之間。由于Mo(s)是確定的，M(s)和δ(s)的期望值等同于E(M(s))=E(δ(s))+Mo(s)。因此作業(yè)車間調(diào)度方案的魯棒性可以等同為

R(s)=r·E(Mo(s))+E(δ(s))

(9)

在計算R(s)的基礎(chǔ)上，對魯棒性進(jìn)行分析，采用R(s)和r·E(Mo(s))的接近程度反映調(diào)度方案的相對魯棒性，計算得其偏差為

(10)

采用R(s)與平均單機(jī)工序工時之和r∑(T/4)的偏差反映該方案實(shí)際性能與目標(biāo)性能的偏差：

(11)

在eM-Plant環(huán)境中建立仿真調(diào)度模型，對算法輸出方案進(jìn)行分析。歸納出工件的約束關(guān)系和加工時間數(shù)據(jù)(表2)，作為仿真數(shù)據(jù)的輸入。

表2　工序加工時間數(shù)據(jù)及機(jī)器分配方案　min

對仿真模型多次運(yùn)行，并將結(jié)果和未考慮加工時間不確定的柔性作業(yè)車間的調(diào)度方案進(jìn)行對比。其計算結(jié)果如表3所示(其中r=0.7)。

表3　調(diào)度方案魯棒性評價結(jié)果

分析可知，在加工時間不確定情況下，本文提出的算法產(chǎn)生的方案在相對魯棒性和實(shí)際性能上都有較好的表現(xiàn)，在對不確定性作出有效的規(guī)避的同時發(fā)揮了良好的調(diào)度性能。

4　結(jié)語

本文針對中小批量環(huán)境下加工時間不確定的柔性作業(yè)車間調(diào)度問題，結(jié)合冗余處理方法構(gòu)建魯棒調(diào)度模型，并提出順序搜索機(jī)制，降低搜索規(guī)模。對算法參數(shù)進(jìn)行優(yōu)化和修正，并進(jìn)行了仿真實(shí)驗(yàn)。該算法的主要特性有以下兩點(diǎn):①普適性。算法采用冗余處理方法構(gòu)建模型，對加工歷史數(shù)據(jù)依賴性低，算法稍作調(diào)整，便適用于其他的車間調(diào)度問題。②快速性。算法針對兩層嵌套結(jié)構(gòu)，創(chuàng)新采用順序搜索機(jī)制，有效減少了計算量，在乘數(shù)時間內(nèi)獲得不確定因素擾動下的調(diào)度方案。

綜合考慮本文的工作和領(lǐng)域的發(fā)展，進(jìn)一步的研究可以關(guān)注于以下兩點(diǎn)：①增加算法在復(fù)雜問題下的性能分析實(shí)驗(yàn)和同類算法之間的對比實(shí)驗(yàn)；②對多種不確定因素耦合作用下的車間調(diào)度問題進(jìn)行研究。

[1]Van S，Demeulemeester L，Herroelen W． A Classification of Predictive-reactive Project Scheduling Procedures[J]. Journal of Scheduling, 2007, 10(3): 195-207.

[2]陳庭貴，琚春華．多干擾的資源約束項(xiàng)目調(diào)度問題[J]．計算機(jī)集成制造系統(tǒng)，2012,18(11)：2409-2418.

Chen Tinggui，Ju Chunhua．Resource-constrained Project Scheduling Problem with Multi-factor Disruptions[J]．Computer Integrated Manufacturing System，2012,18(11)：2409-2418.

[3]Herroelen W，Leus R．Robust and Reactive Project Scheduling: a Review and Classification of Procedures[J]．International Journal of Production Research，2004，42(8)：1599-1620．

[4]Novas M, Henning P. Reactive Scheduling Framework Based on Domain Knowledge and Constraint Programming[J]. Computers & Chemical Engineering, 2010, 34(12): 2129-2148.

[5]Xia Y, Chen B, Yue J. Job Sequencing and Due Date Assignment in a Single Machine Shop with Uncertain Processing Times[J]. European Journal of Operational Research, 2008, 184(1): 63-75.

[6]李平，顧幸生．不確定條件下不同交貨期窗口的JobShop調(diào)度[J]．管理科學(xué)學(xué)報，2004,2：22-26.

Li Ping, Gu Xingsheng. Job Shop Scheduling with Uncertain Processing Time and Distinct Due Windows[J]. Journal of Management Sciences in China, 2004,7(2): 22-26.

[7]Zhang M. Two-stage Minimax Regret Robust Uncapacitated Lot-sizing Problems with Demand Uncertainty[J]. Operations Research Letters, 2011, 39(5): 342-345.

[8]魯建廈，施錦峰，李修琳，等．一類已知概率分布下的混合車間魯棒調(diào)度問題研究[J]．中國機(jī)械工程，2010,21(19)：2328-2333.

Lu Jianxia, Shi Jingfeng, Li Xiuling, et al. Study on Hybrid Shop Robust Scheduling Problem with Known Probability Distribution[J]. China Mechanical Engineering, 2010, 21(19): 2328-2333.

[9]Ponsich A, Bonfill A, Espua A, et al. Genetic Algorithms for the Scheduling of Multiproduct Batch Plants within Uncertain Environment[J]. Computer Aided Chemical Engineering, 2007, 24: 619-624.[10]Hufner M, Tometzki T, Engell S. Two-layer Planning and Scheduling of Batch Production Processes under Uncertainty[J]. Computer Aided Chemical Engineering, 2009, 27: 1197-1202.[11]Jensen T．Robust and Flexible Scheduling with Evolutionary Computation[D]．Arhus:University of Arhus，2001．

[12]Rahmani D, Heydari M. Robust and Stable Flow Shop Scheduling with Unexpected Arrivals of New Jobs and Uncertain Processing Times[J]. Journal of Manufacturing Systems, 2013.

(編輯王艷麗)

Robust Scheduling on Flexible Job Shop with Uncertain Processing Time

Wang Junliang1Zhang Jie1Qin Wei1Yin Li2Chen Dingfang2

1.Shanghai Jiao Tong University,Shanghai,200240 2.Wuhan University of Technology,Wuhan,430063

This paper investigated the flexible job-shop scheduling problem (FJSP) with uncertain processing time in a multi-type and low-volume environment. A minimax regret based robust scheduling model was built to minimize the makespan. A novel sequential search rule was put forward to reduce the calculation amount of the algorithm and a two stage genetic algorithm was designed to figure out the redundant and optimal solutions. Orthogonal test was designed to optimize significant parameters, and then, a simulation model was established to evaluate the robustness and objective performance of the algorithm. The results show the proposed algorithm has a better performance than genetic algorithm on flexible job-shop scheduling problem under uncertain and dynamic environment.

processing time disturbance; flexible job-shop; robustness;sequential search

2013-12-23

國家高技術(shù)研究發(fā)展計劃(863計劃)資助項(xiàng)目(2012AA040907)

TH166DOI：10.3969/j.issn.1004-132X.2015.05.010

汪俊亮，男，1991年生。上海交通大學(xué)機(jī)械與動力工程學(xué)院碩士研究生。主要研究方向?yàn)橹圃煜到y(tǒng)建模與優(yōu)化、虛擬制造。張潔(通信作者)，女，1963年生。上海交通大學(xué)機(jī)械與動力工程學(xué)院教授。秦威，男，1985年生。上海交通大學(xué)機(jī)械與動力工程學(xué)院博士。銀莉，女，1990年生。武漢理工大學(xué)能源與動力工程學(xué)院碩士研究生。陳定方，男，1946年生。武漢理工大學(xué)智能制造與控制研究所教授。