作業(yè)車間調(diào)度規(guī)則的挖掘方法研究

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

（工業(yè)控制國家重點實驗室，浙江大學(xué) 智能系統(tǒng)與控制研究所，浙江 杭州310027）

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

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

利用由傳統(tǒng)優(yōu)化算法所獲得的調(diào)度問題優(yōu)化解構(gòu)造新的調(diào)度規(guī)則是一種新興的研究思路［10-11］.Koonce等［12］利用遺傳算法求解一個6×6基準(zhǔn)問題，并應(yīng)用一種面向?qū)傩缘臍w納算法挖掘優(yōu)化解中的隱含規(guī)律.所生成的規(guī)則集能較好地逼近遺傳算法的調(diào)度性能，優(yōu)于傳統(tǒng)的最短時間規(guī)則（shortest processing time，SPT）.Weckman等［9］同樣采用遺傳算法求解JSP，并運用人工神經(jīng)網(wǎng)絡(luò)（artificial neutral network，ANN）從優(yōu)化解中學(xué)習(xí)新的調(diào)度規(guī)則.Kumar等［13-14］分別將蟻群算法和禁忌搜索算法應(yīng)用于生產(chǎn)調(diào)度問題，并利用這兩種自適應(yīng)搜索算法生成的優(yōu)化解構(gòu)造新的調(diào)度規(guī)則.

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

1 基于Petri網(wǎng)的作業(yè)車間調(diào)度問題建模及優(yōu)化

1.1 經(jīng)典Petri網(wǎng)絡(luò)

經(jīng)典的Petri網(wǎng)絡(luò)可以表示為4元組

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

其中γ表示當(dāng)前狀態(tài)下各個庫所的時間參數(shù)的集合.

1.2 作業(yè)車間調(diào)度問題建模

近年來，基于Petri網(wǎng)的生產(chǎn)調(diào)度問題研究取得了廣泛的關(guān)注.Petri網(wǎng)模型可以簡潔詳細地表達出調(diào)度過程的所有狀態(tài)［15］，并很好地表達生產(chǎn)調(diào)度過程中的動態(tài)行為特性.結(jié)合其他的優(yōu)化方法，Petri網(wǎng)建模即可用于求解生產(chǎn)調(diào)度問題.通過這種方式，Petri網(wǎng)的狀態(tài)表達能力可以與傳統(tǒng)優(yōu)化方法的優(yōu)化求解能力有效地結(jié)合起來，并為進一步調(diào)度知識挖掘提供有價值的調(diào)度數(shù)據(jù)，因此，Petri網(wǎng)建模十分有利于生產(chǎn)調(diào)度過程中的知識發(fā)現(xiàn).

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

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

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

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

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

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

以表1所示的一個2×2的JSP為例，其中每個數(shù)據(jù)表格中的第一個數(shù)據(jù)表示加工操作所對應(yīng)的機器，第二個數(shù)據(jù)表示加工操作的加工時間.其TPPN模型如圖1所示.圖1所示的調(diào)度過程處于初始狀態(tài)，該初始狀態(tài)可以表示為

狀態(tài)矩陣M0被分解為3個子矩陣，分別代表相應(yīng)的加工工件和機器的當(dāng)前狀態(tài).

表1 2×2作業(yè)車間調(diào)度問題示例Tab.1 Example of 2×2 job shop scheduling problem

圖1 2×2作業(yè)車間調(diào)度問題TPPN模型Fig.1 TPPN model of the 2×2 job shop scheduling problem

1.3 基于Petri網(wǎng)的分支定界算法

在改進一種基于Petri網(wǎng)的啟發(fā)式搜索算法［16］的基礎(chǔ)上，針對最小化最大完工時間（Makespan）這一性能指標(biāo)，提出一種基于Petri網(wǎng)的分支定界算法用于求解JSP.該算法可以用于求取JSP的優(yōu)化解.所求取的優(yōu)化調(diào)度方案即可以用于進一步的調(diào)度知識發(fā)現(xiàn).

