作業車間調度規則的挖掘方法研究

王成龍，李 誠，馮毅萍，榮 岡

（工業控制國家重點實驗室，浙江大學 智能系統與控制研究所，浙江 杭州310027）

生產調度是現代工業先進制造和管理的核心技術.作業車間調度問題（job shop scheduling problem，JSP），作為研究最為廣泛的確定性生產調度優化問題［1］，受到了學者們的廣泛關注.JSP是許多實際工業生產調度問題的簡化模型，許多非工業調度問題同樣可以被轉化為作業車間調度問題.JSP是一種復雜的NP-hard問題，即使對于小規模的問題案例，也無法通過遍歷可行解的方式獲得最優解.而且，其可行解空間的規模隨著案例規模的增大而呈指數形式增大.一直以來，JSP都被看作是組合優化（Combinatorial optimization）問題的典型代表.針對這一問題所開發的求解策略，可以應用于許多其它組合優化問題的求解.

目前，應用于JSP的常用優化方法包括分支定界法［2］、遺傳算法［3-5］、模擬退火算法［6-7］以及禁忌搜索算法［8］等自適應搜索算法.這些方法均能成功應用于求解JSP，并能求取最優解或近似最優解.求得的優化解中往往包含著有關該調度問題的有價值的規律或知識.但這些方法的實現過程復雜，需要進行大量的參數整定工作和較長的計算時間，無法適應作業車間實時變化的作業狀態.這些方法雖然能夠求取最優解或是近似最優解，但卻無法解釋優化解是如何生成的，或是無法說明這些優化解的共同特性［9］.相反，優先調度規則（priority dispatching rules，PDR）給出了一種基于知識的調度過程決策方法.PDR往往由長期積累獲得的有關調度問題的專家知識抽象而來.利用PDR指導生產調度的過程容易實現，且計算簡單，并能夠適應作業車間的實時變化.但傳統的優先調度規則往往性能較差，無法產生較優的結果.一種新的研究思路是從利用分支定界法或是自適應搜索算法所獲得的優化解中挖掘有價值的規律或知識，用以構造新的調度規則.新調度規則既具有傳統PDR的優點，又能夠較好地保留這些優化算法的優化能力，生成逼近最優解的較優方案.

利用由傳統優化算法所獲得的調度問題優化解構造新的調度規則是一種新興的研究思路［10-11］.Koonce等［12］利用遺傳算法求解一個6×6基準問題，并應用一種面向屬性的歸納算法挖掘優化解中的隱含規律.所生成的規則集能較好地逼近遺傳算法的調度性能，優于傳統的最短時間規則（shortest processing time，SPT）.Weckman等［9］同樣采用遺傳算法求解JSP，并運用人工神經網絡（artificial neutral network，ANN）從優化解中學習新的調度規則.Kumar等［13-14］分別將蟻群算法和禁忌搜索算法應用于生產調度問題，并利用這兩種自適應搜索算法生成的優化解構造新的調度規則.

本文利用Petri網對JSP進行建模，并給出一種分支定界算法用于搜尋優化調度方案.在此基礎上，提出一種基于決策樹（decision tree，DT）分類技術的調度知識挖掘方法，用于挖掘隱藏在優化調度方案中的調度知識.所提取的調度知識可以直接作為新的調度規則來指導作業車間的調度過程.

1 基于Petri網的作業車間調度問題建模及優化

1.1 經典Petri網絡

經典的Petri網絡可以表示為4元組

許多離散事件系統需要考慮時間屬性，經典Petri網同樣可以描述時間信息.時間Petri網根據時間屬性所處的位置分為兩類：時間屬性位于庫所（timed place Petri net，TPPN）；時間屬性位于變遷（timed transition Petri net，TTPN）.本文采用TPPN對JSP進行建模.TPPN可以表達如下：

其中γ表示當前狀態下各個庫所的時間參數的集合.

1.2 作業車間調度問題建模

