擾動累積下基于機器學習的重調度方式選擇

2019-03-06 03:25:58唐秋華成麗新張利平

中國機械工程 2019年4期

關鍵詞：模型

唐秋華成麗新張利平

1．武漢科技大學生產系統工程研究所，武漢，430081 2．武漢科技大學冶金裝備及其控制教育部重點實驗室，武漢，430081 3．武漢科技大學機械傳動與制造工程湖北省重點實驗室，武漢，430081

0 引言

制造系統中，存在到達時間不準及操作時間波動等不可避免的隱性擾動。短時間的隱性擾動對生產調度沒有顯著影響，但隱性擾動的持續性累積很可能會干擾生產運行，迫使生產過程無法按照原定計劃執行，而需進行重調度。目前面向隱性擾動的重調度研究較少[1]，主要原因是隱性擾動以累積的形式對生產過程進行干擾：當累積效應在可控范圍內時，無需啟用重調度；當超出受控范圍時需啟動重調度。這導致是否啟動重調度的決策成為隱性擾動區別于顯性擾動的關鍵。另外，對于選擇何種類型的重調度方式，如完全重調度(TR)、右移重調度(RSR)還是局部重調度，也需深入研究[2]。由于面向隱性擾動的重調度與具體生產情形有關，具有多變性和復雜性，故現場管理時主要采用人工調度。然而，由于生產產品類型增多、調度所需信息指數增長、調度員知識結構和經驗水平有限等，人工調度決策的穩定性、較優性很難保證，在某些情形下甚至無法保證可行性。故而，亟需研究擾動累積下基于學習的重調度方式選擇框架，以便調度員快速、準確、智能地響應生產狀況。

在不同生產情形下同時完成重調度方式智能選擇及重調度時刻點決策的研究相對較少。PETROVIC等[3]以生產持續時間和原材料缺貨量為參數描述生產過程的不確定性,建立了基于模糊推理的重調度決策系統。喬非等[4]引入最小重調度時間間隔約束，避免混合驅動策略中出現重調度觸發點間隔過小或過大的現象，保證系統實時性和穩定性。單暉[5]、陳靜云[6]、JIANG等[7]研究了基于實時工況的動態自適應重調度決策機制。劉明周等[8]提出基于損益云模型的重調度決策方法，實現重調度觸發判定及調度方案的選取。劉壯等[9]、AKKAN[10]采用被動觸發式重調度驅動規則對隱性擾動的重調度決策進行研究，提出基于改進TOPSIS的重調度決策方法。然而，現有重調度研究集中于給定擾動情形下的重調度方法和重調度策略優化，缺少具有普適性的重調度決策框架；此外，基于實際生產情形的數據獲取代價較大，而且實際上也不可能獲得完備數據集、不可能讓采集樣本覆蓋全部生產情形。

為此，本文提出了一種隱性擾動累積下基于學習的重調度決策機制。

1 問題描述

隱性擾動問題復雜多變，基于學習的擾動累積下重調度方式選擇問題需將隱性擾動量化，用數據表征生產狀況。此外，由于隱性擾動的累積效應，需決策何時啟動重調度，進一步需確定啟用何種重調度。

1.1 基于累積誤差時間的隱性擾動量化

在實際生產中，加工時長變動、生產物流銜接等，都會導致工序開始加工時刻的變化。

累積誤差時間即實時累積延遲，針對工件而言，是其工序實際/計劃開始時刻的差值。若某工件的每道工序按計劃開始，則其累積誤差為0；若提前開始，則累積誤差為負；若滯后開始，則累積誤差為正。累積誤差反映了前面各道工序執行狀況對本道工序開始時間的顯著影響，故可用累積誤差時間來量化隱性擾動的影響程度。

1.2 重調度時刻點確定

