湯洪濤，費永輝，陳青豐，詹 燕，魯建廈，李晉青

(浙江工業(yè)大學 特種裝備制造與先進加工技術教育部/浙江省重點實驗室，浙江 杭州 310012)

0 引言

柔性作業(yè)車間動態(tài)調(diào)度問題已經(jīng)得到廣泛的研究[1-7]。但隨著產(chǎn)品需求不斷向個性化轉(zhuǎn)變，制造工藝更加多樣，實際調(diào)度問題也變得更加復雜，制造企業(yè)對車間調(diào)度問題的解決方法在實際可操作性、計算效率以及對車間擾動的實時響應能力等方面都提出了更高的要求。優(yōu)先調(diào)度規(guī)則是一種簡單的啟發(fā)式規(guī)則，其計算效率高、實際可操作性強且可用于實時調(diào)度，適用于復雜動態(tài)的調(diào)度環(huán)境[8]。但優(yōu)先調(diào)度規(guī)則的性能受到實際環(huán)境變化的影響，單一的調(diào)度規(guī)則不能在所有擾動環(huán)境中都有較好的調(diào)度性能。為滿足實際作業(yè)車間調(diào)度的需求，一種可行的思路是從調(diào)度相關歷史數(shù)據(jù)中挖掘關于調(diào)度規(guī)則的調(diào)度知識來指導實際車間調(diào)度活動[9]。通過數(shù)據(jù)挖掘來解決調(diào)度問題的研究主要分為結合已有優(yōu)先調(diào)度規(guī)則的方法與從調(diào)度相關歷史數(shù)據(jù)中挖掘調(diào)度規(guī)則的方法。

在結合已有的優(yōu)先調(diào)度規(guī)則方面，Wang等[10]針對半導體行業(yè)，提出一種結合決策樹與神經(jīng)網(wǎng)絡從調(diào)度相關歷史數(shù)據(jù)中挖掘優(yōu)先調(diào)度規(guī)則選擇機制的方法，該選擇機制可以得到當前環(huán)境下最適合的優(yōu)先調(diào)度規(guī)則。Zhang等[11]通過聚類將車間狀態(tài)進行劃分，并借助強化學習從仿真數(shù)據(jù)中學習如何在不同車間狀態(tài)下選擇最合適的優(yōu)先調(diào)度規(guī)則。Ma等[12]提出了基于支持向量回歸(Support Vector Regression，SVR)的動態(tài)調(diào)度問題解決方法，該方法借助SVR挖掘得到針對不同車間實時狀態(tài)的優(yōu)先調(diào)度規(guī)則組合方法。Nasiri等[13]通過多層感知人工神經(jīng)網(wǎng)絡、徑向基函數(shù)和數(shù)據(jù)包絡分析，從離散事件仿真數(shù)據(jù)中挖掘得到針對機器的優(yōu)先調(diào)度規(guī)則實時組合方法。

優(yōu)先調(diào)度規(guī)則僅通過少量信息作出調(diào)度決策，這可能導致調(diào)度結果不盡如人意，因此從調(diào)度相關歷史數(shù)據(jù)中提取新的調(diào)度規(guī)則是另一種思路。LI等[14]提出一種利用決策樹從調(diào)度相關歷史數(shù)據(jù)中得到全新調(diào)度規(guī)則的方法，并通過實驗證明了所提取的調(diào)度規(guī)則能很好地擬合原調(diào)度方案。Sigurdur等[15]提出一種兩階段的調(diào)度知識學習方法，首先學習如何從調(diào)度過程數(shù)據(jù)中得到適合挖掘的訓練實例，再對這些訓練實例進行調(diào)度規(guī)則的挖掘。王成龍等[16]提出一種結合Petri網(wǎng)建模的分支定界算法與決策樹算法的調(diào)度規(guī)則挖掘方法，提取的調(diào)度規(guī)則可用于指導靜態(tài)作業(yè)車間調(diào)度。Tarik等[17]針對單機總加權拖期最小化調(diào)度問題展開研究，提出一種采用神經(jīng)網(wǎng)絡的調(diào)度規(guī)則挖掘方法。Ingimundardottir等[18]為了提高調(diào)度規(guī)則的挖掘效率與準確率，提出一種訓練數(shù)據(jù)的構造方法，并通過偏好學習的方法，從訓練數(shù)據(jù)中挖掘調(diào)度規(guī)則。Zahmani等[19]提出一種結合數(shù)據(jù)挖掘算法與遺傳算法的單機總加權拖期最小化調(diào)度問題求解方法，采用數(shù)據(jù)挖掘算法挖掘調(diào)度規(guī)則，并運用遺傳算法使用這些調(diào)度規(guī)則。

綜上所述，目前關于從調(diào)度相關歷史數(shù)據(jù)中挖掘調(diào)度規(guī)則的方法主要針對普通作業(yè)車間調(diào)度問題，但將其運用于柔性作業(yè)車間動態(tài)調(diào)度問題的較少。此外，上述方法所使用的調(diào)度相關歷史數(shù)據(jù)偏向于理論數(shù)據(jù)，隨著智能感知設備在車間層的大量使用，車間開始向智能化發(fā)展[20]，車間調(diào)度相關歷史數(shù)據(jù)呈現(xiàn)出規(guī)模大、價值低、連續(xù)采樣、高維等工業(yè)大數(shù)據(jù)的特點。

為此，本文提出一種針對柔性作業(yè)車間動態(tài)調(diào)度問題的調(diào)度規(guī)則挖掘方法。該方法在處理具有工業(yè)大數(shù)據(jù)特點的調(diào)度相關歷史數(shù)據(jù)時，使用了Hadoop生態(tài)體系下的開源大數(shù)據(jù)技術，完成數(shù)據(jù)采集、清洗、整合與篩選。同時，考慮到在動態(tài)調(diào)度中，車間擾動環(huán)境的變化會改變生產(chǎn)屬性對于調(diào)度決策影響的大小，因此，該方法以調(diào)度方案為單元采用DBSCAN(density-based spatial clustering of applications with noise)聚類方法對預處理的數(shù)據(jù)進行聚類，將不同擾動環(huán)境下作出的調(diào)度決策所產(chǎn)生的數(shù)據(jù)進行劃分。在以往關于調(diào)度規(guī)則挖掘的研究中，決策樹是一種被廣泛采用的挖掘方法，但決策樹的泛化能力弱，不適合大規(guī)模、高維度且存在噪聲的調(diào)度相關歷史數(shù)據(jù)集的調(diào)度規(guī)則挖掘，因此本文提出了改進的隨機森林算法。最后，通過實驗驗證了該調(diào)度規(guī)則挖掘方法得到的調(diào)度規(guī)則在具有優(yōu)先調(diào)度規(guī)則優(yōu)點的同時，還具有較好的調(diào)度性能。