近年來，基于Petri網的生產調度問題研究取得了廣泛的關注.Petri網模型可以簡潔詳細地表達出調度過程的所有狀態［15］，并很好地表達生產調度過程中的動態行為特性.結合其他的優化方法，Petri網建模即可用于求解生產調度問題.通過這種方式，Petri網的狀態表達能力可以與傳統優化方法的優化求解能力有效地結合起來，并為進一步調度知識挖掘提供有價值的調度數據，因此，Petri網建模十分有利于生產調度過程中的知識發現.

對Ghaeli等［16］提出的Petri網建模方法進行改進，得到JSP建模策略.Ghaeli等［16］利用Petri網對批調度問題進行建模.但所提出的建模方法無法表達調度任務的全部中間過程，如各加工操作的開始與結束以及加工任務的中間等待過程等.這不利于對調度過程的分析和相關調度數據的提取.在此基礎上，使用如下方式建立JSP的Petri網模型.

1）對于加工工件i，其第j個加工操作o ij對應于一個庫所p ij，其時間參數為γij，代表這一加工操作的加工時間；2個相鄰的加工操作庫所p ij和p ik之間對應于一個等待庫所p ijk，代表2個相鄰的加工操作之間的等待狀態，其時間參數為0；加工工件i還對應于一個起始庫所p is和一個終止庫所p if，用于代表該加工任務的開始和結束，其時間參數均為0.這4種庫所即可用于代表加工工件i的所有不同狀態.

2）加工機器m對應于一個庫所p m，代表一個加工資源，其時間參數為0.

3）加工操作庫所p ij擁有一個輸入變遷t sij和一個輸出變遷t fij，分別代表加工操作的開始和結束.變遷tsij以等待庫所p i（j-1）j作為輸入庫所，變遷t fij以等待庫所p ij（j+1）作為輸出庫所.特別地，變遷tsi1以起始庫所p is作為輸入庫所，變遷t fim以終止庫所p if作為輸出庫所.按這種方式，代表同一加工工件的各個庫所和變遷按加工順序相互連接.此外，任一個加工操作開始變遷tsij對應于一個機器庫所作為輸入，該機器為相應的加工操作所對應的加工機器，該連接代表對機器的占用.任一個加工操作結束變遷t fij對應于一個機器庫所作為輸出，該機器同樣為相應的加工操作所對應的加工機器，該連接代表對機器的釋放.

4）每個加工工件擁有一個令牌，并在起始階段存儲于起始庫所中.令牌的位置代表該加工工件的當前加工狀態.此外，每個機器庫所在初始時刻也擁有一個令牌.機器庫所的令牌代表該加工資源的空閑狀態，即該機器已經準備好進行工件的加工.

利用上述方式，即可建立JSP的TPPN模型.其中除每個表示加工操作庫所的時間屬性代表其對應的加工時間外，其它庫所的時間屬性均為0，表示資源或加工狀態的直接可用性.

以表1所示的一個2×2的JSP為例，其中每個數據表格中的第一個數據表示加工操作所對應的機器，第二個數據表示加工操作的加工時間.其TPPN模型如圖1所示.圖1所示的調度過程處于初始狀態，該初始狀態可以表示為

狀態矩陣M0被分解為3個子矩陣，分別代表相應的加工工件和機器的當前狀態.

表1 2×2作業車間調度問題示例Tab.1 Example of 2×2 job shop scheduling problem

圖1 2×2作業車間調度問題TPPN模型Fig.1 TPPN model of the 2×2 job shop scheduling problem

1.3 基于Petri網的分支定界算法

在改進一種基于Petri網的啟發式搜索算法［16］的基礎上，針對最小化最大完工時間（Makespan）這一性能指標，提出一種基于Petri網的分支定界算法用于求解JSP.該算法可以用于求取JSP的優化解.所求取的優化調度方案即可以用于進一步的調度知識發現.

該分支定界算法是從Petri網模型的初始狀態開始，通過不斷觸發允許的變遷來構建可達樹.可達樹一個節點對應于TPPN模型的一個狀態.每個節點向下的不同分支代表觸發不同的變遷.可達樹的所有葉節點均代表TPPN的終止狀態，即代表調度加工任務的結束.因此，每一條從可達樹根節點到葉節點的路徑均為對應JSP問題的一個可行解.