對于隱性擾動問題，判定重調度啟動與否的具體時刻點對重調度的使用頻次、車間穩定性和生產連續性具有較大的影響。當累積誤差為正時，實際調度已經顯著偏離計劃，有可能出現交貨期延遲等問題。由于魯棒優化下的原計劃調度具有一定程度的抗干擾能力，可削弱隱性擾動的影響，故將實際生產中累積誤差為正的任務開始時刻選為重調度時刻點，在一定程度保持系統穩定性并對生產狀況進行響應。

1.3 重調度方式及其優化決策

常見的重調度方式有多種，如右移重調度、完全重調度。右移重調度不改變后續工序的操作順序，但調整其開始時間；完全重調度需對操作順序和開始時間均作調整。不同的重調度方式會導致不同的制造周期和調整成本，故在不同的擾動累積情形下，要決策其最優重調度方式。

基于學習的重調度方式選擇，是在海量帶標簽樣本的基礎上，通過采用機器學習等方法，決策不同擾動累積情形下的最優重調度方式。其中，每個數據樣本均以最優重調度決策方式作為標簽。

1.4 擾動累積下重調度方式優化決策模型

(1)

(2)

重調度數學模型約束條件可表示為

(3)

?k,t=T

(4)

(5)

(6)

(7)

(8)

(9)

?i,j

其中，式(3)表示不同重調度方式下的制造周期；式(4)表示在任一機器上的加工次序t，最多可執行一道工序；式(5)表示尚需加工的任一工序oij，只能在某一機器的某一加工次序上完成；式(6)表示在任一臺機器上，只有在前一個加工次序已被分配任務的前提下，才可分配任務給隨后的加工次序；式(7)表示在任一臺機器上，前一個加工次序t的任務完成后，下一加工次序t+1任務才能開始；式(8)表示啟動重調度后，所有剩余工序的開始加工時間大于或等于t0；式(9)表示對加工同一個工件先后兩個工序的兩臺機器而言，需要排在前面的機器k的加工次序t完成后，才能開始機器k′的加工次序t′。

重調度方式選擇的目標函數可表示為

(10)

由于右移重調度只調整了工序的開始結束時間，并未調整工序順序，其模型可用式(3)、式(7)～式(10)描述；當采用完全重調度時，工序順序和加工時間都有變化，故需用式(3)～式(10)描述。

1.5 基于學習的重調度方式選擇框架

為實現快速、智能、實時決策，本文構建了圖1所示的基于數據學習的重調度方式選擇框架。具體包括重調度大樣本生成、重調度選擇模型構建以及實際生產中重調度方式選擇模型應用。

圖1 重調度方式選擇框架Fig.1 Framework of rescheduling mode selection

2 融合魯棒計劃和擾動累積的重調度樣本生成

由于設備、技術等原因，直接從實際生產中獲得所需的研究數據代價極大。本文通過模擬仿真產生實驗研究數據，將隱性擾動問題量化，用數據反映現實加工狀況。如圖2所示，所采集數據包括重調度前、重調度啟動后表征生產狀況的數據，以及重調度方式選擇標簽數據。

圖2 數據采集框架Fig.2 Framework of data acquisition

(1)加工數據生成。隱性擾動造成工序加工時長變化，從而改變原調度計劃，故可利用3種隨機數改變加工時長來生成大量加工數據以模擬實際擾動：第一種隨機數是產生擾動的工序總道數；第二種是某個工件的某道工序產生的擾動；第三種是擾動量大小。各工序魯棒閾的設定是將歸一化的原加工時長作為權重乘以(0,1)之間的隨機數。

(2)重調度前評價因素。基于遺傳算法生成魯棒優化最優調度方案，并與實際生產調度中各工序開始加工時刻對比，獲得累積誤差時間進而確定重調度時刻點。此過程中考慮從加工周期(makespan)、累積誤差時間、重調度前工序加工狀況幾個方面評估生產狀況。