1 調(diào)度任務定義

柔性作業(yè)車間的車間模式可以描述為：在作業(yè)車間的生產(chǎn)中，有n個待加工工件和m個可選加工機器，每個工件都有多道加工工序，每道工序可以在多臺機器上加工完成。同時，在車間的運行過程中，還會發(fā)生例如機器故障、原材料短缺、收到緊急訂單等擾動。

調(diào)度規(guī)則是一種實時調(diào)度的方法，挖掘所得調(diào)度規(guī)則的調(diào)度任務是在考慮擾動的情況下解決兩個子問題：①工件的機器選擇問題；②空閑機器從隊列中選擇工件進行加工的問題。通過兩兩比較選出最優(yōu)的方法，可以將上述兩個子問題轉(zhuǎn)換成以下兩個分類問題：①對于某一工件的某道工序，給定可以加工這道工序的機器集合中的任意兩臺機器，比較這兩臺機器，區(qū)分出適合該工件加工的機器與不適合該工件加工的機器；②對于某臺空閑機器，給定在這臺機器排隊等待加工的工件集合中的任意兩個工件，比較這兩個工件，區(qū)分出加工優(yōu)先性高的工件與加工優(yōu)先性低的工件。

2 調(diào)度規(guī)則挖掘架構

柔性作業(yè)車間是一類工序加工路徑可以靈活調(diào)整的車間模式，在該模式的運行中會遇到各種擾動事件，同時會產(chǎn)生具有規(guī)?；?、高維度、多樣化特點的調(diào)度相關歷史數(shù)據(jù)。針對柔性作業(yè)車間的特點，本文設計了如圖1所示的調(diào)度規(guī)則挖掘架構。該架構由結合大數(shù)據(jù)的數(shù)據(jù)預處理模型、基于擾動屬性的聚類策略與基于改進隨機森林算法的挖掘模型3部分組成。

結合大數(shù)據(jù)的數(shù)據(jù)預處理模型的主要任務是處理來自于制造執(zhí)行系統(tǒng)(Manufacturing Execution System，MES)、企業(yè)資源計劃(Enterprise Resource Planning，ERP)、數(shù)據(jù)采集與監(jiān)控系統(tǒng)(Supervisory Control and Data Acquisition，SCADA)等現(xiàn)有的信息系統(tǒng)中與調(diào)度相關的歷史數(shù)據(jù)。該模型結合大數(shù)據(jù)技術，通過數(shù)據(jù)采集、數(shù)據(jù)清洗、數(shù)據(jù)整合與數(shù)據(jù)篩選，將具有工業(yè)大數(shù)據(jù)特點的調(diào)度相關歷史數(shù)據(jù)轉(zhuǎn)化成可以進行調(diào)度規(guī)則挖掘的數(shù)據(jù)形式。

柔性作業(yè)車間中擾動環(huán)境的變化會改變生產(chǎn)屬性對調(diào)度決策的影響程度，通過基于擾動屬性的聚類策略，可以對不同擾動環(huán)境下作出的調(diào)度決策產(chǎn)生的調(diào)度相關歷史數(shù)據(jù)進行合理的劃分。在此基礎上，通過數(shù)據(jù)挖掘算法可以從聚類后的每個簇中分別得到針對不同擾動環(huán)境的調(diào)度規(guī)則。在擾動環(huán)境發(fā)生改變時，切換不同的調(diào)度規(guī)則，以此提高調(diào)度規(guī)則對擾動的實時響應能力。

通過基于改進隨機森林算法挖掘模型，可以從調(diào)度相關歷史數(shù)據(jù)中發(fā)現(xiàn)有價值的調(diào)度規(guī)律或模式，并以調(diào)度規(guī)則的形式表現(xiàn)。在該模型中提出一種改進的隨機森林算法，并以此作為調(diào)度規(guī)則的挖掘算法，得到的隨機森林調(diào)度規(guī)則由多棵決策樹構成，通過貝葉斯投票機制得到每棵決策樹加權后的結果，從而區(qū)分出合適的機器或加工優(yōu)先性更高的工件。

2.1 結合大數(shù)據(jù)技術的調(diào)度歷史數(shù)據(jù)預處理模型

隨著信息技術、自動化技術、物聯(lián)網(wǎng)技術在制造業(yè)的飛速發(fā)展，特別是無線傳感器、數(shù)據(jù)采集裝置和其他智能感知設備在車間底層的大量使用，企業(yè)全面和精準獲取具有大數(shù)據(jù)特點的調(diào)度相關歷史數(shù)據(jù)的能力大幅增強[21]。對于這些多源異構的調(diào)度大數(shù)據(jù)，需要通過恰當?shù)臄?shù)據(jù)預處理，才能從中獲取想要的調(diào)度知識。本文提出一種結合大數(shù)據(jù)技術的調(diào)度數(shù)據(jù)預處理模型，包括數(shù)據(jù)采集、數(shù)據(jù)清洗、數(shù)據(jù)整合與數(shù)據(jù)篩選4個部分，如圖2所示。

2.1.1 數(shù)據(jù)采集

