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

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

生產(chǎn)調(diào)度是現(xiàn)代工業(yè)先進(jìn)制造和管理的核心技術(shù).作業(yè)車間調(diào)度問題（job shop scheduling problem，JSP），作為研究最為廣泛的確定性生產(chǎn)調(diào)度優(yōu)化問題［1］，受到了學(xué)者們的廣泛關(guān)注.JSP是許多實(shí)際工業(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)度問題的有價(jià)值的規(guī)律或知識(shí).但這些方法的實(shí)現(xiàn)過程復(fù)雜，需要進(jìn)行大量的參數(shù)整定工作和較長的計(jì)算時(shí)間，無法適應(yīng)作業(yè)車間實(shí)時(shí)變化的作業(yè)狀態(tài).這些方法雖然能夠求取最優(yōu)解或是近似最優(yōu)解，但卻無法解釋優(yōu)化解是如何生成的，或是無法說明這些優(yōu)化解的共同特性［9］.相反，優(yōu)先調(diào)度規(guī)則（priority dispatching rules，PDR）給出了一種基于知識(shí)的調(diào)度過程決策方法.PDR往往由長期積累獲得的有關(guān)調(diào)度問題的專家知識(shí)抽象而來.利用PDR指導(dǎo)生產(chǎn)調(diào)度的過程容易實(shí)現(xiàn)，且計(jì)算簡單，并能夠適應(yīng)作業(yè)車間的實(shí)時(shí)變化.但傳統(tǒng)的優(yōu)先調(diào)度規(guī)則往往性能較差，無法產(chǎn)生較優(yōu)的結(jié)果.一種新的研究思路是從利用分支定界法或是自適應(yīng)搜索算法所獲得的優(yōu)化解中挖掘有價(jià)值的規(guī)律或知識(shí)，用以構(gòu)造新的調(diào)度規(guī)則.新調(diào)度規(guī)則既具有傳統(tǒng)PDR的優(yōu)點(diǎn)，又能夠較好地保留這些優(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］利用遺傳算法求解一個(gè)6×6基準(zhǔn)問題，并應(yīng)用一種面向?qū)傩缘臍w納算法挖掘優(yōu)化解中的隱含規(guī)律.所生成的規(guī)則集能較好地逼近遺傳算法的調(diào)度性能，優(yōu)于傳統(tǒng)的最短時(shí)間規(guī)則（shortest processing time，SPT）.Weckman等［9］同樣采用遺傳算法求解JSP，并運(yùn)用人工神經(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進(jìn)行建模，并給出一種分支定界算法用于搜尋優(yōu)化調(diào)度方案.在此基礎(chǔ)上，提出一種基于決策樹（decision tree，DT）分類技術(shù)的調(diào)度知識(shí)挖掘方法，用于挖掘隱藏在優(yōu)化調(diào)度方案中的調(diào)度知識(shí).所提取的調(diào)度知識(shí)可以直接作為新的調(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)需要考慮時(shí)間屬性，經(jīng)典Petri網(wǎng)同樣可以描述時(shí)間信息.時(shí)間Petri網(wǎng)根據(jù)時(shí)間屬性所處的位置分為兩類：時(shí)間屬性位于庫所（timed place Petri net，TPPN）；時(shí)間屬性位于變遷（timed transition Petri net，TTPN）.本文采用TPPN對JSP進(jìn)行建模.TPPN可以表達(dá)如下：

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

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

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

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

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

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

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

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

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

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

狀態(tài)矩陣M0被分解為3個(gè)子矩陣，分別代表相應(yīng)的加工工件和機(jī)器的當(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)的分支定界算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用隨機(jī)生成的4×4規(guī)模的JSP案例構(gòu)建決策樹模型.其中每個(gè)工件在不同機(jī)器上的加工順序隨機(jī)生成，各個(gè)加工操作的加工時(shí)間服從1～10的離散均勻分布.最終共構(gòu)建出包括300個(gè)訓(xùn)練實(shí)例在內(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個(gè)沖突加工操作的先后加工順序，并作為新的調(diào)度規(guī)則指導(dǎo)作業(yè)車間調(diào)度過程.該決策樹模型不僅可以直接用于調(diào)度決策過程，還蘊(yùn)含著許多有關(guān)相應(yīng)調(diào)度任務(wù)的有價(jià)值的規(guī)律.Rule1表示如果job1的剩余加工操作數(shù)≤job2的剩余加工操作數(shù)，且job1的剩余加工時(shí)間≤job2的剩余加工時(shí)間的0.2倍，且job1與job2的等待時(shí)間之差≤2，則可確定應(yīng)先對job2進(jìn)行加工.通過進(jìn)一步分析這些挖掘出的規(guī)則可以增加對相關(guān)調(diào)度過程的理解，有利于進(jìn)一步的知識(shí)發(fā)現(xiàn).

3.2 實(shí)驗(yàn)對比1

首先使用一組隨機(jī)生成的6×6規(guī)模的測試案例用于測試該決策樹規(guī)則的調(diào)度性能.在測試案例中，各個(gè)加工操作的加工時(shí)間服從［5，10］之間的離散均勻分布.6×6的JSP案例同樣被廣泛應(yīng)用于已有的從優(yōu)化算法獲得的優(yōu)化解中提取新的調(diào)度規(guī)則的方法之中，用于驗(yàn)證所提取的調(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ī)則進(jìn)行對比，測試其調(diào)度性能.

表6展示了3種方法在10個(gè)6×6規(guī)模的測試案例上獲得的Makespan.基于Petri網(wǎng)的分支定界算法可以生成所有測試案例的優(yōu)化解，將這些優(yōu)化解用作對比的基準(zhǔn).由對比結(jié)果可知，在8個(gè)測試案例中，決策樹調(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ī)則.為了進(jìn)一步驗(yàn)證決策樹調(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個(gè)測試案例上利用分支定界算法所獲得的 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)η計(jì)算結(jié)果如表7所示.

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

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

3.3 實(shí)驗(yàn)對比2

使用一組不同規(guī)模的benchmark調(diào)度問題進(jìn)一步測試所提取的決策樹調(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)度性能.該研究利用一個(gè)4層感知器神經(jīng)網(wǎng)絡(luò)來提取由遺傳算法得到的優(yōu)化解中的調(diào)度知識(shí).結(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問題上進(jìn)行對比，以進(jìn)一步測試其調(diào)度性能.

首先使用Fisher等［22］提出的6×6 benchmark問題ft06進(jìn)行對比實(shí)驗(yàn).性能參數(shù)指標(biāo)η同樣用于表示不同調(diào)度規(guī)則相對于分支定界算法的優(yōu)化調(diào)度性能（n=1）.Weckman等［9］在該benchmark問題上將NN調(diào)度器與4種常用的優(yōu)先調(diào)度規(guī)則進(jìn)行對比，將所提取的決策樹規(guī)則與這四種優(yōu)先調(diào)度規(guī)則以及NN調(diào)度規(guī)則進(jìn)行對比，結(jié)果如表8所示.對比結(jié)果顯示：決策樹調(diào)度規(guī)則能夠生成與NN調(diào)度器相同的調(diào)度結(jié)果.決策樹調(diào)度規(guī)則與NN調(diào)度器的η值遠(yuǎn)小于其它優(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)度性能，并驗(yàn)證決策樹規(guī)則在不同規(guī)模問題上的可擴(kuò)展性.這些benchmark問題包括ft10［22］、la24［23］、la36［23］、abz7［24］和 yn1［25］.這 些 benchmark問題取自不同的基準(zhǔn)問題集，因此具有較好的代表性.Weckman等［9］同樣應(yīng)用這組問題集驗(yàn)證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%）遠(yuǎn)小于 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ī)模上的可擴(kuò)展性也得到了驗(yàn)證.

表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)解，但是極小的計(jì)算量和極少的計(jì)算時(shí)間就能夠獲得較優(yōu)的調(diào)度結(jié)果.所提取的調(diào)度規(guī)則可以較好地代替?zhèn)鹘y(tǒng)優(yōu)先調(diào)度規(guī)則.

4 結(jié) 語

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

由實(shí)驗(yàn)結(jié)果可知，構(gòu)建的規(guī)則所生成的調(diào)度結(jié)果相對于已知最優(yōu)解仍存在差距.因此，在今后的工作中，需要繼續(xù)研究使用新的分類技術(shù)進(jìn)行目標(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ìn)遺傳算法［J］.浙江大學(xué)學(xué)報(bào)：工學(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)度問題的雙倍體遺傳算法與軟件實(shí)現(xiàn)［J］.計(jì)算機(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］.自動(dòng)化學(xué)報(bào)，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.