動態(tài)車間調(diào)度問題調(diào)度規(guī)則算法仿真試驗的樣本容量確定方法

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

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

0 引言

車間作業(yè)調(diào)度問題是制造系統(tǒng)信息化與自動化技術(shù)需要解決的關(guān)鍵問題之一，是先進(jìn)制造技術(shù)中的重要研究主題，也是運籌學(xué)研究的熱門問題之一?；谡{(diào)度要素相關(guān)信息獲取的時間特性，車間調(diào)度問題可分為靜態(tài)和動態(tài)兩種類型。在絕大多數(shù)實際制造系統(tǒng)中，作業(yè)任務(wù)是陸續(xù)到達(dá)的，屬于動態(tài)調(diào)度問題。此外，與經(jīng)典調(diào)度問題相比，實際制造系統(tǒng)的調(diào)度問題中通常包括許多復(fù)雜和不確定因素，因而，在求解算法方面，雖然學(xué)者及工程技術(shù)人員提出了諸多智能算法，如進(jìn)化類算法[1,2]、蟻群算法[3,4]、粒子群算法[5,6]、專家系統(tǒng)方法[7,8]、神經(jīng)網(wǎng)絡(luò)算法[9,10]等，但基于調(diào)度規(guī)則的算法仍以其求解復(fù)雜大規(guī)模動態(tài)調(diào)度問題經(jīng)濟(jì)、快速而有效的特點得到許多研究者的關(guān)注，并在實際調(diào)度系統(tǒng)中得到較廣泛應(yīng)用。在過去的50余年中，各類文獻(xiàn)資料中所提出的調(diào)度規(guī)則已有上百種；然而，由于調(diào)度規(guī)則的性能好壞與求解問題的模型密切相關(guān)的，且目前尚無有效的解析方法可對規(guī)則性能進(jìn)行有效的分析評價。因此，對于調(diào)度規(guī)則的使用，多數(shù)研究者一般基于已有的研究結(jié)果，先在已提出的調(diào)度規(guī)則初步甄選出若干規(guī)則，或嘗試開發(fā)一些新調(diào)度規(guī)則；然后采用模擬實驗的方法，對具體調(diào)度問題進(jìn)行調(diào)度仿真，通過對仿真結(jié)果的統(tǒng)計分析，來評價調(diào)度規(guī)則于具體調(diào)度問題的性能[2]。

1 相關(guān)研究及問題提出

德國帕紹大學(xué)Holthaus和印度理工學(xué)院Rajendran是對調(diào)度規(guī)則設(shè)計、仿真及評價研究最多的學(xué)者。文獻(xiàn)[3]提到重復(fù)仿真次數(shù)為10次；文獻(xiàn)[4～6]中提到獨立仿真次數(shù)為20次；文獻(xiàn)[7]中提到的獨立仿真次數(shù)為30次；文獻(xiàn)[8]中提到的迭代次數(shù)為100?？梢?，在不同文獻(xiàn)中，關(guān)于獨立仿真次數(shù)的采用有所差別，且尚無一個公認(rèn)基準(zhǔn)，文獻(xiàn)中也未給出采用相應(yīng)仿真次數(shù)的理論依據(jù)。顯然，把仿真調(diào)度看做一種隨機(jī)試驗，從統(tǒng)計學(xué)意義上，獨立仿真次數(shù)越多，仿真數(shù)據(jù)的統(tǒng)計結(jié)果更能反映總體特性；但另一方面，對于復(fù)雜大規(guī)模調(diào)度問題來說，更多獨立仿真次數(shù)必然需要付出更大的代價。因而，在滿足一定置信度和置信區(qū)間內(nèi)，合理的仿真次數(shù)應(yīng)該為多少，其研究具有重要意義。

2 樣本容量的確定方法

2.1 基本思路

基于調(diào)度規(guī)則的仿真調(diào)度過程實際上相當(dāng)于一個隨機(jī)試驗過程。采用一個調(diào)度規(guī)則進(jìn)行一次仿真調(diào)度，相當(dāng)于進(jìn)行一次隨機(jī)試驗抽樣，所得到的某個調(diào)度性能指標(biāo)值（如最大完工時間、最大延期/拖期、總延期/拖期、拖期工件總數(shù)/百分比等）即是一個抽樣觀測值。仿真調(diào)度的目的是對不同調(diào)度規(guī)則進(jìn)行若干次仿真調(diào)度，相當(dāng)于進(jìn)行多次抽樣，根據(jù)抽樣結(jié)果，進(jìn)行合理的統(tǒng)計分析，以對不同調(diào)度規(guī)則性能進(jìn)行比對，判斷其性能差異是否具有統(tǒng)計學(xué)意義，差異程度如何，孰優(yōu)孰劣，從而為實際調(diào)度系統(tǒng)應(yīng)用中調(diào)度規(guī)則的選擇提供參考。

2.2 確定方法

2.2.1 抽樣方法

基于所需考察的動態(tài)調(diào)度問題模型，以車間為空閑狀態(tài)開始（即所有機(jī)器均閑置，其前無加工隊列），生成仿真調(diào)度案例。初始階段，車間的任務(wù)量較少，顯然，此時即開始采樣將產(chǎn)生初始偏誤。應(yīng)待車間達(dá)到穩(wěn)定狀態(tài)時開始進(jìn)行有效數(shù)據(jù)的采樣。許多文獻(xiàn)提到500個工件到達(dá)后可認(rèn)為車間達(dá)到穩(wěn)定狀態(tài)，因此，有效的采樣從第501個到達(dá)的工件開始[9]。動態(tài)車間系統(tǒng)可以看作是一種“非中斷式”系統(tǒng)，仿真采樣需要關(guān)注的是調(diào)度性能指標(biāo)的長期平均值或穩(wěn)態(tài)行為。文獻(xiàn)中通常以到達(dá)穩(wěn)定狀態(tài)后完成2000個工件的加工作為系統(tǒng)達(dá)到對其長期行為的一個合理近似。因此，采樣的結(jié)束可按第2500個工件加工完成為節(jié)點，為保持采樣一直處于車間穩(wěn)定狀態(tài)，在第2500個工件完成之前，需保持工件一直按模型陸續(xù)到達(dá)車間。

2.2.2 計算公式與步驟

1）樣本容量的計算公式

對于動態(tài)車間作業(yè)調(diào)度仿真試驗來說，樣本容量即是獨立仿真調(diào)度的次數(shù)。樣本容量越大，樣本的統(tǒng)計量與總體的統(tǒng)計量越接近；對應(yīng)地，仿真調(diào)度所獲得的性能指標(biāo)值能更接近地反映其真值。但顯然這樣需要付出更多的消耗（計算時間或成本等）?？梢哉J(rèn)為總體是服從正態(tài)分布的，以多次仿真調(diào)度所獲得的性能指標(biāo)值均值作為統(tǒng)計量，在總體方差未知的情況下，有：

令Δ表示均值估計偏差，即：

可得樣本容量為：

在確定置信度1-α及均值估計偏差Δ后，可由式(3)計算所需樣本容量，即獨立仿真調(diào)度的運行次數(shù)。然而，因式(3)右側(cè)的t分布的雙側(cè)1002/α百分位點與n有關(guān)，因此，需通過試算確定樣本容量。

2）樣本容量的計算步驟

基于上述的公式與方法，樣本容量的計算步驟敘述如下。

Step3：查t分布分位數(shù)表，并由式(3)計算n值；

3 仿真案例

動態(tài)車間調(diào)度模型的仿真基本數(shù)據(jù)如下：車間機(jī)器數(shù)量為10，車間利用率取為85%，每個工件所含工序數(shù)量由離散均勻分布DU[3，6]產(chǎn)生，工序工時由均勻分布U[5，15]產(chǎn)生，交貨期設(shè)置的寬裕度系數(shù)取為6。采用MDD（Modif i ed Due-Date）調(diào)度規(guī)則，進(jìn)行若干次仿真調(diào)度。記拖期工件數(shù)量為T，以拖期工件百分比T%為性能指標(biāo)。取置信度為99%，拖期工件百分比均值的估計偏差為±2%。仿真調(diào)度的原始數(shù)據(jù)及統(tǒng)計分析結(jié)果如表1所示。表中指標(biāo)及統(tǒng)計量計算方式如下：

由表1可知，置信度99%下拖期工件百分比均值估計偏差為±2%時的樣本容量為17，即需要獨立運行17次仿真調(diào)度，可滿足要求。

事實上，由表中數(shù)據(jù)可知，一定次數(shù)運行后方差相對比較穩(wěn)定，因此，一種簡略而變通的估計方式是：進(jìn)行一定次數(shù)的獨立仿真運行（如取），對方差取均值，即：

此后，可不再繼續(xù)運行，將方差固定取為，再根據(jù)式(3)及t分布分位數(shù)表估計樣本容量。

4 結(jié)論

仿真調(diào)度是評價調(diào)度規(guī)則性能好壞最常用的方法。一次仿真調(diào)度相當(dāng)于一次隨機(jī)試驗。為使評價結(jié)果具有統(tǒng)計學(xué)意義，且盡量降低仿真試驗的代價，有必要合理確定仿真調(diào)度的運行次數(shù)。本文將統(tǒng)計學(xué)的區(qū)間估計方法應(yīng)用于仿真試驗調(diào)度設(shè)計中，推導(dǎo)了樣本容量的計算公式，提出了樣本容量的確定方法，并進(jìn)一步利用仿真案例進(jìn)行了說明。

表1 仿真調(diào)度數(shù)據(jù)及統(tǒng)計分析結(jié)果

[1] 王凌,鄭大鐘.基于遺傳算法的Job Shop調(diào)度研究進(jìn)展[J].控制與決策,2001,16(Z1):641-646.

[2] Wannaporn Teekeng,Arit Thammano.Modif i ed Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science,2012(12):122-128.

[3] Rajendran Chandrasekharan, Ziegler Hans. Ant-colony algorithms for permutation fl owshop scheduling to minimize makespan / total flowtime of jobs[J].European Journal of Operational Research,2004,155(2):426-438.

[4] 陳知美,顧幸生.基于蟻群算法的不確定條件下的Job Shop調(diào)度[J].山東大學(xué)學(xué)報(工學(xué)版),2005,35(4):74-79.

[5] 宋曉宇,曹陽,孟秋宏.求解Job Shop調(diào)度問題的粒子群算法研究[J].系統(tǒng)工程與電子技術(shù),2008,30(12):2398-2401.

[6] Koulinas Georgios,Lazaros Kotsikas,Konstantinos Anagnostopoulos. A particle swarm optimization based hyperheuristic algorithm for the classic resource constrained project scheduling problem[J].Information Sciences,2014,277:680-693.

[7] David A. Ress,Kenneth R.Currie. Development of an expert system for scheduling work content in a job shop environment [J].Computers & Industrial Engineering,1993,25(1-4):131-134.

[8] 曾明如,游文堂,錢信,韓偉.基于專家系統(tǒng)的貨位管理與作業(yè)調(diào)度優(yōu)化[J].南昌大學(xué)學(xué)報(工科版),2009,31(4):385-388.

[9] Haibin Yu,Wei Liang.Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling[J].Computers &Industrial Engineering,2001,39(3-4):337-356.

[10] 劉輝,陳友玲.基于客戶滿意度的模糊神經(jīng)網(wǎng)絡(luò)JSP研究[J].世界科技研究與發(fā)展,2011,33(5):809-813.

[11] 熊禾根,李建軍,孔建益,楊金堂,蔣國璋.考慮工序相關(guān)性的動態(tài)Job shop調(diào)度問題啟發(fā)式算法[J].機(jī)械工程學(xué)報,2006,42(8):50-55.

[12] Holthaus Oliver,Rajendran Chandrasekharan.Efficient dispatching rules for scheduling in a job shop[J].Int.J.Production Economics,1997,48:87-105.

[13] Holthaus O.Design of efficient job shop scheduling rules[J].Computers ind. Engng,1997,33(1-2):249-252.

[14] Rajendran Chandrasekharan , Holthaus Oliver.A comparative study of dispatching rules in dynamic fl owshops and jobshops[J].European Journal of Operational Research,1999,116:156-170.

[15] Jayamohan M S,Rajendran Chandrasekharan. Development and analysis of cost-based dispatching rules for job shop scheduling[J].European Journal of Operational Research,2004,157:307-321.

[16] Holthaus Oliver.Scheduling in job shops with machine breakdowns:an experimental study[J].Computers and Industrial Engineering,1999,36:137-162.

[17] Chen Binchao,Matis Timothy I.A flexible dispatching rule for minimizing tardiness in job shop scheduling[J].Int. J. Production Economics,2013,141:360-365.

[18] Raghu T S,Rajendran Chandrasekharan. An efficient dynamic dispatching rule for scheduling in a job shop[J].Internationul Journal of Production Economics,1993,32:301-313.