調(diào)度數(shù)據(jù)采集是調(diào)度規(guī)則挖掘的前提，其目標是從多個數(shù)據(jù)源中采集柔性作業(yè)車間制造的調(diào)度相關歷史數(shù)據(jù)。本文使用Hadoop生態(tài)體系下的數(shù)據(jù)采集工具Sqoop與Flume，從數(shù)據(jù)庫或文件系統(tǒng)中獲取調(diào)度方案執(zhí)行時機器、工件和人員等信息?？紤]到柔性作業(yè)車間動態(tài)調(diào)度問題是在有擾動的環(huán)境下解決工件的機器選擇問題和空閑機器的工件選擇問題，因此采集的調(diào)度相關歷史數(shù)據(jù)集合Dh(簡稱調(diào)度數(shù)據(jù)集合)可以表示為Dh={d1,d2,d3}。其中：d1為調(diào)度方案制定時與擾動相關的系統(tǒng)擾動信息，如車間中機器故障數(shù)量、返工工件數(shù)量等；d2為工件的某道工序選擇加工機器時，當前可以加工這道工序的機器集合中每臺機器的狀態(tài)信息，如機器前在制品數(shù)量、機器加工這道工序的時間等；d3為空閑機器需要在等待隊列中選擇工件進行加工時，當前隊列中每個工件的狀態(tài)信息，如工件在該機器上加工的時間、工件是否為返工工件等。

2.1.2 數(shù)據(jù)清洗

在車間智能化的發(fā)展趨勢下，勢必會造成對調(diào)度相關歷史數(shù)據(jù)進行多次重復的記錄，導致從多個業(yè)務系統(tǒng)中采集的調(diào)度數(shù)據(jù)集合Dh中存在數(shù)據(jù)沖突與數(shù)據(jù)重復等情況，只有對復雜多樣的調(diào)度數(shù)據(jù)進行數(shù)據(jù)清洗才能為后續(xù)的調(diào)度規(guī)則挖掘奠定基礎。本文通過建立過濾規(guī)則庫和數(shù)據(jù)清洗規(guī)則，定義每種生產(chǎn)屬性需要使用的過濾規(guī)則以及過濾規(guī)則內(nèi)部的數(shù)據(jù)處理邏輯，對采集得到的多源調(diào)度歷史相關數(shù)據(jù)進行清洗工作?；谠撨^濾器與數(shù)據(jù)清洗規(guī)則，每一條采集的數(shù)據(jù)會根據(jù)自身屬于調(diào)度數(shù)據(jù)集合Dh中哪一部分的哪一類數(shù)據(jù)，查詢數(shù)據(jù)清洗規(guī)則中的數(shù)據(jù)清洗方法，從規(guī)則庫中選擇相應的過濾規(guī)則進行組合，并通過Spark(為大規(guī)模數(shù)據(jù)處理而設計的快速通用的計算架構)完成最終的數(shù)據(jù)清洗工作。經(jīng)過數(shù)據(jù)清洗的調(diào)度數(shù)據(jù)集合Dh將被存入到Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System，HDFS)中。

2.1.3 數(shù)據(jù)整合

調(diào)度數(shù)據(jù)集合Dh中的數(shù)據(jù)形式混亂，無法直接用于接下來的數(shù)據(jù)篩選、聚類以及調(diào)度規(guī)則挖掘工作，需要通過數(shù)據(jù)整合整理調(diào)度數(shù)據(jù)集合Dh的數(shù)據(jù)形式。數(shù)據(jù)整合的目的是將調(diào)度數(shù)據(jù)集合Dh中的數(shù)據(jù)以調(diào)度方案為單元進行劃分，并將其轉(zhuǎn)化為適合數(shù)據(jù)挖掘的表達形式。數(shù)據(jù)整合工作分為兩個階段：第一階段的整合通過數(shù)據(jù)倉庫工具Hive使用SQL語句對HDFS文件系統(tǒng)中的調(diào)度數(shù)據(jù)集合Dh以調(diào)度方案為單元進行劃分，即將一次調(diào)度方案在執(zhí)行中產(chǎn)生的調(diào)度相關歷史數(shù)據(jù)劃分到一起；第二階段的整合使用Spark將第一階段整合的數(shù)據(jù)中的d2與d3部分轉(zhuǎn)化為訓練實例，用于調(diào)度規(guī)則挖掘，轉(zhuǎn)化為訓練實例的過程如下，以采集的調(diào)度數(shù)據(jù)集合Dh的d2部分為例，將某歷史調(diào)度方案中實際選擇的機器m1視為最合適的機器，將其與其他可加工該工序的備選機器集合{m2,m3,…}中的機器一一比較形成訓練實例，具體表達形式如表1所示。最終完成數(shù)據(jù)整合的調(diào)度相關歷史數(shù)據(jù)集合，以調(diào)度方案單元的形式存儲到NoSql數(shù)據(jù)庫Hbase中。

表1 工序機器選擇相關信息的數(shù)據(jù)表達形式

2.1.4 數(shù)據(jù)篩選

在調(diào)度數(shù)據(jù)集合Dh中隱含了反映實際調(diào)度環(huán)境特點及調(diào)度知識的大量有效信息，也伴隨著許多無用的或錯誤的規(guī)律或模式。同時，調(diào)度方案的優(yōu)劣將影響調(diào)度方案執(zhí)行時所產(chǎn)生的調(diào)度數(shù)據(jù)中有多少有價值的調(diào)度知識可以提取。通過建立如圖3所示的多指標篩選機制，從多個角度對歷史調(diào)度方案進行考量，使用Spark篩選得到表現(xiàn)良好的調(diào)度方案在執(zhí)行中產(chǎn)生的調(diào)度相關歷史數(shù)據(jù)集合Db(簡稱較優(yōu)調(diào)度數(shù)據(jù)集合)。

多指標篩選機制中選擇了最大完工時間、總拖期時間、機器總負荷3個指標作為篩選依據(jù)，能同時滿足這3個指標的調(diào)度方案在執(zhí)行中產(chǎn)生的調(diào)度數(shù)據(jù)集合，將作為調(diào)度規(guī)則挖掘算法的輸入。在最大完工時間指標上，以同種情況下只使用最短加工時間(Shortest Process Time，SPT)規(guī)則生成的調(diào)度方案的最大完工時間作為篩選標準。只使用SPT規(guī)則是指工件選擇加工最快的機器與空閑機器選擇加工時間最短的工件。在總拖期時間指標上，以同種情況下使用最早交貨期(Earliest job Due Date，EDD)規(guī)則結合SPT規(guī)則完成相同情況下調(diào)度任務的總延期時間作為篩選標準。SPT+EDD規(guī)則是指工件選擇加工最快的機器與空閑機器選擇交貨期最早的工件。在機器總負荷指標上，以同種情況下結合設備最長等待時間調(diào)度(Longest Machine Waiting Time，LMWT)規(guī)則與SPT規(guī)則完成調(diào)度任務的機器總負荷作為篩選標準，LMWT+SPT規(guī)則是指工件選擇空閑時間最長的機器與空閑機器選擇加工時間最短的工件。

