范華麗，熊禾根，錢國潔，蔣國璋，李公法

（武漢科技大學 機械自動化學院，武漢 430081）

0 引言

調(diào)度問題自被提出以來，一直受到各個學科和領域的廣泛關注。調(diào)度問題有多種類型，其中Job Shop調(diào)度問題[1]（即單件車間作業(yè)計劃調(diào)度問題）是一類與實際生產(chǎn)調(diào)度密切相關的調(diào)度問題，其研究具有重要的理論意義與工程實用價值，因此它也是目前研究最為廣泛的車間調(diào)度問題[2]。經(jīng)典的Job Shop調(diào)度問題多是靜態(tài)調(diào)度問題，然而在實際車間生產(chǎn)中，工件多是動態(tài)到達的，且與工件相關的特征都是隨時間變化的，這類問題即所謂的動態(tài)Job Shop調(diào)度問題。對于工件動態(tài)到達的動態(tài)Job Shop調(diào)度問題，仿真調(diào)度為主要研究方法之一。由于工件動態(tài)到達的動態(tài)Job Shop 調(diào)度問題通常是對應于面向訂單（MTO-make to order）的制造系統(tǒng)，因此，交貨期的設置對于這類問題的研究來說非常重要。

現(xiàn)有的交貨期設置方法有多種，包括考慮工件特征信息（如總加工工時、總工序數(shù)等）的靜態(tài)規(guī)則和綜合考慮工件信息與車間狀態(tài)信息（包括工件到達時系統(tǒng)中已有的工件數(shù)量、工件到達時在它的加工路徑上的工件數(shù)等）的動態(tài)規(guī)則[3]。靜態(tài)規(guī)則有總工時規(guī)則TWK（Total Work Content）、等裕量規(guī)則CON（Constant allowance for all jobs）、等松弛規(guī)則SLK（Equal slack for all jobs）、工序數(shù)量規(guī)則NOP（Number of operations）等；動態(tài)規(guī)則有系統(tǒng)工件數(shù)量規(guī)則JIS（Job in system）、隊列工件數(shù)量規(guī)則JIQ（Job in queue）、隊列總工時規(guī)則WIQ（Work in queue）等。這些規(guī)則中，以TWK規(guī)則被認為是交貨期設置的最好方法[4]，也是所有的交貨期設置方法中使用最為廣泛的方法之一。記工件Jj的投放時間為rj，工件的總工時為Pj（含裝設時間），根據(jù)TWK規(guī)則，工件的交貨期dj設置為：

式中乘子k即交貨期寬裕度系數(shù)，其取值大小決定了交貨期的松緊程度。

文獻中常見的關于確定交貨期寬裕度系數(shù)k的方法主要有以下三種：1) 各種仿真參數(shù)配置下均取一組相同的寬裕度系數(shù)。最常見的取值為在（2,3,4,5,6,7,8）中取兩至四個值[5～11]，如文獻[5]中，k的取值為2、4、6和8；文獻[7]中，k的取值為4、6和8；文獻[8]中，k的取值為4和8等。對于非交貨期相關性能指標（如最大流程時間、平均流程時間等）的調(diào)度問題研究來說，k的大小對性能的影響不大[11]，因此這一方法是簡單且可行的。2）不同車間利用率下取幾組不同的寬裕度系數(shù)。由于交貨期松緊程度與車間利用率密切相關[12]，因此在設置交貨期寬裕度系數(shù)k時考慮不同車間利用率下取不同的值。如文獻[11]中，針對80%車間利用率，寬裕度系數(shù)的一組不同松緊程度的取值為k=(2.5,5.0,7.5,10.0)，而在90%車間利用率下，寬裕度系數(shù)的取值分別為k=(5.0,10.0,15.0,20.0)。這一種方法考慮了車間環(huán)境對交貨期的影響，更為合理，但對于交貨期松緊程度的評判，尚未考慮具體的指標。3) 以某個基準調(diào)度規(guī)則進行仿真調(diào)度，根據(jù)拖期工件百分比的幾個不同級別，確定寬裕度系數(shù)取值。如文獻[13]以FCFS（First come first server）為基準規(guī)則，按拖期工件百分比大致為1%、10%、20%三個等級確定寬裕度系數(shù)；而文獻[14]則選用SPT（Shortest processing time）為基準規(guī)則，按拖期工件百分比5%和20%分別確定相應的緊和松的寬裕度系數(shù)。這一方法引入拖期工件百分比為指標，對交貨期松緊程度進行了定量化的評判，但相關文獻的研究中并未考慮不同的車間利用率。