該分支定界算法是從Petri網(wǎng)模型的初始狀態(tài)開始，通過不斷觸發(fā)允許的變遷來構(gòu)建可達樹.可達樹一個節(jié)點對應(yīng)于TPPN模型的一個狀態(tài).每個節(jié)點向下的不同分支代表觸發(fā)不同的變遷.可達樹的所有葉節(jié)點均代表TPPN的終止?fàn)顟B(tài)，即代表調(diào)度加工任務(wù)的結(jié)束.因此，每一條從可達樹根節(jié)點到葉節(jié)點的路徑均為對應(yīng)JSP問題的一個可行解.

每個可行解由從起始狀態(tài)到終止?fàn)顟B(tài)的狀態(tài)序列組成，代表作業(yè)車間的動態(tài)調(diào)度過程.對于每個非葉結(jié)點，其向下可能通過多條路徑到達葉節(jié)點，即對應(yīng)著多個可行解.根節(jié)點對應(yīng)著整個可行解空間.分支定界算法通過不斷擴展可達樹來搜索最優(yōu)解，其分支策略即對應(yīng)于可達樹的分支策略.

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

f（Mk）為Mk對應(yīng)的可行解集合的Makespan下界.

g（Mk）為當(dāng)前狀態(tài)Mk的生成時間即當(dāng)前時刻.

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

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

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

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

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

利用這種新狀態(tài)生成策略可以同時觸發(fā)多個變遷，從而有效減少可達樹的節(jié)點數(shù)，縮減可達樹的規(guī)模，進一步提高計算效率.

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

1）獲取當(dāng)前狀態(tài)Mk.

2）計算后續(xù)調(diào)度生產(chǎn)時間下限h（Mk），結(jié)合當(dāng)前時間g（Mk），計算 Makespan下界f（Mk）.若f（Mk）大于或等于當(dāng)前的最小Makespan，程序返回.

3）若Mk等于終止?fàn)顟B(tài)，轉(zhuǎn)到步驟5）.

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

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

2 作業(yè)車間調(diào)度規(guī)則挖掘

2.1 目標(biāo)調(diào)度模式定義

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

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

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

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

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

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

3）決策樹模型的構(gòu)建不需要任何領(lǐng)域知識，且無需進行復(fù)雜的參數(shù)整定，更具有實用性.

2.2 數(shù)據(jù)收集

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

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

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

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

表2 4×4作業(yè)車間調(diào)度問題示例__Tab.2 Example of 4×4 job shop scheduling problem_

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

2.3 構(gòu)造輸入屬性集

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

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

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

已有的用于描述一個加工操作的屬性包括加工時間，等待時間及其在所對應(yīng)的加工工件中的加工序號.此外，一些已有的有關(guān)時間或加工機器的信息可以用于構(gòu)造描述沖突時調(diào)度環(huán)境信息的屬性.根據(jù)這些已有的屬性，即可以構(gòu)造有關(guān)2個沖突加工操作的對比屬性和相應(yīng)的調(diào)度環(huán)境屬性.

對于面向?qū)傩缘膶W(xué)習(xí)算法，目前尚無有效的方法用于最優(yōu)屬性子集的選擇［20］.采用一種后向搜索（backward search）的啟發(fā)式算法確定一組較優(yōu)的屬性子集.后向搜索方法從整個屬性集開始，每次從該屬性集中選擇剔除一個屬性，使得剔除該屬性后分類評價函數(shù)達到最優(yōu)，直到滿足終止條件為止.

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

表3 參數(shù)符號定義Tab.3 Definition of notations____________

2.4 分類模型構(gòu)建

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

圖3 目標(biāo)調(diào)度模式的決策樹模型Fig.3 Decision tree model of the target scheduling pattern

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

3 實驗分析

為了驗證所提出的作業(yè)車間調(diào)度規(guī)則挖掘方法的可行性，利用一組隨機生成的JSP案例構(gòu)建訓(xùn)練實例集，并進一步利用所構(gòu)建的訓(xùn)練實例集訓(xùn)練獲得代表目標(biāo)調(diào)度模式的決策樹模型.在此基礎(chǔ)上，將所構(gòu)建的決策樹作為新的調(diào)度規(guī)則，在一組隨機生成的JSP測試案例以及一組不同規(guī)模的benchmark調(diào)度問題上進行測試.并將測試結(jié)果與傳統(tǒng)的優(yōu)先調(diào)度規(guī)則以及已有的從JSP問題的優(yōu)化解中提取的新調(diào)度規(guī)則進行對比.