2.2 基于生產(chǎn)擾動屬性的聚類策略

本文選擇隨機森林算法作為調(diào)度規(guī)則的挖掘算法，最終得到的調(diào)度規(guī)則為該算法構建的隨機森林，本質(zhì)上為多棵經(jīng)過訓練的C4.5決策樹。因此，調(diào)度規(guī)則的調(diào)度性能取決于決策樹的分類性能，調(diào)度規(guī)則的計算效率與復雜程度取決于決策樹的分支數(shù)量。決策樹的分類性能越好，分支越少，則得到的調(diào)度規(guī)則的復雜程度越低、調(diào)度性能越好、計算效率也越高?；谏a(chǎn)擾動屬性的聚類策略提出的目的是為了提高調(diào)度規(guī)則中決策樹的分類性能，減少決策樹的分支數(shù)量。在此基礎上，通過數(shù)據(jù)挖掘算法可以從聚類后的每個簇中分別得到針對不同擾動環(huán)境的調(diào)度規(guī)則。在擾動環(huán)境發(fā)生改變時，切換不同的調(diào)度規(guī)則可以提高調(diào)度規(guī)則對擾動的實時響應能力。

在動態(tài)調(diào)度問題中，車間擾動環(huán)境的變化會改變生產(chǎn)屬性對調(diào)度決策的影響程度，例如在某種沒有擾動的情況下，空閑機器在判斷工件加工優(yōu)先性時不會考慮工件所屬訂單是否為緊急訂單，但是當車間發(fā)生緊急插單時，工件所屬訂單是否為緊急訂單會成為工件加工優(yōu)先性的考慮因素。生產(chǎn)屬性對調(diào)度決策的影響程度的變化體現(xiàn)在C4.5決策樹中為生產(chǎn)屬性的信息增益率的改變。信息增益率的公式如下：

GR(D,A)=G(D,A)/H(A)；

(1)

G(D,A)=H(D)-H(D|A)；

(2)

(3)

(4)

(5)

其中：GR(D,A)表示生產(chǎn)屬性A的信息增益率；G(D,A)表示屬性A的信息增益；H(A)表示屬性A的分裂信息；D表示訓練實例數(shù)據(jù)集，|D|表示D的訓練實例數(shù)量，而D具有K個類別Ck，k=1,2；|Ck|表示在類別Ck中的訓練實例個數(shù)。D可以通過屬性A將其劃分為n個子集D1，D2，…，Dn，|Di|為Di的訓練實例個數(shù)。Di中屬于類Ck的訓練實例的集合為Dik，|Dik|為Dik的訓練實例個數(shù)。

使用上述情況中沒有擾動的情況下產(chǎn)生的訓練實例數(shù)據(jù)集Dnodisturbance、發(fā)生緊急插單后產(chǎn)生的訓練實例數(shù)據(jù)集Ddisturbance，以及合并了Dnodisturbance與Ddisturbance的訓練實例數(shù)據(jù)集Dtotal分別構建3棵決策樹，得到Treenodisturbance、Treedisturbance與Treetotal。在Treenodisturbance構建時，生產(chǎn)屬性工件所屬訂單是否為緊急訂單的信息增益率為0；在Treedisturbance構建時，工件所屬訂單是否為緊急訂單的信息增益率為a(a>0)；在Treetotal構建時，工件所屬訂單是否為緊急訂單的信息增益率b介于a與0之間。這表明將幾種不同擾動環(huán)境下產(chǎn)生的訓練實例數(shù)據(jù)集合一起(類似于Dtotal)用于構建決策樹會導致生產(chǎn)屬性的信息增益率偏離實際值。而C4.5決策樹是以信息增益率來進行特征選擇的決策樹學習過程，因此屬性信息增益率的偏離會影響構建的決策樹的分類性能。此外，幾種不同擾動環(huán)境下產(chǎn)生的訓練實例數(shù)據(jù)集合一起構建的決策樹較一種擾動環(huán)境下產(chǎn)生的訓練實例數(shù)據(jù)集合(類似于Dnodisturbance與Ddisturbance)構建的決策樹會有更多的分支，因為更多的擾動環(huán)境意味著在構建決策樹時，更多的與擾動相關的生產(chǎn)屬性都會有一定的信息增益率，這些屬性會在決策樹的分支中至少出現(xiàn)一次。

綜上所述，若能對較優(yōu)調(diào)度數(shù)據(jù)Db進行合理的劃分，區(qū)分出在不同擾動環(huán)境下做出的調(diào)度決策所產(chǎn)生的數(shù)據(jù)，再從劃分的每個區(qū)域中分別得到針對不同擾動環(huán)境的調(diào)度規(guī)則，可以使得調(diào)度規(guī)則復雜程度更低，計算效率更高，調(diào)度性能更好。

Db中d1部分數(shù)據(jù)具有數(shù)據(jù)規(guī)模大且存在噪聲等生產(chǎn)數(shù)據(jù)的典型特點。DBSCAN算法是一種基于密度的經(jīng)典聚類算法，它可以對任意形狀的數(shù)據(jù)集進行聚類，可以分離噪聲數(shù)據(jù)，并且不需要人為事先指定簇的數(shù)量，多用于事先不確定聚類個數(shù)且?guī)в性肼暤臄?shù)據(jù)集[22-23]。李群等[24]在聚類測試中發(fā)現(xiàn)，對大規(guī)模且存在噪聲的數(shù)據(jù)進行聚類時，DBSCAN聚類算法比K-means與AGENES聚類算法準確率更高，計算速度更快。此外，在對于生產(chǎn)數(shù)據(jù)的處理中，焦磊等[25]將DBSCAN聚類算法成功運用于調(diào)度規(guī)則挖掘前生產(chǎn)數(shù)據(jù)的屬性離散化，即通過單個屬性對數(shù)據(jù)集進行劃分，而基于擾動屬性的聚類策略是在調(diào)度規(guī)則挖掘前，依據(jù)多個生產(chǎn)數(shù)據(jù)屬性對數(shù)據(jù)集進行劃分，但本質(zhì)上都是依據(jù)生產(chǎn)數(shù)據(jù)屬性對數(shù)據(jù)集進行劃分，因此將DBSCAN運用于基于擾動屬性的聚類具有有效性。