每個可行解由從起始狀態到終止狀態的狀態序列組成，代表作業車間的動態調度過程.對于每個非葉結點，其向下可能通過多條路徑到達葉節點，即對應著多個可行解.根節點對應著整個可行解空間.分支定界算法通過不斷擴展可達樹來搜索最優解，其分支策略即對應于可達樹的分支策略.

對于每個非葉節點M k，采用Ghaeli等［16］提出的如下公式計算其所對應的可行解集合的makespan下界：

f（Mk）為Mk對應的可行解集合的Makespan下界.

g（Mk）為當前狀態Mk的生成時間即當前時刻.

h（Mk）為從當前狀態Mk到達葉節點即終止狀態所需時間的下限估計.其中τij表示加工任務i在機器j上的加工時間.U j（Mk）表示機器j已經運行的時間（不包括其空閑時間），而代表它的剩余運行時間.表示工件i已被加工的時間，而代表工件i總的剩余加工時間.利用式（4）得到的最大完工時間估計值滿足

f*（Mk）為Mk所對應的可能的調度方案的實際Makespan.f（Mk）可作為節點Mk所對應的可行解集合的Makespan下界，用以縮小搜索規模，提高計算效率.

基于Petri網的分支定界算法的重點在于如何由當前節點通過觸發變遷到達新的節點.與文獻［16］中的啟發式算法不同，本文結合所構建的TPPN模型特點，提出一種新的變遷觸發方法用以從當前節點生成新節點.對TPPN模型分析可得，所有加工操作輸出變遷不會與其他變遷發生沖突，因此可以同時觸發所有允許的輸出變遷.觸發順序不會對結果產生影響.而加工操作輸入變遷可能會由于與其他輸入變遷爭奪加工資源而發生沖突.為此，本文提出如下的變遷觸發策略：

1）觸發所有允許的加工操作輸出變遷；

2）確定當前時刻所有的可用機器庫所.對于其中每個庫所，可以選定一個與之相連的允許的加工操作輸入變遷（不存在的則忽略不計）.這些輸入變遷即可以組成一個不沖突的變遷組合.依次觸發其中的變遷，可以生成一個新的狀態.找出所有不沖突輸入變遷組合，即可生成當前節點的所有下行節點.

利用這種新狀態生成策略可以同時觸發多個變遷，從而有效減少可達樹的節點數，縮減可達樹的規模，進一步提高計算效率.

基于Petri網的分支定界算法采用遞歸的方式進行.遞歸從TPPN的初始狀態開始，并以一個較大值作為當前獲得的初始最小Makespan.遞歸函數運算步驟如下：

1）獲取當前狀態Mk.

2）計算后續調度生產時間下限h（Mk），結合當前時間g（Mk），計算 Makespan下界f（Mk）.若f（Mk）大于或等于當前的最小Makespan，程序返回.

3）若Mk等于終止狀態，轉到步驟5）.

4）由當前狀態Mk確定下一個最近的調度決策點（調度決策點為一臺機器剛剛完成一個加工操作時所對應的時刻）.在該調度決策點，利用如上所述的變遷觸發策略，獲取一組新的狀態.分別利用新的狀態重新調用遞歸函數，程序返回.

5）分支到達最終狀態，如果該分支對應的可行解的最大完工時間小于當前獲得的最小Makespan，將其更新為新的最大完工時間，程序返回.

2 作業車間調度規則挖掘

2.1 目標調度模式定義

對于JSP問題，在每一個調度決策點，可能會有多個加工操作等待在同一臺空閑機器上進行加工.這些加工操作之間存在沖突.在這種情況下，需要依據優化目標的要求選擇一個最優加工操作在這臺機器上進行下一步加工.若能對任意2個沖突加工操作進行對比，確定應先對哪個加工操作進行加工，即可通過兩兩對比，從所有沖突的加工操作中選出最優的加工操作.據此，定義要挖掘的目標調度模式：給定2個需要在同一臺機器上進行加工的沖突加工操作（oper1和oper2），如何根據其相關信息以及相應的調度環境信息等，確定哪一個加工操作應該先進行加工.Li等［17-18］將這一調度模式定義應用于單機器調度的知識發現當中.對于JSP問題，已有的同類方法［9，12-14］往往是以如何確定任意一個加工操作在相應加工機器上的加工序號作為要挖掘的模式.這些方法所提取的調度知識無法直接用于指導作業車間調度過程，需要再結合其他已有的啟發式方法.與此不同，本文所定義的目標調度模式可以作為新的調度規則直接應用于任意規模的作業車間調度問題.