3.1 決策樹模型構(gòu)建

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

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

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

3.2 實驗對比1

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

表6展示了3種方法在10個6×6規(guī)模的測試案例上獲得的Makespan.基于Petri網(wǎng)的分支定界算法可以生成所有測試案例的優(yōu)化解，將這些優(yōu)化解用作對比的基準(zhǔn).由對比結(jié)果可知，在8個測試案例中，決策樹調(diào)度規(guī)則產(chǎn)生了優(yōu)于SPT規(guī)則的調(diào)度結(jié)果.在案例8上，二者產(chǎn)生了相同的調(diào)度結(jié)果.僅在案例3上，SPT的調(diào)度結(jié)果優(yōu)于決策樹調(diào)度規(guī)則的調(diào)度結(jié)果.對比結(jié)果說明：決策樹調(diào)度規(guī)則能夠較好地復(fù)現(xiàn)基于Petri網(wǎng)的分支定界算法的優(yōu)化調(diào)度能力，并明顯優(yōu)于傳統(tǒng)的SPT調(diào)度規(guī)則.為了進一步驗證決策樹調(diào)度規(guī)則的泛化能力，

表6 6×6測試案例優(yōu)化結(jié)果對比Tab.6 Comparison results on 6×6 test instances

現(xiàn)構(gòu)建如下的性能參數(shù)指標(biāo)：式中：Mi（best）表示在第i個測試案例上利用分支定界算法所獲得的 Makespan，Mi（rule）表示由一種調(diào)度規(guī)則所獲得的Makespan，n表示測試案例數(shù).η（rule）用于表示這種調(diào)度規(guī)則相對于分支定界算法的優(yōu)化調(diào)度性能度量.測試案例數(shù)n取為100，針對決策樹調(diào)度規(guī)則和SPT規(guī)則的性能參數(shù)指標(biāo)η計算結(jié)果如表7所示.

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

表7 性能參數(shù)指標(biāo)η計算值Tab.7 Computed results of performance indexη___

3.3 實驗對比2

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

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

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

表8 6×6 benchmark問題上的優(yōu)化結(jié)果對比Tab.8 Comparison results on 6×6 benchmark problem

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

表9 不同規(guī)?；鶞?zhǔn)問題上的結(jié)果對比Tab.9 Comparison results on different sized benchmark________problems

相對于傳統(tǒng)的優(yōu)化算法（如：分支定界法和遺傳算法），所提取的調(diào)度規(guī)則雖然無法用于求取最優(yōu)解或近似最優(yōu)解，但是極小的計算量和極少的計算時間就能夠獲得較優(yōu)的調(diào)度結(jié)果.所提取的調(diào)度規(guī)則可以較好地代替?zhèn)鹘y(tǒng)優(yōu)先調(diào)度規(guī)則.

4 結(jié) 語

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

由實驗結(jié)果可知，構(gòu)建的規(guī)則所生成的調(diào)度結(jié)果相對于已知最優(yōu)解仍存在差距.因此，在今后的工作中，需要繼續(xù)研究使用新的分類技術(shù)進行目標(biāo)調(diào)度模式的挖掘.此外，Petri網(wǎng)同樣適用于其它類型調(diào)度問題的建模和優(yōu)化過程.

（

）:

［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］方水良，姚嫣菲，趙詩奎.柔性車間調(diào)度的改進遺傳算法［J］.浙江大學(xué)學(xué)報：工學(xué)版，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］王萬良，宋毅，吳啟迪.求解作業(yè)車間調(diào)度問題的雙倍體遺傳算法與軟件實現(xiàn)［J］.計算機集成制造系統(tǒng)，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］吳啟迪，喬非，李莉，等.基于數(shù)據(jù)的復(fù)雜制造過程調(diào)度［J］.自動化學(xué)報，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.