以調(diào)度方案為單元(即一個調(diào)度方案產(chǎn)生的數(shù)據(jù)作為一個對象)，根據(jù)Db中的方案制定時的系統(tǒng)擾動屬性(d1部分)，采用DBSCAN對Db進行聚類的具體步驟如下：

步驟1對d1部分數(shù)據(jù)進行標準化處理，使各擾動屬性值都處于同一個數(shù)量級別上。如某擾動屬性在各個方案中的數(shù)據(jù)為X1,X2,X3,…，Xn，則它們需要經(jīng)過如下變換：

(6)

步驟2確定DBSCAN算法的參數(shù)。本文采用焦磊等[25]提出的自動計算方法得到領域半徑Eps，與核心對象領域半徑內(nèi)至少包含的對象個數(shù)MinPts。

步驟3隨機找出一個未被處理(沒有歸為某個簇或者標記為噪聲)的核心對象p(領域半徑內(nèi)包含的對象個數(shù)不小于MinPts)，建立新簇C，將p鄰域半徑Eps內(nèi)所有對象加入候選集N。

步驟4隨機找出一個候選集N中尚未被處理的對象q。若q為核心對象，則將q鄰域半徑Eps內(nèi)未被處理的且未加入到N的對象加入到N中。如果q未歸入任何一個簇，則將q加入C。

步驟5重復步驟4，直到N為空。

步驟6重復步驟3～步驟5，直到?jīng)]有新的對象可以被添加到任何簇時，該過程結束

2.3 基于改進隨機森林算法的挖掘模型

在普通車間靜態(tài)調(diào)度問題的調(diào)度規(guī)則挖掘研究中，決策樹是一種被廣泛使用的挖掘算法[12-15]，具有計算量小、調(diào)度知識表達直觀、能夠處理數(shù)字和其他類別的數(shù)據(jù)等特點。然而，決策樹的泛化能力弱，容易對訓練數(shù)據(jù)集中的噪聲過度擬合，這在一定程度上限制了所挖掘調(diào)度規(guī)則的調(diào)度性能。本文針對柔性作業(yè)車間動態(tài)調(diào)度問題進行調(diào)度規(guī)則挖掘，使用的數(shù)據(jù)是具有工業(yè)大數(shù)據(jù)特點的調(diào)度相關歷史數(shù)據(jù)，即使這些數(shù)據(jù)經(jīng)過了預處理，還是不可避免地存在噪聲屬性與噪聲數(shù)據(jù)。如果使用決策樹進行調(diào)度規(guī)則挖掘，很容易發(fā)生過擬合現(xiàn)象。

隨機森林是一種使用多棵決策樹對樣本進行訓練并預測的組合分類器。通過隨機森林算法構建隨機森林時，對泛化誤差進行了無偏估計，因此具有較強的泛化能力。此外，隨機森林算法在處理大規(guī)模、高維度數(shù)據(jù)集時，相對于其他分類算法具有更高的準確度[26]。因此，本文將隨機森林算法作為基礎算法用于柔性作業(yè)車間動態(tài)調(diào)度問題的調(diào)度規(guī)則挖掘。同時，本文選取C4.5決策樹作為隨機森林算法的基本分類器。C4.5算法是應用最廣泛的決策樹算法，是ID3算法的一種延伸和優(yōu)化，它克服了ID3算法傾向于選擇擁有多個屬性值的屬性作為分裂屬性的不足，并且可以處理離散型屬性(如機器是否故障)和連續(xù)型屬性(如加工時間)。C4.5算法已成功應用于許多分類問題[27-28]，其中也包括調(diào)度規(guī)則挖掘領域，如王成龍[16]等通過C4.5算法對作業(yè)車間靜態(tài)調(diào)度問題進行調(diào)度規(guī)則挖掘，故本文將C4.5算法作為隨機森林算法的基本分類器。

2.3.1 隨機森林算法的改進

柔性作業(yè)車間調(diào)度問題相對于普通車間靜態(tài)調(diào)度問題，工件加工路徑更加靈活，考慮了更多實際的擾動因素，因此對于調(diào)度規(guī)則的調(diào)度性能有更高的要求。為了滿足調(diào)度規(guī)則挖掘工作的客觀需求，本文針對隨機森林算法做出了兩點改進：

(7)

隨機森林算法通過Bagging(bootstrap aggregation)策略生成的決策樹具有近似的分布，因此隨機森林算法的方差可以看作是一組同分布的隨機變量的方差，其方差計算如式(8)[30]所示：

(8)

由式(8)可知，對于需要構建多棵決策樹的隨機森林算法(n較大)，若能減少決策樹之間的相關性ρ，就能減小方差，從而提高算法的性能。式中：n為隨機森林中決策樹的數(shù)量；Ti表示第i棵決策樹；ρ代表決策樹之間的相關性；θ2代表每棵決策樹的方差。

基于上述分析，本文提出了避免相似決策樹的策略，用于減少決策樹之間的相關性ρ，達到提高隨機森林算法性能的目的。如果兩棵決策數(shù)之間的相似度大于60%，即被認為是相似的決策樹[31]，需要淘汰其中對測試數(shù)據(jù)分類表現(xiàn)差的一棵。該策略采用Irene[32]提出的決策樹相似度計算方法，決策樹之間的相似度取決于它們在使用相同特征屬性并對測試實例產(chǎn)生相同預測次數(shù)的百分比，相似度計算如式(9)所示：

(9)