目標調度模式的挖掘問題可以看成是一個分類問題.類屬性取值為0或1：取1表示oper1需要先進行加工，取0表示oper2需要先進行加工.模式挖掘的目標是構建分類模型，用以根據2個沖突加工操作的對比信息以及沖突發生時的調度環境信息，確定需要對哪個加工操作進行加工.

應用較為廣泛的數據挖掘分類模型包括決策樹、神經網絡、貝葉斯分類器以及支持向量機等.選用決策樹用以表達目標調度模式.決策樹是一種類似于流程圖的樹狀結構.其中每個非樹葉節點代表在一個屬性上的測試，而每個樹葉節點對應一個類屬性標號.給定一個類屬性值未知的元組，在決策樹上測試該元組的屬性，根據測試結果從根節點移到一個葉節點.該葉節點就存放著該元組的類屬性預測值.

相對于其他分類模型，決策樹具有以下優點［19］：

1）決策樹模型的學習和分類過程簡單且只需要極少的計算時間.而且，決策樹通常能夠獲得很好的分類準確率.

2）決策樹模型以樹的形式表示所獲取的模式，直觀且便于理解.而且，決策樹模型可以轉換成更加易懂的IF-THEN規則集的形式.這有利于用戶理解所獲取的調度知識.

3）決策樹模型的構建不需要任何領域知識，且無需進行復雜的參數整定，更具有實用性.

2.2 數據收集

歸納出代表目標調度模式的決策樹分類模型，需要收集有價值的相關調度數據用于構建訓練數據集.即需要用一對已知先后加工順序的沖突加工操作的相關信息來構建一個類屬性值已知的訓練實例.一組這樣的訓練實例即可用于訓練代表目標調度模式的決策樹分類模型.

在TPPN建模的基礎上，JSP問題的可行解空間可以表示為一棵可達樹，可達樹上從根節點到葉節點的每條路徑代表一個可行解.在每個非葉節點處，不同分支的出現是由于加工操作輸入變遷之間因爭奪資源令牌而發生沖突.其實際意義為當加工機器完成上一個加工操作而閑置時，可能會有多個加工操作正在等待利用該機器進行加工，從而導致加工隊列的產生.這些加工操作即為沖突的加工操作，不同的分支對應于安排不同的加工操作在該機器上進行下一步加工.

利用基于Petri網模型的分支定界算法可以求取JSP問題的優化解.該優化解對應于可達樹上的一條優化狀態轉移路徑.在優化路徑的每個非葉結點處，一個優化加工操作會從一組正在爭奪同一臺加工機器的沖突加工操作中被選出進行下一步的加工.在該優化調度方案中，這些優化加工操作相對于與其發生沖突的其它加工操作擁有更高的加工優先級.所以，一個最優加工操作與任意一個與其發生沖突的加工操作即可以用于構建一個類屬性值已知的訓練元組.該最優加工操作可以被選作oper1（訓練元組類屬性值為1）或oper2（訓練元組類屬性值為0）.

以表2所示的4×4規模的作業車間調度問題為例，對應的可達樹如圖2所示（由于可達樹的規模較大，只提取可達樹的前兩層作為示例）.Mij表示第i層的第j個節點，M0為根節點.加粗路徑表示由分支定界算法求取的優化調度方案.圖中的矩陣集表示對應節點的狀態矩陣.在初始時刻，工件1、2、3的第一個加工操作需要爭奪機器4，而工件4的第一個加工操作可在機器1上直接完成.工件1、2、3的第一個加工操作即為一組沖突的加工操作.在優化調度方案中，工件1優先進行加工，因此工件1的第一個加工操作即為此次沖突中的最優加工操作.在這種情況下，工件1的第一個加工操作可以分別與工件2和工件3的第一個加工操作組合構建2個類屬性值已知的訓練實例.

