動態車間調度問題調度規則算法仿真試驗的樣本容量確定方法

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

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

0 引言

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

1 相關研究及問題提出

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

2 樣本容量的確定方法

2.1 基本思路

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

2.2 確定方法

2.2.1 抽樣方法

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

2.2.2 計算公式與步驟

1）樣本容量的計算公式

對于動態車間作業調度仿真試驗來說，樣本容量即是獨立仿真調度的次數。樣本容量越大，樣本的統計量與總體的統計量越接近；對應地，仿真調度所獲得的性能指標值能更接近地反映其真值。但顯然這樣需要付出更多的消耗（計算時間或成本等）。可以認為總體是服從正態分布的，以多次仿真調度所獲得的性能指標值均值作為統計量，在總體方差未知的情況下，有：

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

可得樣本容量為：

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

2）樣本容量的計算步驟

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

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

3 仿真案例

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

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

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

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

4 結論

仿真調度是評價調度規則性能好壞最常用的方法。一次仿真調度相當于一次隨機試驗。為使評價結果具有統計學意義，且盡量降低仿真試驗的代價，有必要合理確定仿真調度的運行次數。本文將統計學的區間估計方法應用于仿真試驗調度設計中，推導了樣本容量的計算公式，提出了樣本容量的確定方法，并進一步利用仿真案例進行了說明。

表1 仿真調度數據及統計分析結果

[1] 王凌,鄭大鐘.基于遺傳算法的Job Shop調度研究進展[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調度[J].山東大學學報(工學版),2005,35(4):74-79.

[5] 宋曉宇,曹陽,孟秋宏.求解Job Shop調度問題的粒子群算法研究[J].系統工程與電子技術,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] 曾明如,游文堂,錢信,韓偉.基于專家系統的貨位管理與作業調度優化[J].南昌大學學報(工科版),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] 劉輝,陳友玲.基于客戶滿意度的模糊神經網絡JSP研究[J].世界科技研究與發展,2011,33(5):809-813.

[11] 熊禾根,李建軍,孔建益,楊金堂,蔣國璋.考慮工序相關性的動態Job shop調度問題啟發式算法[J].機械工程學報,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.