動態Job Shop調度仿真中的交貨期設置問題研究

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

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

0 引言

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

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

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

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

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

1 基準規則選擇及評判標準的確定

1.1 基準規則的選擇

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

1.2 評判標準的確定

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

2 試驗設計

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

2.1 仿真案例生成方法

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

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

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

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

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

2.2 試驗過程、數據獲取與處理

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

則的完工時間，RULE取值為上述三個調度規則。

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

3 試驗結果及分析

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

3.1 試驗結果

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

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

3.2 結果分析

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

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

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

[2] 楊皓翔,梁川,侯小波.改進的TOPSIS模型在地下水水質評價中的應用[J].南水北調與水利科技,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] 欒圣罡.基于氣路參數樣本的航空發動機狀態監控監視方法與系統研究[D]. 哈爾濱:哈爾濱工業大學,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軟件實現[J].福州大學學報（自然科學版）,2012,40(1):31-37.