數據驅動的Job Shop生產調度知識挖掘及優化

王家海，陳 煜

WANG Jiahai,CHEN Yu

同濟大學 機械與能源工程學院，上海 201804

School of Mechanical Engineering,Tongji University,Shanghai 201804,China

1 引言

海量的生產數據中蘊藏著豐富的生產調度知識，經過挖掘可以得出有價值的規律，有助于生產調度領域知識的管理和決策優化，加強調度解決方案的可行性，在這種迫切需求下，如何分析和處理調度數據成為這一領域的關鍵問題。

針對企業生產車間的優化調度，通過建立多目標優化模型是目前有效的解決方法。面向不同環境的Job Shop調度問題的研究也有很多的成果[1-3]，但仍有以下問題值得關注：（1）模型計算精度低，偏差大，給具體實施帶來一定困難；（2）求解效率低下，運行時間較長；（3）缺乏知識指導，在調度優化目標和規則的選取上更加局限，無法綜合考慮調度性能指標。因此研究如何從調度算法結果中發掘調度知識，形成新的調度規則并應用于調度求解的進一步優化是十分必要的。知識化制造系統[4]是一種自適應、自學習、自進化、自重構、自培訓和自維護為主要特征，強調對制造系統所蘊含的生產知識進行挖掘、處理和利用，以時間、量、成本、服務和環境為主要優化目標的深度智能制造系統。基于知識的生產調度方法也逐漸成為研究熱點[5-6]，但是目前基于知識的調度在知識獲取方面仍存在瓶頸，所以無法直接應用于生產現場的調度。基于本體的知識表示[7-9]在傳統的知識表示方法上做出改進，在知識工程領域的應用日益廣泛。秦大力[10]等人為了提高機械故障診斷的準確性與可靠性，引入了診斷維護知識的語義表示方法；鄭永前[11]等通過定義白車身制造工藝的本體，建立了關系本體模型并提出了基于本體知識庫的整體框架。

針對上述問題，本文提出一種海量數據環境下基于知識挖掘的作業車間調度多目標優化方法。在獲取領域內豐富的調度知識后進行基于本體的知識表示，從而得到調度領域的知識庫，為后續數據處理提供規范的數據結構。通過數據挖掘的方法，對調度數據進行采集和處理，挖掘隱藏在數據中的調度規則，在此基礎上結合啟發式智能調度算法，運用合理的調度規則和調度知識，給出了更加有效的搜尋優化調度方案。

2 基于本體的調度知識表示

調度知識的表示是實現生產調度知識挖掘的關鍵。本體的優勢在于知識表示能力強，實用性強。建立調度領域本體的目的是將領域的知識進行抽象，將實體間的關系描述出來。其中，領域知識一般被分為三種類型：描述性知識、過程性知識和控制性知識。在調度問題中，將包含概念與定義、操作和行為的描述性和過程性知識放在領域知識庫中，調度規則庫則包含決策和判斷等控制性知識。將本體所構建的知識庫和規則庫共同構成調度的知識來源，幫助決策者發現調度實例中隱含的知識，彌補傳統調度的不足。

2.1 調度領域知識本體建模

采取專家訪問和實地調研等方式對領域內信息進行詳細地分析，通過本體對領域內知識進行語義標注，在語義這個載體上，梳理出調度領域中知識間的基本關系，便于調度知識被調度相關人員理解并組合使用。可以用三元組C=＜D,W,K＞表示對本體進行概念的形式化，其中C表示領域中元素的集合，W表示領域中相關事務的狀態集，K表示領域空間＜D,W＞上的概念關系集。

根據Perez等提出的建模元語包括類或概念、關系、函數、公理、實例，從領域中選取的核心概念有：任務、指標、目標、約束、規則、資源和解決方案。概念本體的屬性有：分解、滿足、指導、實現、分配和執行，其他關系有subclass-of、has、attribute-of等。

JSSP（Job Shop Scheduling Problem）調度問題的領域本體可以用一個六元組進行定義：