式中：DT1與DT2表示進行相似度計算的兩棵決策樹；k表示DT1與DT2對測試實例分類結果相同的次數(shù)；r1n與r2n表示第n次分類結果相同時，DT1與DT2用到的特征屬性，c表示分類結果；當r1n=r2n時，即DT1與DT2用相同的特征屬性得到相同的分類結果時，I(r1n·c,r2n·c)=1，否則為0，Nt為測試實例的個數(shù)。

(2)使用貝葉斯投票機制 傳統(tǒng)的隨機森林算法多采用少數(shù)服從多數(shù)的投票機制，在隨機森林中決策樹的分類性能無論好壞，都具有相同的權值。這導致分類性能差的決策樹與分類性能好的決策樹的分類結果對于最終結果具有相同的影響程度。而貝葉斯投票機制采用貝葉斯平均算法(Bayesian average)計算投票結果，是一種以貝葉斯推理(Bayesian inference)思想為基礎的投票機制。貝葉斯推理是一種運用于不確定條件下的決策統(tǒng)計方法，它通過歷史信息對原有的判斷進行修正，其基本原理是將未知參數(shù)的先驗信息與樣本信息綜合，再根據(jù)貝葉斯定理得到后驗信息，以此判斷未知參數(shù)。貝葉斯投票機制以貝葉斯推理為基礎，根據(jù)決策樹對測試數(shù)據(jù)的分類表現(xiàn)，設定一個估計值(根據(jù)貝葉斯推理中的先驗概率得到)作為“權”添加到分類結果中，決策樹對測試數(shù)據(jù)的分類表現(xiàn)越好，“權”的比重也越小。在貝葉斯投票機制中，每一棵決策樹加權后的表決結果的計算公式如下：

(10)

式中：WR表示決策樹給出的加權結果；v代表該決策樹對測試實例正確分類的次數(shù)；m表示對測試實例錯誤分類次數(shù)；C表示該決策樹給出的分類結果；R表示所有決策樹給出的分類結果的均值，也作為貝葉斯推理中的“先驗概率”。由式(10)可知，決策樹在測試中的分類表現(xiàn)越差，其加權結果中的自身

分類結果C所占比重v/(v+m)越小，分類結果的均值R所占比重m/(m+v)越大。反之，決策樹在測試中的分類表現(xiàn)越好，其自身分類結果C所占比重v/(v+m)越大，分類結果的均值R所占比重m/(m+v)越小。由此可見，貝葉斯投票機制借助了貝葉斯推理的思想，通過決策樹在測試中的分類表現(xiàn)這一歷史信息，修正了其分類結果對最終結果的影響程度。因此，本文選擇貝葉斯投票機制代替少數(shù)服從多數(shù)的投票機制。

2.3.2 改進隨機森林算法的調(diào)度規(guī)則挖掘流程

如圖4為改進的隨機森林算法挖掘調(diào)度規(guī)則的流程圖，圖中隨機森林調(diào)度規(guī)則1由d2部分數(shù)據(jù)訓練得到,用于解決工件的機器選擇問題;隨機森林調(diào)度規(guī)則2,由d3部分數(shù)據(jù)訓練得到,用于解決空閑機器的工件選擇問題。針對某擾動環(huán)境，使用改進的隨機森林算法挖掘調(diào)度規(guī)則的步驟如下：

步驟1構建隨機森林。首先，將該擾動環(huán)境對應簇中的較優(yōu)調(diào)度數(shù)據(jù)作為訓練數(shù)據(jù)。在此基礎上，從較優(yōu)調(diào)度數(shù)據(jù)的d2/d3部分中有放回地抽取訓練實例，形成k個新的訓練實例集合(bagging策略)。最后，每個訓練實例集合分別從d2/d3的屬性中隨機選擇m個屬性作為特征屬性，并計算最佳分類方式，得到k棵決策樹。

步驟2測試決策樹分類表現(xiàn)。將較優(yōu)調(diào)度數(shù)據(jù)的d2/d3部分沒有被選為訓練實例的數(shù)據(jù)作為測試數(shù)據(jù)，測試并記錄每棵決策樹的分類表現(xiàn)。

步驟3避免相似決策樹策略。計算決策樹之間的相似度，若兩顆決策樹之間的相似度大于60%，則被認為相似決策樹，需要淘汰其中在測試表現(xiàn)中較差的一棵。

步驟4計算每棵決策樹的權值。根據(jù)對測試數(shù)據(jù)分類的表現(xiàn)，計算隨機森林中保留下的每一棵決策樹的權值，即得到式(10)中的v/(m+v)與m/(v+m)。

2.3.3 隨機森林調(diào)度規(guī)則運用

通過改進的隨機森林算法挖掘得到隨機森林調(diào)度規(guī)則后，就可以使用隨機森林調(diào)度規(guī)則區(qū)分出合適的機器，或得到加工優(yōu)先程度高的工件。例如，某工件的工序OperationX需要在m1、m2、m3中選擇一臺最合適的機器進行加工。首先，找到與當前柔性作業(yè)車間的擾動環(huán)境對應的簇中的隨機森林調(diào)度規(guī)則1，以此作為區(qū)分合適機器的依據(jù)。在此基礎上，先從m1與m2中找出適合OperationX加工的機器，將m1和m2的實時信息輸入隨機森林調(diào)度規(guī)則1，得到該規(guī)則中所有決策樹分類結果，這些結果中包含了1和2(1代表前者m1合適，2代表后者m2合適)。根據(jù)式(10)得到每棵決策樹加權后的表決結果，將這些結果取均值，若均值小于1.5，則說明前者m1更適合OperationX加工，反之m2為合適的機器。得到m1與m2中合適的機器以后，用相同的方法與m3比較，就能得到最適合OperationX加工的機器。

3 模型驗證

