動態(tài)Job Shop調(diào)度仿真中的交貨期設(shè)置問題研究

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

（武漢科技大學(xué) 機(jī)械自動化學(xué)院，武漢 430081）

0 引言

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

現(xiàn)有的交貨期設(shè)置方法有多種，包括考慮工件特征信息（如總加工工時、總工序數(shù)等）的靜態(tài)規(guī)則和綜合考慮工件信息與車間狀態(tài)信息（包括工件到達(dá)時系統(tǒng)中已有的工件數(shù)量、工件到達(dá)時在它的加工路徑上的工件數(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ī)則被認(rèn)為是交貨期設(shè)置的最好方法[4]，也是所有的交貨期設(shè)置方法中使用最為廣泛的方法之一。記工件Jj的投放時間為rj，工件的總工時為Pj（含裝設(shè)時間），根據(jù)TWK規(guī)則，工件的交貨期dj設(shè)置為：

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

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

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

1 基準(zhǔn)規(guī)則選擇及評判標(biāo)準(zhǔn)的確定

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

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

1.2 評判標(biāo)準(zhǔn)的確定

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

2 試驗設(shè)計

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

2.1 仿真案例生成方法

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

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

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

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

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

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

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

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

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

3 試驗結(jié)果及分析

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

3.1 試驗結(jié)果

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

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

3.2 結(jié)果分析

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

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

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

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

[3] 肖淳,邵東國,楊豐順.基于改進(jìn)TOPSIS法的流域初始水權(quán)分配模型[J].武漢大學(xué)學(xué)報（工學(xué)版）,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ā)動機(jī)狀態(tài)監(jiān)控監(jiān)視方法與系統(tǒng)研究[D]. 哈爾濱:哈爾濱工業(yè)大學(xué),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] 陳可嘉,于先康.逆向物流服務(wù)供應(yīng)商選擇的ANP方法及Super Decisions軟件實現(xiàn)[J].福州大學(xué)學(xué)報（自然科學(xué)版）,2012,40(1):31-37.