式中，C表示概念集，AC表示屬性集，R表示概念關系集，AR表示關系的屬性集，H表示概念的從屬集，X表示公理集。

用選取的核心概念和明確定義的屬性來描述的調度領域的知識本體如圖1所示。Job Shop生產調度問題以任務為核心，將任務分解為以指標為表征的多個子任務及活動，在滿足約束條件下，用調度規則指導生成解決方案以實現一定的多目標優化，再根據解決方案來分配生產資源，使解決方案得以執行。

2.2 調度領域概念本體及屬性表示

本體關系圖可以直接形象地表示調度本體模型，但是為了便于研究知識本體的性質，需要定義各個核心概念、基本屬性及屬性關系。調度領域本體可以概念化為：

圖1 生產調度領域本體關系模型

式中，N表示概念的名稱；P表示概念的屬性；ρn表示概念關系。

生產調度任務即完成那個工件的加工任務，工件集的子任務集包含對應的工序，任務的概念本體可以表示為：

式中，Task_Details包括任務的名稱、類型（工件集/工序集）、目標數量等具體信息；Task_Attribute表示屬性分解，工件集分解后形成工序集，工序集分解后構成最小粒度的工步；Task_Relation表示subclass-of關系，即活動是工序的子集，工序是工件的子集。

實際的生產調度問題的指標有很多，例如時間指標、生產成本指標、質量指標、設備OEE指標等。生產調度的目標則是對指標的一個評價度量值，在解決多目標優化問題時，還需要考慮不同指標間的權重平衡關系。目標本體及其屬性指標本體定義為：

式中，Target_Set表示各指標的集合；Target_Attribute表示沖突、包含、權重系數等屬性；Target_Functions表示了多目標之間的關系，即表達了指標的權重平衡關系的目標函數。

調度規則即在目標和指標的準則下，根據約束條件給生產資源分派加工任務，主要包括基于加工周期的規則、基于交貨期的規則、基于車間狀況的規則等。將調度規則概念化定義為：

式中，Rule_Name表示調度規則的名稱或者唯一標識；Rule_Attribute表示調度規則的內容即根據工序的剩余加工時間、任務的優先級、交貨期等值的比較來確定先執行哪一道工序；Rule_Relation則表示各個調度規則間的關系如包含、組合、互斥等。

生產資源是調度問題中時間和成本指標的保證，資源的靜態信息即概況數據，動態數據則表示具體生產過程中的狀態信息。將調度領域中的資源本體看成一個領域本體，包括的核心概念有人、機器以及物料。各核心概念的形式化定義由具體的資源類型決定。用五元組定義調度資源本體概念：JSSP_ResourceOntology=＜C（人、機器、物料），AC（Person_Attribute，Machine_Attribute，Materiel_Attribute），R（屬性關系，層次關系，實例關系等），H（平行調度），X（匹配約束，互斥約束）＞。

3 基于決策樹的調度規則挖掘

3.1 調度知識挖掘框架

針對傳統的調度數據并不能直接用于優化調度的問題，數據驅動的生產調度優化重點在于如何發揮數據與知識結合的重要作用。如圖2所示的是調度知識挖掘框架對采集的樣本數據進行數據轉換和預處理，引入經典學習算法支持向量機對樣本進行預處理和選擇，并結合決策樹學習算法對調度數據進行分析和歸納，將歸納得到的規則放入規則庫，進而強化知識庫，并在各個決策點實現知識驅動的自動化決策，得到更為優化的結果。

圖2 基于數據挖掘的調度知識挖掘框架

3.2 集成支持向量機的決策樹學習算法

對調度數據集的挖掘研究領域廣闊，傳統的可視化、描述統計法和機器學習技術都可以應用于發現調度數據集中的隱性和顯性知識[12-13]。選取決策樹方法在調度數據集中提取調度規則知識，利用信息論對數據屬性進行取值，不同的屬性取值形成不同的決策樹分支，自上而下進行遍歷循環，遞歸構建決策樹和剪枝，把決策樹轉化成為規則，獲得有效知識。