表2 4×4作業車間調度問題示例__Tab.2 Example of 4×4 job shop scheduling problem_

圖2 4×4作業車間調度問題的部分可達樹示例Fig.2 Partial reachability tree of 4×4 job shop scheduling problem

2.3 構造輸入屬性集

決策樹歸納需要用一組輸入屬性來描述所使用的訓練實例.這些輸入屬性需要有效地反映有關2個沖突加工操作的對比信息以及沖突發生時的調度環境信息，以便較好地預測類屬性的值.構造輸入屬性集的目的是利用有關加工操作和加工環境的現有屬性或變量，構造出一組最優的屬性集以描述分類問題和最大化分類模型的分類準確率.該過程包含以下2個步驟：

1）屬性創建.基于Petri網表達的優化調度方案可以提供豐富的調度數據，但這些數據中的已有屬性或變量并不足以用于進行分類預測任務.對于所要挖掘的目標模式，需要用一組對比屬性來描述2個沖突加工操作的比較信息.因此，需要在已有屬性或變量的基礎上創建新的屬性.

2）屬性選擇.屬性選擇的目的是從可以獲得的所有屬性中選擇最優的屬性子集用于構建分類模型.與目標分類問題不相關或冗余的屬性會影響分類模型的分類精度，而且會使最終獲得的分類模型更加難以解釋.

已有的用于描述一個加工操作的屬性包括加工時間，等待時間及其在所對應的加工工件中的加工序號.此外，一些已有的有關時間或加工機器的信息可以用于構造描述沖突時調度環境信息的屬性.根據這些已有的屬性，即可以構造有關2個沖突加工操作的對比屬性和相應的調度環境屬性.

對于面向屬性的學習算法，目前尚無有效的方法用于最優屬性子集的選擇［20］.采用一種后向搜索（backward search）的啟發式算法確定一組較優的屬性子集.后向搜索方法從整個屬性集開始，每次從該屬性集中選擇剔除一個屬性，使得剔除該屬性后分類評價函數達到最優，直到滿足終止條件為止.

最終獲得的較優輸入屬性集如表4所示.Machine_Time_Ratio用于描述有關沖突發生時刻的調度環境信息，表示此次沖突對應的加工機器的剩余運行時間占總運行時間（不包括空閑時間）的比值.剩余的4個屬性用于描述有關2個沖突的加工操作的對比信息.

表3 參數符號定義Tab.3 Definition of notations____________

2.4 分類模型構建

包含5個輸入屬性和一個二元類屬性的訓練實例集即可以用于決策樹模型的訓練.使用文獻［21］中的C4.5算法構建決策樹分類模型（見圖3）.C4.5算法是應用最廣泛的決策樹歸納算法，并已被成功應用于許多分類問題中.利用C4.5算法所構建的決策樹模型可以用于表達目標調度模式.給定有關2個沖突加工操作的輸入屬性值，利用該決策樹模型可以預測應先對哪個加工操作進行加工.該決策樹模型可以作為新的調度規則，用于指導作業車間調度過程.

圖3 目標調度模式的決策樹模型Fig.3 Decision tree model of the target scheduling pattern

表4 決策樹輸入屬性集定義Tab.4 Input attributes for the induction of decision trees

3 實驗分析

為了驗證所提出的作業車間調度規則挖掘方法的可行性，利用一組隨機生成的JSP案例構建訓練實例集，并進一步利用所構建的訓練實例集訓練獲得代表目標調度模式的決策樹模型.在此基礎上，將所構建的決策樹作為新的調度規則，在一組隨機生成的JSP測試案例以及一組不同規模的benchmark調度問題上進行測試.并將測試結果與傳統的優先調度規則以及已有的從JSP問題的優化解中提取的新調度規則進行對比.

3.1 決策樹模型構建

使用隨機生成的4×4規模的JSP案例構建決策樹模型.其中每個工件在不同機器上的加工順序隨機生成，各個加工操作的加工時間服從1～10的離散均勻分布.最終共構建出包括300個訓練實例在內的訓練集用于訓練決策樹模型.所構建的決策樹可以轉化為一組IF-THEN規則，其中部分規則如表5所示.

