擾動累積下基于機器學(xué)習(xí)的重調(diào)度方式選擇

唐秋華 成麗新 張利平

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

0 引言

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

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

為此，本文提出了一種隱性擾動累積下基于學(xué)習(xí)的重調(diào)度決策機制。

1 問題描述

隱性擾動問題復(fù)雜多變，基于學(xué)習(xí)的擾動累積下重調(diào)度方式選擇問題需將隱性擾動量化，用數(shù)據(jù)表征生產(chǎn)狀況。此外，由于隱性擾動的累積效應(yīng)，需決策何時啟動重調(diào)度，進一步需確定啟用何種重調(diào)度。

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

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

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

1.2 重調(diào)度時刻點確定

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

1.3 重調(diào)度方式及其優(yōu)化決策

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

基于學(xué)習(xí)的重調(diào)度方式選擇，是在海量帶標(biāo)簽樣本的基礎(chǔ)上，通過采用機器學(xué)習(xí)等方法，決策不同擾動累積情形下的最優(yōu)重調(diào)度方式。其中，每個數(shù)據(jù)樣本均以最優(yōu)重調(diào)度決策方式作為標(biāo)簽。

1.4 擾動累積下重調(diào)度方式優(yōu)化決策模型

(1)

(2)

重調(diào)度數(shù)學(xué)模型約束條件可表示為

(3)

?k,t=T

(4)

(5)

(6)

(7)

(8)

(9)

?i,j

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

重調(diào)度方式選擇的目標(biāo)函數(shù)可表示為

(10)

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

1.5 基于學(xué)習(xí)的重調(diào)度方式選擇框架

為實現(xiàn)快速、智能、實時決策，本文構(gòu)建了圖1所示的基于數(shù)據(jù)學(xué)習(xí)的重調(diào)度方式選擇框架。具體包括重調(diào)度大樣本生成、重調(diào)度選擇模型構(gòu)建以及實際生產(chǎn)中重調(diào)度方式選擇模型應(yīng)用。

圖1 重調(diào)度方式選擇框架Fig.1 Framework of rescheduling mode selection

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

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

圖2 數(shù)據(jù)采集框架Fig.2 Framework of data acquisition

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

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

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

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

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

3 數(shù)據(jù)處理與選擇模型構(gòu)建

3.1 樣本數(shù)據(jù)清洗

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

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

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

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

3.2 樣本數(shù)據(jù)分析

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

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

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

此外，為檢驗數(shù)據(jù)的相關(guān)性，對數(shù)據(jù)進行了皮爾遜相關(guān)性分析，結(jié)果見表1。標(biāo)注*號的數(shù)據(jù)表示相關(guān)性顯著，從相關(guān)性系數(shù)可看出很多數(shù)據(jù)間呈強相關(guān)關(guān)系。

3.3 基于線性降維方法的數(shù)據(jù)降維

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

表1 皮爾遜相關(guān)性

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

(11)

(12)

j=-1,1

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

(13)

3.4 SVM分類決策模型

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

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

(14)

(15)

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

(16)

4 實驗

4.1 不同降維方式對比實驗

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

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

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

利用PCA對數(shù)據(jù)降維，前三個主成分貢獻了92.65%的信息，將數(shù)據(jù)降到三維時，兩類數(shù)據(jù)樣本的分布圖見圖5?？煽闯銎浞诸愋Ч麅?yōu)于ISOMAP，說明采用PCA更有利于不同擾動累積情形下的重調(diào)度方式樣本數(shù)據(jù)分類。

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

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

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

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

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

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

4.2 LDA-SVM實驗

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

圖9 分類準(zhǔn)確率對比Fig.9 Comparison of classification accuracy

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

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

表2 不同決策模型對比實驗(樣本規(guī)模10 000)

表3 不同規(guī)模下LDA-SVM模型預(yù)測實驗

4.3 單樣本預(yù)測實驗

實驗以6個工件，在10臺機器上加工，每個工件都要經(jīng)過6道加工工序的問題為例，表4、表5分別為魯棒優(yōu)化加工時間表、實際加工時間表。

表4 魯棒優(yōu)化的各工序加工時間表

表5 含擾動的模擬實際加工時間表

通過調(diào)度模型、遺傳算法可得到最優(yōu)原計劃調(diào)度方案。圖10給出了調(diào)度甘特圖，從圖中可看出各工序加工順序以及開始結(jié)束時刻，以及makespan。

根據(jù)原計劃調(diào)度模擬實際生產(chǎn)加工過程，可得到實際生產(chǎn)運行甘特圖(圖11)。在每個工序開始加工時刻計算各工件累積誤差時間，從而確定重調(diào)度時刻點，并在重調(diào)度時刻點結(jié)束運行啟動重調(diào)度。本次實驗將在202開始加工時刻啟動重調(diào)度。此過程中，根據(jù)樣本數(shù)據(jù)采集步驟可獲得重調(diào)度前評價因子數(shù)據(jù)。

圖10 原計劃調(diào)度圖Fig.10 Original scheduling

圖11 實際調(diào)度圖Fig.11 Actual scheduling

確定重調(diào)度時刻點后，根據(jù)重調(diào)度模型、遺傳算法得到圖12、圖13所示的右移、完全重調(diào)度方案。此過程可得到重調(diào)度后評價因子數(shù)據(jù)及決策標(biāo)簽。

圖12 右移重調(diào)度圖Fig.12 Right shift rescheduling

圖13 完全重調(diào)度圖Fig.13 Total rescheduling

以上步驟獲得了表征生產(chǎn)狀況以及影響決策標(biāo)簽的19個評價因子數(shù)據(jù)以及決策標(biāo)簽，完成了數(shù)據(jù)采集工作，具體數(shù)據(jù)見表6。為檢驗結(jié)果，表6給出了右移和完全重調(diào)度的makespan。

表6 所采集數(shù)據(jù)匯總

獲得數(shù)據(jù)后，通過LDA建立的映射可得到三維映射數(shù)據(jù)，輸入SVM得到預(yù)測結(jié)果為-1，其結(jié)果與實驗數(shù)據(jù)一致。

5 結(jié)論

(1)本文基于隨機仿真獲得大量的生產(chǎn)情形，基于數(shù)學(xué)模型和優(yōu)化算法生成對應(yīng)情形下的重調(diào)度決策樣本，提供了一種低成本的、在無法獲取海量樣本前提下的重調(diào)度決策樣本生成方法。

(2)通過分析數(shù)據(jù)特征，構(gòu)建了LDA-SVM模型，便于管理者決策。

(3)將數(shù)據(jù)仿真、智能優(yōu)化和機器學(xué)習(xí)進行結(jié)合，并用于重調(diào)度方式選擇問題中，為研究隱性擾動下的重調(diào)度問題提供了新思路。后續(xù)工作將集中在影響因子組合選擇、決策模型參數(shù)優(yōu)化等方面，以便進一步提升預(yù)測精度。