許多文獻中的試驗都表明，車間利用率是影響交貨期性能的主要參數(shù)[5]。當車間利用率較低時，較小交貨期寬裕度系數(shù)即可對應于較松交貨期；當車間利用率較高時，較大的交貨期寬裕度系數(shù)也可能對應于較緊交貨期。因此本文將對后兩種方法進行綜合，并在基準調(diào)度規(guī)則和評判標準方面進行了一定的改進，研究了面向交貨期相關性能指標的動態(tài)調(diào)度問題仿真研究中寬裕度系數(shù)的確定方法；探索了不同拖期工件百分比下寬裕度系數(shù)隨車間利用率變化的內(nèi)在規(guī)律。

1 基準規(guī)則選擇及評判標準的確定

1.1 基準規(guī)則的選擇

已有的關于交貨期寬裕度系數(shù)研究的文獻中，通常選擇一些簡單規(guī)則作為基準進行仿真調(diào)度。最常用的規(guī)則為調(diào)度規(guī)則性能比對中使用的標桿規(guī)則，如SPT規(guī)則和FIFO（First-in first-out）或FCFS規(guī)則。然而，這些規(guī)則中不包含交貨期相關的任何信息，且對如拖期時間等交貨期相關的性能指標來說性能不佳。因此，由此確定的寬裕度系數(shù)所反映出的松緊程度對許多含交貨期信息的規(guī)則（如EDD，earliest due date；MDD，modified due date，ODD，earliest operation due date；RR，rule by Raghu and Rajendran等）來說是偏松的。本文中，為研究面向交貨期相關性能指標的動態(tài)調(diào)度問題仿真研究中寬裕度系數(shù)的確定方法，我們選擇三個最常用的含交貨期信息的簡單規(guī)則，即EDD、MDD和ODD作為基準規(guī)則。

1.2 評判標準的確定

衡量交貨期松緊程度的指標通常為拖期工件百分比，即完工時間大于設定交貨期的工件的數(shù)量占所有工件的百分數(shù)，記為 T % 。文獻[13]選用了三個級別，即 T % 大致為1%、10%、20%；文獻[14]選用選擇了兩個等級，T%≈5%和T%≈20%，大致對應于松交貨期和緊交貨期兩種情況；而文獻[3]中則明確提到交貨期的緊（tight）、中等（moderate）和松（loose）三個級別，其對應的拖期工件百分比 T % 分別為50%、25%、10%?？梢姡瑢回浧谒删o程度目前尚無統(tǒng)一的標準。由于交貨期松緊程度本身即是一個模糊概念，因此在本文的研究中，我們以一個范圍作為松緊程度的評判標準，具體的評判標準取定為：T%=0%～10%對應于松交貨期，T%=10%～30%對應于中等交貨期，T%＞30%對應于緊交貨期。

2 試驗設計

工件陸續(xù)到達的Job Shop調(diào)度問題是一種典型的動態(tài)車間作業(yè)調(diào)度問題。本文將針對此類問題進行仿真調(diào)度試驗，以探索在不同車間利用率和不同交貨期松緊程度下寬裕度系數(shù)的設置問題。

2.1 仿真案例生成方法

仿真試驗案例中有10臺機器，工件總數(shù)為3000個，以指數(shù)分布形式到達車間。每個工件的工序數(shù)量從離散均勻分布DU[3,6]中產(chǎn)生。工件的工藝路線隨機生成，每道工序的加工機器以相同概率按無放回抽樣方式從10臺機器中產(chǎn)生。每道工序的加工工時從離散均勻分布DU [5,15]中產(chǎn)生，因此每道工序的平均加工時間p=10個單位時間。

車間利用率 Ug用平均工件到達率l來控制。當工件動態(tài)到達的時候，根據(jù)文獻[3,8]，此時車間利用率 Ug的表達式為：

給定一個車間利用率（如 Ug=80%，90%，95%），即可計算出每批工件到達的時間間隔tv。不失一般性，假設第一批工件的到達時間為0，則根據(jù)時間間隔tv可計算出每批工件的到達時間，即投放時間ri。