(3)重調度后評價因素。分析和處理需要進入重調度的工序。此過程可用進入重調度的工序加工情況評估生產狀況。鑒于前期文獻缺乏此方面的研究，故考慮因子時應盡可能多地收集與生產狀況有關的數據。此外，限于篇幅，將在后續單樣本實例中具體展示所需因子數據。

(4)決策標簽。利用重調度模型得到右移和完全重調度的最大完工時間，若兩者差值為負，則選右移重調度并標記為1，否則為-1。

(5)獲取大樣本數據。重復以上步驟，可獲得多維樣本數據(最后一維是決策標簽)。

3 數據處理與選擇模型構建

3.1 樣本數據清洗

數據樣本的質量對數據分析以及模型建立有直接影響。以下是針對所采集數據的初步處理。

(1)缺失值。采用平均值填充方式對數據進行處理。

(2)異常值。不同于以往定義，考慮將累積誤差時間都小于0(未啟動重調度)的數據作為異常數據，此類數據生成無效，直接丟失。

(3)平衡兩類樣本。通過使用重復、自舉或合成少數類過采樣(SMOTE)等方法來生成新的稀有樣本。

3.2 樣本數據分析

不同特征數據的處理方式不一樣，故在運用數據建模之前，有必要對數據特征進行簡單分析，了解數據形態。

圖3統計了36個工序、4 000個樣本獲得各自在不同重調度時刻點的生產情形。它表明生成的樣本中，除已加工工序數{1,2,35}沒有對應樣本外，其他重調度情況都有對應樣本。此結果表明，除極端情況外，生成的樣本能有效覆蓋實際生成狀況。

圖3 樣本整體概括Fig.3 Sample generalization

此外，為檢驗數據的相關性，對數據進行了皮爾遜相關性分析，結果見表1。標注*號的數據表示相關性顯著，從相關性系數可看出很多數據間呈強相關關系。

3.3 基于線性降維方法的數據降維

數據降維一方面可降低計算代價、實現可視化、便于理解，另一方面有利于有效信息的提取綜合、無用信息的擯棄[11]。通過數據分析結果可知，樣本因子數據間相關性強、帶標簽，故考慮采用有監督的線性降維方法(linear discriminant analysis，LDA)進行數據降維。

表1 皮爾遜相關性

設重調度樣本D={(x1,y1),(x2,y2),…,(xm,ym)}，y為重調度決策標簽，yi∈{-1,1}，Nj為第j類樣本的個數，Xj為第j類樣本的集合，μj為第j類樣本的均值向量，Σj為第j類樣本的協方差矩陣,則有

(11)

(12)

j=-1,1

為保證同一重調度方式樣本的投影點盡可能接近，而不同重調度方式樣本中心之間的距離盡可能大，將LDA模型簡化為

(13)

3.4 SVM分類決策模型

分類預測方法眾多，如決策樹、貝葉斯分類器等，但不同分類器對數據特征的要求不同，如貝葉斯分類器、決策樹等不易于對樣本屬性值連續的數據進行分類預測；而神經網絡訓練分類器時，其訓練過程是使網絡全局誤差趨于極小值，易出現過擬合狀況從而使預測準確率降低；支持向量機(support vector machine, SVM)訓練的分類器在解決連續屬性分類問題上有一定成效，能在分類準確的基礎上，最大化容忍犯錯，有效避免過擬合，較好地對二類問題進行分類預測[12]。由于重調度方式選擇的樣本數據屬性連續,故考慮用SVM進行分類預測。

在SVM中，支持向量表示在線性可分的情況下，訓練數據集的樣本點中與分離超平面距離最近的樣本點的實例。定義y為重調度決策標簽,y∈{-1,1}，ω為法向量，b為偏置，n為重調度樣本總數，xi表示第i個樣本,則有

(14)

(15)

式(14)為一般計算點到直線的距離d的公式。在SVM中，式(15)描述函數能夠正確劃分點到超平面(能將兩類重調度方式樣本分隔的面)的距離dd。若定義支持向量到超平面的距離為1，即y(ωTx+b)=1,為保證模型準確，其他樣本需滿足y(ωTx+b)>1,此時SVM模型求解過程變為