表5 部分IF-THEN規則示例Tab.5 Partial lists of extracted IF-THEN rules

所構建的決策樹即可用于確定任意2個沖突加工操作的先后加工順序，并作為新的調度規則指導作業車間調度過程.該決策樹模型不僅可以直接用于調度決策過程，還蘊含著許多有關相應調度任務的有價值的規律.Rule1表示如果job1的剩余加工操作數≤job2的剩余加工操作數，且job1的剩余加工時間≤job2的剩余加工時間的0.2倍，且job1與job2的等待時間之差≤2，則可確定應先對job2進行加工.通過進一步分析這些挖掘出的規則可以增加對相關調度過程的理解，有利于進一步的知識發現.

3.2 實驗對比1

首先使用一組隨機生成的6×6規模的測試案例用于測試該決策樹規則的調度性能.在測試案例中，各個加工操作的加工時間服從［5，10］之間的離散均勻分布.6×6的JSP案例同樣被廣泛應用于已有的從優化算法獲得的優化解中提取新的調度規則的方法之中，用于驗證所提取的調度規則的調度性能［9，12，14］，在不考慮截止日期（due date）的情況下，SPT規則是應用最為廣泛的優先調度規則，并已證明能夠在JSP上產生較為理想的調度結果［12］.因此，通過將決策樹調度規則與基于Petri網的分支定界優化算法以及SPT調度規則進行對比，測試其調度性能.

表6展示了3種方法在10個6×6規模的測試案例上獲得的Makespan.基于Petri網的分支定界算法可以生成所有測試案例的優化解，將這些優化解用作對比的基準.由對比結果可知，在8個測試案例中，決策樹調度規則產生了優于SPT規則的調度結果.在案例8上，二者產生了相同的調度結果.僅在案例3上，SPT的調度結果優于決策樹調度規則的調度結果.對比結果說明：決策樹調度規則能夠較好地復現基于Petri網的分支定界算法的優化調度能力，并明顯優于傳統的SPT調度規則.為了進一步驗證決策樹調度規則的泛化能力，

表6 6×6測試案例優化結果對比Tab.6 Comparison results on 6×6 test instances

現構建如下的性能參數指標：式中：Mi（best）表示在第i個測試案例上利用分支定界算法所獲得的 Makespan，Mi（rule）表示由一種調度規則所獲得的Makespan，n表示測試案例數.η（rule）用于表示這種調度規則相對于分支定界算法的優化調度性能度量.測試案例數n取為100，針對決策樹調度規則和SPT規則的性能參數指標η計算結果如表7所示.

表7中，η（DT）和η（SPT）分別表示決策樹調度規則和SPT規則的性能參數指標.η（DT）的取值僅為η（SPT）的一半左右，從而進一步說明：相對于SPT規則，所提取的決策樹調度規則能夠生成更加逼近于最優結果的調度方案.決策樹調度規則的泛化性能得以驗證.

表7 性能參數指標η計算值Tab.7 Computed results of performance indexη___

3.3 實驗對比2

使用一組不同規模的benchmark調度問題進一步測試所提取的決策樹調度規則的調度性能.已有學者提出一些從不同優化算法的優化解中提取新的調度規則的方法.針對最小化Makespan的JSP問題，Weckman等［9］提出的人工神經網絡（neural network，NN）調度器具有優于已有的同類調度規則和傳統優先調度規則的調度性能.該研究利用一個4層感知器神經網絡來提取由遺傳算法得到的優化解中的調度知識.結合著名的Giffler-Thomson（GT）啟發式算法，訓練后的神經網絡可以作為新的調度規則，用于指導作業車間調度過程.因此，將所提取的決策樹調度規則與NN調度規則以及傳統的優先調度規則在benchmark問題上進行對比，以進一步測試其調度性能.