文獻中常見的仿真試驗設置的車間利用率從50%到97%變化不等。本文從其間選取了9種典型的車間利用率，研究交貨期寬裕度系數(shù)對交貨期松緊程度的影響并對其進行定量的仿真研究。

關于寬裕度系數(shù)k，試驗取值范圍設置為（2，50），以增量2進行遞增。然后根據(jù)拖期工件百分比，確定不同車間利用率下合理的交貨期寬裕度系數(shù)k的取值。

2.2 試驗過程、數(shù)據(jù)獲取與處理

為了使抽樣統(tǒng)計的樣本更加接近實際，需要進行多次統(tǒng)計計算平均值，本文中，進行從50%～97%共9種利用率下的仿真調(diào)度，每種車間利用率下生成20個仿真案例，考慮車間穩(wěn)定狀態(tài)和所采集數(shù)據(jù)的有效合理性，截除前后各500個工件[6]，采集20次仿真[16]在三個調(diào)度規(guī)則EDD、MDD和ODD下的拖期工件百分比，第i次仿真結果分別記

則的完工時間，RULE取值為上述三個調(diào)度規(guī)則。

記拖期工件百分比的總體均值為 T % ，由下式計算：

3 試驗結果及分析

為分析不同車間利用率和不同交貨期松緊程度下交貨期寬裕度系數(shù)的合理取值，基于Java語言開發(fā)了相應的仿真調(diào)度系統(tǒng)，并在JBuilder集成開發(fā)環(huán)境下進行了仿真運行，得到了相應的仿真試驗結果，并進一步對結果進行了分析。

3.1 試驗結果

經(jīng)過仿真試驗 ，我們得到在不同車間利用率下，選取不同交貨期寬裕度系數(shù)k時的拖期工件百分比 %T 。結果如表1和圖1所示。

圖1 不同 gU 下， %T 隨k變化的曲線

3.2 結果分析

從所得曲線圖可以看出，當車間利用率一定時，拖期工件百分比隨著交貨期寬裕度系數(shù)的增大而減小。即在設置交貨期時，按TWK方法，若取較小的寬裕度系數(shù)k，則會出現(xiàn)較多的拖期工件；反之，若取較大的k值，則拖期工件會較少。因此可以根據(jù)需要選取不同的交貨期寬裕度系數(shù)值。另一方面，比較不同車間利用率下的曲線可發(fā)現(xiàn)，當交貨期寬裕度系數(shù)一定時，車間利用率較小的車間中的拖期工件較少，而車間利用率較大的車間中拖期工件較多。這進一步證實了車間利用率是影響交貨期的重要因素，因此在設置交貨期時，可根據(jù)不同車間利用率設置不同松緊程度的交貨期。發(fā)動機性能信息重疊，提高計算速度。

表1 典型 gU 下取不同k時的 %T

[1] 張海軍,左洪福,梁劍.航空發(fā)動機多指標模糊信息熵的性能排序研究[J]. 應用科學學報,2006,24(3):288-292.

[2] 楊皓翔,梁川,侯小波.改進的TOPSIS模型在地下水水質(zhì)評價中的應用[J].南水北調(diào)與水利科技,2012, (5):51-55.

[3] 肖淳,邵東國,楊豐順.基于改進TOPSIS法的流域初始水權分配模型[J].武漢大學學報（工學版）,2012,45(3):329-334.

[4] Karimi M, Moztarzadeh F,Pakzad A. Application of Fuzzy TOPSIS for Group Decision making in Evaluating Financial Risk Management, 2012[C].Malacca, Malaysia,2012 International Conference on Innovation, Management and Technology Research (ICIMTR2012),2012:215-218.

[5] 欒圣罡.基于氣路參數(shù)樣本的航空發(fā)動機狀態(tài)監(jiān)控監(jiān)視方法與系統(tǒng)研究[D]. 哈爾濱:哈爾濱工業(yè)大學,2008.

[6] Karimi M, Moztarzadeh F, Pakzad A. Application of Fuzzy TOPSIS for Group Decision making in Evaluating Financial Risk Management,2012[C].Malacca, Malaysia,2012 International Conference on Innovation, Management and Technology Research (ICIMTR2012),2012:215-218.

[7] 陳可嘉,于先康.逆向物流服務供應商選擇的ANP方法及Super Decisions軟件實現(xiàn)[J].福州大學學報（自然科學版）,2012,40(1):31-37.