熊禾根，錢國(guó)潔，范華麗，蔣國(guó)璋

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

0 引言

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

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

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

2 樣本容量的確定方法

2.1 基本思路

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

2.2 確定方法

2.2.1 抽樣方法

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

2.2.2 計(jì)算公式與步驟

1）樣本容量的計(jì)算公式

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

令Δ表示均值估計(jì)偏差，即：

可得樣本容量為：

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

2）樣本容量的計(jì)算步驟

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

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

3 仿真案例

動(dòng)態(tài)車間調(diào)度模型的仿真基本數(shù)據(jù)如下：車間機(jī)器數(shù)量為10，車間利用率取為85%，每個(gè)工件所含工序數(shù)量由離散均勻分布DU[3，6]產(chǎn)生，工序工時(shí)由均勻分布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%，拖期工件百分比均值的估計(jì)偏差為±2%。仿真調(diào)度的原始數(shù)據(jù)及統(tǒng)計(jì)分析結(jié)果如表1所示。表中指標(biāo)及統(tǒng)計(jì)量計(jì)算方式如下：

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

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

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

4 結(jié)論

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

表1 仿真調(diào)度數(shù)據(jù)及統(tǒng)計(jì)分析結(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é)報(bào)(工學(xué)版),2005,35(4):74-79.

[5] 宋曉宇,曹陽(yáng),孟秋宏.求解Job Shop調(diào)度問(wèn)題的粒子群算法研究[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é)報(bào)(工科版),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ó)璋.考慮工序相關(guān)性的動(dòng)態(tài)Job shop調(diào)度問(wèn)題啟發(fā)式算法[J].機(jī)械工程學(xué)報(bào),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.