首先使用Fisher等［22］提出的6×6 benchmark問題ft06進行對比實驗.性能參數指標η同樣用于表示不同調度規則相對于分支定界算法的優化調度性能（n=1）.Weckman等［9］在該benchmark問題上將NN調度器與4種常用的優先調度規則進行對比，將所提取的決策樹規則與這四種優先調度規則以及NN調度規則進行對比，結果如表8所示.對比結果顯示：決策樹調度規則能夠生成與NN調度器相同的調度結果.決策樹調度規則與NN調度器的η值遠小于其它優先調度規則的η值，說明2種調度規則的調度性能均優于傳統的優先調度規則.

將一組規模更大的benchmark問題用于對比決策樹調度規則與NN調度器以及傳統調度規則的優化調度性能，并驗證決策樹規則在不同規模問題上的可擴展性.這些benchmark問題包括ft10［22］、la24［23］、la36［23］、abz7［24］和 yn1［25］.這 些 benchmark問題取自不同的基準問題集，因此具有較好的代表性.Weckman等［9］同樣應用這組問題集驗證NN調度器的調度性能.

表8 6×6 benchmark問題上的優化結果對比Tab.8 Comparison results on 6×6 benchmark problem

對比結果如表9所示.結果顯示：決策樹調度規則在所有benchmark問題上的調度結果均優于NN調度器和SPT規則.決策樹調度規則的η值（19.42%）遠小于 NN 調度器（40.39%）及 SPT（72.64%）的η值.對比結果說明：決策樹調度規則的優化調度性能優于其他規則的性能.決策樹調度規則能夠產生最接近已知最優解的調度結果，其在不同規模上的可擴展性也得到了驗證.

表9 不同規模基準問題上的結果對比Tab.9 Comparison results on different sized benchmark________problems

相對于傳統的優化算法（如：分支定界法和遺傳算法），所提取的調度規則雖然無法用于求取最優解或近似最優解，但是極小的計算量和極少的計算時間就能夠獲得較優的調度結果.所提取的調度規則可以較好地代替傳統優先調度規則.

4 結 語

本文利用時間Petri網絡對作業車間調度問題進行建模，提出一種基于Petri網建模的分支定界算法，用于生成優化調度方案.在此基礎上，提出一種基于決策樹分類方法的作業車間調度規則挖掘方法，用于挖掘隱藏在基于Petri網模型表達的優化調度方案中的調度模式.所提取的調度模式通過決策樹模型加以表達，能夠預測任意2個沖突加工操作的先后加工順序.該調度模式可作為新的調度規則，用以指導作業車間調度過程.在測試案例和benchmark問題上的實驗結果表明：所提取的決策樹規則優于已有的同類規則和傳統的優先調度規則.

由實驗結果可知，構建的規則所生成的調度結果相對于已知最優解仍存在差距.因此，在今后的工作中，需要繼續研究使用新的分類技術進行目標調度模式的挖掘.此外，Petri網同樣適用于其它類型調度問題的建模和優化過程.

（

）:

［1］MEERAN S，MORSHED M S.A hybrid genetic tabu search algorithm for solving job shop scheduling problems：a case study［J］.Journal of Intelligent Manufacturing，2012，23（4）：1063- 1078.

［2］BRUCKER P，JURISCH B，SIEVERS B.A branch and bound algorithm for the job-shop scheduling problem ［J］.Discrete applied mathematics，1994，49（1）：107- 127.

［3］方水良，姚嫣菲，趙詩奎.柔性車間調度的改進遺傳算法［J］.浙江大學學報：工學版，2012，46（4）：629- 635.FANG Shui-liang，YAO Yan-fei，ZHAO Shi-kui.Improved genetic algorithm for flexible job shop scheduling［J］.Journal of Zhejiang University：Engineering Science，2012，46（4）：629- 635.

［4］GONCALVES J F，DE MAGALHAES MENDES J J，Resende M G C.A hybrid genetic algorithm for the job shop scheduling problem［J］.European Journal of Operational Research，2005，167（1）：77- 95.

［5］王萬良，宋毅，吳啟迪.求解作業車間調度問題的雙倍體遺傳算法與軟件實現［J］.計算機集成制造系統，2004，10（1）：65- 69.WANG Wan-liang，SONG Yi，WU Qi-di.Double Chromosomes Genetic Algorithm and Its Realization for Jobshop Scheduling Problems ［J］.Computer Integrated Manufacturing Systems，2004，10（1）：65- 69.