由于決策樹分類的性能在很大程度上取決于樣本的好壞，因此在這里引入集成的概念，在面對海量的原始數據時，通過有限個支持向量機對數據進行分類學習，得到一個由有限個判別函數組合而成的判別函數。再從原始數據中隨機選取一組屬性特征向量，用判別函數進行類別判斷，構建一個新的樣本集，和原始數據集形成最終的訓練數據集，在這個新的訓練數據集上進行決策樹學習，進而得到決策樹規則。

3.3 基于CART算法的決策樹規則提取

（1）CART算法

屬性是決策樹的分支點，其選擇策略成為決策樹構建的核心所在。選擇的基本準則是屬性的不純度最小，故常啟發式地定義規則為使分類后的子節點的純度最大。屬性選擇規則最常見的有基于熵的信息增益和基尼不純度指數（Gini Impurity Index）。CART算法根據基尼純度最小化分類準則確定各節點的屬性。基尼不純度指數定義如下所示。

如果一個調度數據集D有k個類，其基尼指數為：

式中，D表示調度數據集，f(k|D)表示k類在數據集D中的概率。節點屬性所屬類別概率相同時取到最大值1-，最小值0表示節點處只有一個類別。

決策樹的父節點選取樣本t，若CART選擇屬性x分為兩個子節點，對應集合為tv1和tv2，分裂后的基尼不純度指數為：

其中，||·表示對應集合的記錄數量，vi表示屬性x的不同取值。

在每一個節點計算屬性的基尼指數，選出不純度減少量最大的屬性。不純度減少量的定義如下：

式中，V是屬性相應的所有屬性值的集合，fparent,v表示在父節點屬性值v滿足的實例占整個數據集的概率，G(child|v)表示子節點屬性值滿足v的基尼不純度指數。

算法的具體步驟如下：

步驟1對調度數據集進行轉換和預處理，確定屬性、屬性值及類別值；

步驟2從樣本集中選出包括全部類的訓練集以及測試集；

步驟3父節點對應樣本集合t，將基尼不純度最小的屬性作為分支的根節點；

步驟4每個子集中選擇不純度減少量最大的屬性作為分支的根節點，遞歸建樹，若子集中只含有一個類別時，結束分裂；

步驟5用測試集判定步驟4中決策樹的誤差，若存在過度擬合則采用后剪枝，修整決策樹。

（2）實例分析

以6×6規模的JSSP調度問題為例，從優化算法得到的海量的原始調度數據中選取300個數據構成調度數據集，其中250個調度數據用于訓練支持向量機分類器后，從中隨機選取100個特征向量進行類別判定構成新的100個樣本，和另150個未判別的樣本構成250個訓練樣本，剩下的50個用于測試決策樹。CART算法的前提的是數據的離散屬性，因此需要通過離散化處理樣本中的連續型數據。針對6×6的調度問題，以滿足交貨期和總通過時間最短為目標，選擇與該目標相關的指標為屬性作為決策樹的輸入屬性，采用每個樣本對應指標的數據作為屬性值，同一臺機床上等待被加工的工件的排序情況作為類別，可以用數值型數據來表示排序并作為類別值。處理后的調度數據集結構如表1所示。

表1 MOO數據集數據結構表

CART算法采用后剪枝的方法防止決策樹過度擬合，從葉節點開始，在除去從屬同一父節點的同級葉節點后不純度誤差較小，則除去這些葉節點，再從父節點重新出發循環計算；不斷地從葉節點往上回溯，形成最終的決策樹，如圖3所示。

圖3生成的決策樹可表示為如表2的幾條“if-then”的規則組合。

圖3 分類不純度最低的CART樹圖

表2 if-then決策樹規則

4 知識驅動的生產調度優化