(16)

4 實驗

4.1 不同降維方式對比實驗

為證實所選降維方法LDA的有效性，以非線性降維ISOMAP和無監督線性降維主成分分析(principal component analysis, PCA)為代表，進行對比實驗。

其中，ISOMAP是一種等距映射算法。利用ISOMAP降維時，從二維到三維殘差方差下降最快，將數據降到三維時，兩類數據樣本分布見圖4。

圖4 ISOMAP降維Fig.4 Dimension reduction of ISOMAP

利用PCA對數據降維，前三個主成分貢獻了92.65%的信息，將數據降到三維時，兩類數據樣本的分布圖見圖5。可看出其分類效果優于ISOMAP，說明采用PCA更有利于不同擾動累積情形下的重調度方式樣本數據分類。

圖5 PCA降維Fig.5 Dimension reduction of PCA

對比線性無監督降維PCA與線性有監督降維LDA可知， PCA方法不考慮數據標簽，只選擇樣本點投影具有最大方差的方向，而LDA使得同類樣例投影點盡可能接近、異類樣例投影點盡可能遠離，因此選用LDA對此類數據降維更有利于樣本的分類。

圖6是基于LDA將高維大樣本數據降到一維時的兩類樣本分布圖，由圖可看出第二類樣本的數值基本小于第一類樣本，兩類樣本基本可區分；圖7是采用LDA將數據降到二維時兩類樣本的分布圖，由圖可看出樣本點間雖有融合，但大體可區分。由于將數據降到3維以上時出現復數，其降維效果將以分類準確率的形式量化。

圖7 二維樣本分布圖Fig.7 2D sample distribution map

為精確比較降維效果好壞，基于4 000個樣本，用不同降維方法處理的數據訓練了三維輸入下的SVM模型，并進行預測。其中，訓練樣本與測試樣本比例為7∶3。從圖8可看出，直接用原始高維數據建立SVM模型，模型準確率83.8%，但數據維度高，存儲和計算代價高；基于PCA的SVM模型，準確率為0.788，數據儲存等代價降低，但可能由于損失了數據精度，準確率下降；基于ISOMAP的SVM模型，準確率為0.62；而利用LDA方法對數據處理后，模型準確率為83.7%，既去除了高維數據中的冗余信息，降低了計算代價，又保證了數據精度。

圖8 不同降維方法的準確率Fig.8 Accuracy of different dimension reduction methods

4.2 LDA-SVM實驗

為測試LDA降維維度對LDA-SVM模型的影響，實驗中，從4 000組訓練樣本中隨機抽取2 800組訓練模型。訓練模型輸入由LDA處理得到，測試輸入由LDA降維時主特征值對應特征向量映射得到，模型輸出為對應決策標簽。由圖9可看出，基于LDA降維數據的SVM模型分類準確率在80%以上。與一維特征量相比，二維特征量表達的信息更多，分類準確率提升0.027。但數據維度降到三維以上時，由于數據冗余等干擾，分類準確率略有下降。

圖9 分類準確率對比Fig.9 Comparison of classification accuracy

確定降維方式及最佳降維維度后，為測試LDA-SVM組合模型的有效性，在樣本規模為10 000的實驗環境下進行了表2所示實驗。其中，訓練樣本與測試樣本比例為7∶3。實驗結果顯示，同一樣本下LDA-SVM預測準確率最高。

為進一步測試LDA-SVM模型的穩定性，需要進行不同樣本規模下的模型測試實驗。表3中，所有實驗的訓練、測試樣本比例為7∶3，數據維度為2。表3表明，隨著樣本規模的改變，模型準確率稍有變動，但總體準確率保持在83%。此外，樣本規模為4 000時，模型已學習到數據基本特征，盡管樣本規模進一步擴大，準確率卻難有提升，模型基本穩定。