［6］VAN LAARHOVEN P J M，AARTS E H L，Lenstra J K.Job shop scheduling by simulated annealing［J］.Operations Research，1992，40（1）：113- 125.

［7］ZHANG R，WU C.A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective［J］.Computers and Operations Research，2011，38（5）：854- 867.

［8］NOWICKI E，SMUTNICKI C.An advanced tabu search algorithm for the job shop problem ［J］.Journal of Scheduling，2005，8（2）：145- 159.

［9］WECKMAN G R，GANDURI C V，KOONCE D A.A neural network job-shop scheduler［J］.Journal of Intelligent Manufacturing，2008，19（2）：191- 201.

［10］吳啟迪，喬非，李莉，等.基于數據的復雜制造過程調度［J］.自動化學報，2009，35（6）：807- 813.WU Qi-di，QIAO Fei，LI Li，et al.Data-based Scheduling for Complex Manufacturing Processes［J］.Acta Automatica Sinica，2009，35（6）：807- 813.

［11］LI L，SUN Z J，NI J C，et al.Data-based scheduling framework and adaptive dispatching rule of complex manufacturing systems［J］.The International Journal of Advanced Manufacturing Technology，2013，66（9-12）：1891- 1905.

［12］KOONCE D A，TSAI S C.Using data mining to find patterns in genetic algorithm solutions to a job shop schedule ［J］.Computers and Industrial Engineering，2000，38（3）：361- 374.

［13］KUMAR S，RAO C S P.Application of ant colony，genetic algorithm and data mining-based techniques for scheduling［J］.Robotics and Computer-Integrated Manufacturing，2009，25（6）：901- 908.

［14］SHAHZAD A，MEBARKI N.Data mining based job dispatching using hybrid simulation-optimization approach for shop scheduling problem ［J］.Engineering Applications of Artificial Intelligence，2012，25（6）：1173- 1181.

［15］TUNCEL G，BAYHAN G M.Applications of Petri nets in production scheduling：a review［J］.The International Journal of Advanced Manufacturing Technology，2007，34（7／8）：762- 773.

［16］GHAELI M，BAHRI P A，LEE P，et al.Petri-net based formulation and algorithm for short-term scheduling of batch plants［J］.Computers and Chemical Engineering，2005，29（2）：249- 259.

［17］LI X，OLAFSSON S.Discovering dispatching rules using data mining ［J］.Journal of Scheduling，2005，8（6）：515- 527.

［18］OLAFSSON S，Li X.Learning effective new single machine dispatching rules from optimal scheduling data［J］.International Journal of Production Economics，2010，128（1）：118- 126.

［19］HAN J，KAMBER M.Data mining：concepts and techniques［M］.2th ed.San Francisco：Morgan Kaufmann Publishers，2006：291- 310.

［20］SHIUE Y R，GUH R S.The optimization of attribute selection in decision tree-based production control systems［J］.The international journal of advanced manufacturing technology，2006，28（7／8）：737- 746.

［21］QUINLAN J R.C4.5 programs for machine learning［M］.San Francisco：Morgan Kaufmann Publishers，1993：17- 26.

［22］FISHER H，THOMPSON G L.Probabilistic learning combinations of local job-shop scheduling rules ［J］.Industrial scheduling，1963，3：225- 251.

［23］LAWRENCE S.Resource constrained project scheduling：an experimental investigation of heuristic scheduling techniques（supplement）［J］.Graduate School of Industrial Administration，Carnegie-Mellon University，Pittsburgh，Pennsylvania，1984.

［24］ADAMS J，BALAS E，ZAWACK D.The shifting bottleneck procedure for job shop scheduling ［J］.Management Science，1988，34（3）：391- 401.

［25］YAMADA T，NAKANO R.A Genetic algorithm applicable to large-scale job-shop problems［C］∥International Conference on Parallel Problem Soluing frorn Nature（PPSN）.Amsterdam：Elsevier，1992：281- 290.