基于知識的調度可以自動或輔助調度人員完成調度方案的制定，根據實際給定的優化目標，對知識進行搜索和利用，進而執行擇優的調度方案，提供在線和離線的支持。上述的基于數據的調度規則挖掘和調度知識的表示，提出將調度規則知識用于啟發式智能調度算法人工魚群算法的初始化改進中，優化后分析得到的知識可以用于修改參數或者初始化人工魚群算法的種群，對生產調度的策略選取和優化求解提供指導。

4.1 目標模型

以第3章實例分析的調度問題為例，以交貨期和最小化總通過時間為調度目標，在數學描述的基礎上建立調度目標函數。若某作業車間有n個需要加工的工件，工件集合為N={1,2,…,n}，有m臺加工設備，設備集合為M={1,2,…,m} ，每個工件包含多道工序j，1≤j≤m。Oijk表示工件i的第j道工序在第k臺設備上加工，工序開始加工時間為Sijk，加工時間為Tijk，工件最后一道工序的加工開始時間為ESijk，需加工的時間ETijk。工件的交貨期為Di，同一時刻設備k上一組等待被加工的工序組合為[Oijk,Onmk]，采用二進制值表示工序的優先級，[Oijk,Onmk]=[1,0]表示Oijk先在設備k上加工。

加工過程中還要滿足一些工藝約束條件：一臺設備在同一時間只能操作一道工序；一個工件在同一時間只能在一臺設備上加工；不同工件間的工序是相互獨立的，一個工件的工藝是確定的且不可更改；工序一旦被加工是不可以中斷的；忽略工件切換和機器啟動時間。

故調度目標函數可定義為：

4.2 改進初始化種群的人工魚群算法

4.2.1 初始化種群改進策略

為了彌補傳統人工魚群算法的不足，國內外在人工魚群算法的改進方面進行了很多研究[14-16]。初始人工魚對算法的求解質量和搜索效率有著至關重要的影響，在傳統的人工魚群算法中，一般是隨機進行人工魚種群的初始化，導致初期搜索速度較慢，算法后期收斂緩慢，從而降低了算法的收斂速度。

針對JSSP調度問題，結合決策樹調度規則知識的應用，在設備的每一個決策點用調度知識進行快速簡便初始化工序隊排序。通過決策樹生成的IF-THEN規則判斷被比較工序對應的屬性取值，從而確定工序的先后執行順序，得到一組有序工序對。由于提取的規則無法完全覆蓋所有調度實例，可能會同時產生多個同級優先級工序。此時結合其他優先調度規則，如最短加工時間、最長剩余加工時間等，來最終確定一組工序的順序。為了提高人工魚初始種群的質量，采用混合初始化算法初始種群的方法，即60%的種群W1采用決策樹規則知識進行初始化，20%的種群W2采用優先調度規則初始化，20%的種群W3隨機生成，豐富人工魚種群的多樣性，進一步提高優化算法的搜索質量和搜索效率。

4.2.2 人工魚群調度算法流程

采用知識驅動的人工魚初始種群優化方法，以最小化總通過時間為調度目標，算法流程如圖4所示。

圖4 基于調度知識的改進人工魚群算法流程

5 實驗分析

為了驗證決策樹規則的有效性，以及決策樹規則對于人工魚群算法在求解調度問題的改進作用，以6×6規模的JSSP調度問題為例，選取4.1節中的目標模型和約束條件，應用于改進人工魚群算法的決策樹規則也是基于同樣的6×6規模的JSSP案例，對改進前后的算法進行實驗，分析其調度性能。具體調度數據如表3所示。表中5（130）表示工件1的第5道工序在設備M1上加工，加工時間為130。

表3 6×6調度算例數據表

算法的主要參數設置：種群規模為Total=40，視野距離Visual=6×6=36，擁擠度閾值δ=9，最大迭代次數T=20，試探次數trynumber=30。

表4就改進前后算法對于調度問題求解的運行結果進行了比較，分別對調度案例進行10次重復仿真，并將它們與遺傳算法、基于優先調度規則進行比較。由運行結果可知，改進人工魚群算法10次運行的方差較小，有一定的穩定性，并可以在較短的時間內獲得最優的目標函數值，算法效率較其余3個調度算法更高。