為說明以上提出的調(diào)度規(guī)則挖掘方法的可行性與有效性，通過實驗對其進行驗證。首先利用仿真產(chǎn)生柔性作業(yè)車間動態(tài)調(diào)度的調(diào)度相關歷史數(shù)據(jù)，再使用調(diào)度規(guī)則挖掘框架從中挖掘得到隨機森林調(diào)度規(guī)則。隨機生成滿足多指標篩選的較優(yōu)調(diào)度方案，運用該調(diào)度規(guī)則計算得到與較優(yōu)調(diào)度方案相同調(diào)度問題的調(diào)度方案，并在最大完工時間、總拖期以及機器總負荷這3個指標上進行對比。此外，還將該調(diào)度規(guī)則的調(diào)度性能與未經(jīng)擾動屬性聚類的數(shù)據(jù)集挖掘得到的調(diào)度規(guī)則、使用未改進的隨機森林算法得到的調(diào)度規(guī)則、常用的優(yōu)先調(diào)度規(guī)則進行比較。

3.1 獲取調(diào)度規(guī)則

本文的實驗對象為一個擁有7臺機器的柔性作業(yè)車間，七臺機器分別為m1，m2，…，m7，假設在該柔性作業(yè)車間中加工的工件類型有8種，分別為JT1，JT2，…，JT8，每種類型工件的加工工藝固定，且加工批量都為10件，每種類型工件的各個工序在每臺機器上以100件為單位的初始加工時間如表2所示。車間每天的初始任務是上述類型的工件，每種加工100～200件，即10～20批，初始調(diào)度問題可以看作是問題規(guī)模為7×8的靜態(tài)的柔性作業(yè)車間調(diào)度問題。

表2 各工件加工時間表

初始調(diào)度方案通過以最大完工時間、總拖期以及機器總負荷作為調(diào)度指標，并基于帕累托優(yōu)化的遺傳算法得到。在初始調(diào)度方案的執(zhí)行過程中，會發(fā)生機器故障、工件返工、缺料、緊急插單、加工時間變化這幾種在實際生產(chǎn)環(huán)境中經(jīng)常發(fā)生的擾動。其中每臺機器發(fā)生故障的時間間隔服從指數(shù)分布，平均間隔為150個加工單位時間，且每次故障的修復時間未知，即在相關方案中不再使用該機器；工件的每道工序加工完都有5%的概率需要返工；一批工件的每道工序在選擇加工機器后，有5%的可能發(fā)現(xiàn)缺料，缺料時間為4個加工單位時間；插單的時間間隔服從指數(shù)分布，平均間隔為20個加工時間單位，每次緊急插單的工件種類為2～4種，數(shù)量為每種100～300件；機器的加工時間將因為刀具磨損，隨著機器運行時間的增加線性增加，每臺機器每開動10個加工單位時間，加工時間會增加10%。針對這些擾動，將采用基于周期與事件驅(qū)動的混合重調(diào)度策略，對于機器故障、工件返工、缺料、緊急插單采用事件驅(qū)動的重調(diào)度策略，對于加工時間變化采用基于周期的重調(diào)度策略，重調(diào)度的周期為10個加工單位時間。

調(diào)度相關歷史數(shù)據(jù)將以仿真的方式獲得，首先模擬初始調(diào)度方案執(zhí)行，在該過程中根據(jù)上述各種擾動發(fā)生的特點模擬各類擾動，并通過基于周期與事件驅(qū)動的混合重調(diào)度策略得到重調(diào)度方案并執(zhí)行。在柔性作業(yè)車間動態(tài)調(diào)度活動的仿真中，采集工件與機器的實時狀態(tài)信息，采集頻率為0.001個加工單位時間一次，采集量為30天的調(diào)度相關歷史數(shù)據(jù)，并將其和系統(tǒng)的擾動信息一起存入數(shù)據(jù)庫，采集的信息如表3所示，這些數(shù)據(jù)具有連續(xù)采樣、高維、價值低等工業(yè)大數(shù)據(jù)的特點。得到這些調(diào)度相關歷史數(shù)據(jù)后，將采用本文提出的調(diào)度規(guī)則挖掘框架得到調(diào)度規(guī)則。

表3 采集數(shù)據(jù)表

3.2 實例驗證

下面通過一個實例來驗證所得調(diào)度規(guī)則的可行性。首先，從3.1節(jié)生成的調(diào)度方案(用于產(chǎn)生調(diào)度規(guī)則挖掘所需調(diào)度相關歷史數(shù)據(jù)的調(diào)度方案)中選擇一個較優(yōu)調(diào)度方案，較優(yōu)調(diào)度方案需要滿足多指標篩選機制的篩選條件，具體方案如圖5所示。圖5中較優(yōu)調(diào)度方案的調(diào)度任務如下：需要加工工件JT1，JT2，…，JT8各100件，即10批，其交貨期分別為20.0、22.0、14.0、21.0、19.0、22.0、18.0、23.0個加工單位時間。同時，圖5中較優(yōu)調(diào)度方案是一個經(jīng)歷了事件重調(diào)度與周期調(diào)度的調(diào)度方案，其初始調(diào)度方案如圖6所示，圖中序號百位數(shù)字表示工件類型，個位數(shù)字表示加工序號。在初始調(diào)度方案執(zhí)行過程中，機器m3在時間為4時發(fā)生了機器故障，機器故障后的重調(diào)度方案如圖7所示。當圖7方案執(zhí)行到JT1的第一道工序完成后，其第二道工序發(fā)生缺料，發(fā)生缺料后的重調(diào)度方案如圖8所示。當圖8方案執(zhí)行到時間為10時，進行了周期重調(diào)度，周期重調(diào)度后的調(diào)度方案如圖5所示。

在與圖5中較優(yōu)調(diào)度方案相同的調(diào)度問題(相同的擾動情況與調(diào)度任務)下，根據(jù)實時擾動環(huán)境選擇對應的隨機森林調(diào)度規(guī)則進行決策的調(diào)度方案(簡稱隨機森林調(diào)度方案)如圖9所示；使用未經(jīng)過基于擾動屬性聚類的數(shù)據(jù)集挖掘得到的調(diào)度規(guī)則生成的調(diào)度方案(簡稱未聚類調(diào)度方案)如圖10所示；使用未改進的隨機森林算法得到的調(diào)度規(guī)則生成的調(diào)度方案(簡稱未改進調(diào)度方案)如圖11所示；相同情況下，只使用SPT規(guī)則生成的調(diào)度方案(簡稱SPT調(diào)度方案)如圖12所示；使用SPT+EDD規(guī)則生成的調(diào)度方案(簡稱SPT+EDD調(diào)度方案)如圖13所示。