表4 改進前后算法運行結果比較

圖5和圖6分別通過甘特圖直觀地反映了兩種算法的最優調度順序，從甘特圖中可以看到知識驅動的人工魚群算法得到的工序排列設備利用率高，減少了空閑等待時間，總通過時間更短，調度方案更好。

圖5 基本人工魚群算法調度甘特圖

圖6 改進人工魚群算法調度甘特圖

上述實驗將決策樹規則作為約束來重新處理優化問題，有效性得到了驗證。現在將優化后的結果作為新增樣本，再次訓練初始的決策樹分類器，使得調整后的決策樹分類性能更準確，訓練后得到決策樹規則如表5所示。

表5 訓練后的決策樹規則

6 結束語

針對制造系統在知識獲取和應用方面的局限，本文首先梳理調度領域專業經驗及知識，提出了本體知識表示方法，并集成支持向量機和基于CART的學習算法挖掘決策樹規則以構建調度規則庫，完善調度知識庫。在實施過程中，研究決策樹規則和人工魚群算法的有效結合，并進一步應用于調度問題的求解，找到初始化人工魚種群的改進方法，運用調度知識驅動生產調度優化，并進行仿真實驗測試所提方案的有效性。仿真結果表明，基于知識驅動的人工魚群算法對于調度問題的求解有明顯的提高作用，提取的調度知識可用以指導作業車間調度過程，從而改善了企業調度方案可操作性和生產管理水平。

[1]徐本柱，費曉璐，章興玲.柔性作業車間批量劃分與并行調度優化[J].計算機集成制造系統，2016，22（8）：1953-1964.

[2]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.

[3]Cupek R，Ziebinski A，Huczala L，et al.Agent-based manufacturing execution systems for short-series production scheduling[J].Computers in Industry，2016，82：245-258.

[4]Yan Hongsen，Liu Fei.Knowledgeable manufacturing system—A new kind of advanced manufacturing system[J].Computer Integrated Manufacturing Systems，2001，7（8）：7-11.

[5]姚立，汪崢，穆華靈.基于知識制造系統優化及ASP.NET下實現[J].計算機技術與發展，2011，21（11）：1-3.

[6]汪浩祥，嚴洪森.基于多Agent可互操作知識化制造動態自適應調度策略[J].控制與決策，2013，28（2）：161-168.

[7]Vegetti M，Roldán L，Gonnet S，et al.A framework to represent，capture，and trace ontology development processes[J].Engineering Applications of Artificial Intelligence，2016，56：230-249.

[8]張心源，邱均平.大數據環境下的知識融合框架研究[J].圖書館學研究，2016（8）：66-70.

[9]吳強.基于本體的領域知識表示和獲取[J].計算機工程與應用，2005，41（31）：23-25.

[10]秦大力，于德介，劉堅，等.本體驅動的機械設備診斷維護知識建模[J].中國機械工程，2014，25（14）：1861-1866.

[11]鄭永前，王登俊.基于本體的白車身制造工藝知識的表示研究[J].現代制造工程，2012（2）：74-79.

[12]Bandaru S，Ng A H C，Deb K.Data mining methods for knowledge discovery in multi-objective optimization：Part A—Survey[J].Expert Systems with Applications，2017，70：139-159.

[13]Bandaru S，Ng A H C，Deb K.Data mining methods for knowledge discovery in multi-objective optimization：Part B—New developments and applications[J].Expert Systems with Applications，2017，70：119-138.

[14]Zhao Ming，Yin Huan，Sun Dihua，et al.Flexible job shop scheduling problem based on modified artificial fish swarm alogorithm[J].ChinaMechanicalEngineering，2016，27（8）：1059-1065.

[15]陳新.基于人工魚群算法的柔性作業車間調度研究[D].遼寧大連：大連理工大學，2015.

[16]孫福，張箭鋒，閆軍，等.文化算法框架下的改進人工魚群算法研究[J].計算機仿真，2014，31（4）：407-411.