較優(yōu)調(diào)度方案、隨機森林調(diào)度方案、未聚類調(diào)度方案、未改進調(diào)度方案、SPT調(diào)度方案與SPT+EDD調(diào)度方案在最大完工時間、總拖期與機器總負荷這3項指標上的比較如表4所示，各指標的單位為加工單位時間。其中隨機森林調(diào)度方案在最大完工時間指標上比較優(yōu)調(diào)度方案略小，接近于較優(yōu)調(diào)度方案；在總拖期指標上比較優(yōu)調(diào)度方案大3.7個加工單位時間，略差于較優(yōu)調(diào)度方案；在機器總負荷指標比較優(yōu)調(diào)度方案小20%，明顯好于較優(yōu)調(diào)度方案。隨機森林調(diào)度方案在與未聚類調(diào)度規(guī)則方案、未改進調(diào)度方案的比較中，各項指標均有更好的表現(xiàn)。此外，隨機森林調(diào)度方案在與SPT調(diào)度方案、SPT+EDD調(diào)度方案的比較中，在最大完工時間與總拖期指標上表現(xiàn)更優(yōu)，在機器總負荷指標上比較接近。

表4 各方案多指標比較

下面通過多次實驗，證明所提調(diào)度規(guī)則挖掘方法的穩(wěn)定性。首先，從3.1節(jié)生成的調(diào)度方案中選擇多個能滿足多指標篩選的較優(yōu)調(diào)度方案，并保證每個較優(yōu)調(diào)度方案解決的調(diào)度問題不同。對于每個較優(yōu)調(diào)度方案，分別得到與其對應的隨機森林調(diào)度方案、未聚類調(diào)度方案、未改進調(diào)度方案、SPT調(diào)度方案與SPT+EDD調(diào)度方案，并以此較優(yōu)調(diào)度方案的最大完工時間、總拖期、機器總負荷為基準進行方案比較。對比結果如表5所示，各指標的單位為加工單位時間，表中數(shù)據(jù)為多次實驗中的其他方案(隨機森林調(diào)度方案、未聚類調(diào)度方案、未改進調(diào)度方案、SPT調(diào)度方案與SPT+EDD調(diào)度方案)和與其對應的較優(yōu)調(diào)度方案在3個指標上差值的均值。其中隨機森林調(diào)度方案在最大完工時間指標上接近于較優(yōu)調(diào)度方案，且比其他調(diào)度方案表現(xiàn)更優(yōu)；在總拖期指標上，比較優(yōu)調(diào)度方案大4.68個加工單位時間，略差于較優(yōu)調(diào)度方案，但好于其他方案；在機器總負荷指標上，接近于SPT調(diào)度方案與SPT+EDD調(diào)度方案，且明顯好于較優(yōu)調(diào)度方案、未聚類調(diào)度方案與未改進調(diào)度方案。多次實驗的比較結果與表4中的比較結果類似，表明本文提出的調(diào)度規(guī)則挖掘方法具有較好的穩(wěn)定性，可以保證每次提取的隨機森林調(diào)度規(guī)則的調(diào)度性能。

表5 多次實驗與較優(yōu)方案對比的表現(xiàn)

通過上述比較可以看出，通過本文提出的調(diào)度規(guī)則挖掘方法所挖掘的隨機森林調(diào)度規(guī)則得到的調(diào)度結果接近于滿足多指標篩選的較優(yōu)調(diào)度方案，且好于常用的優(yōu)先調(diào)度規(guī)則。此外，所得隨機森林調(diào)度規(guī)則的調(diào)度性能要好于未聚類數(shù)據(jù)集得到的調(diào)度規(guī)則與為改進算法得到的調(diào)度規(guī)則，說明基于擾動屬性聚類策略與改進的隨機森林算法都能提高調(diào)度規(guī)則的調(diào)度性能。由于所挖掘的隨機森林調(diào)度規(guī)則的工作原理與優(yōu)先調(diào)度規(guī)則類似，是一種實時調(diào)度方法，故一樣具有實際可操作性強，不需要對調(diào)度問題建模，不需要在發(fā)生擾動時進行重調(diào)度，適用于實際復雜動態(tài)的調(diào)度環(huán)境等優(yōu)點。因為決策樹具有計算效率高、調(diào)度知識表達直觀等特點，所以由多棵可以并行計算的決策樹構成的隨機森林調(diào)度規(guī)則也繼承了這些特點，在輸入實時信息后能快速做出調(diào)度決策。綜上所述，說明本文所提出的調(diào)度規(guī)則挖掘方法是可行且有效的。

4 結束語

針對柔性作業(yè)車間動態(tài)調(diào)度問題，本文提出了一種從具有工業(yè)大數(shù)據(jù)特點的調(diào)度相關歷史數(shù)據(jù)中挖掘調(diào)度規(guī)則的方法。該方法通過結合大數(shù)據(jù)技術的數(shù)據(jù)預處理模型，完成數(shù)據(jù)采集、清洗、整合與篩選。此外，使用基于生產(chǎn)擾動屬性的聚類策略，對不同擾動環(huán)境下做出的調(diào)度決策所產(chǎn)生的數(shù)據(jù)進行劃分，由此提高調(diào)度規(guī)則的計算效率與調(diào)度性能。在調(diào)度規(guī)則挖掘中，提出一種改進的隨機森林算法，該算法適合于從大規(guī)模、高維度、存在噪聲的調(diào)度相關歷史數(shù)據(jù)中挖掘調(diào)度規(guī)則。實驗結果表明，該挖掘方法得到的調(diào)度規(guī)則在調(diào)度性能、實際可操作性、計算效率、實時響應能力等方面都有不錯的表現(xiàn)。因為挖掘得到的隨機森林調(diào)度規(guī)則的調(diào)度性能受限于歷史調(diào)度方案的優(yōu)劣，下一步的研究可以考慮如何利用調(diào)度規(guī)則使用中產(chǎn)生的調(diào)度相關數(shù)據(jù)，使隨機森林調(diào)度規(guī)則不斷自我改善。