機器故障下柔性作業(yè)車間的生產(chǎn)重調(diào)度方式?jīng)Q策模型

金鵬博,唐秋華+,成麗新,張利平

(1.武漢科技大學 冶金裝備及其控制教育部重點實驗室,湖北 武漢 430081;2.武漢科技大學 機械傳動與制造工程湖北省重點實驗室,湖北 武漢 430081)

0 引言

實際生產(chǎn)中會遇到各種突發(fā)性擾動,如緊急訂單插入、原材料短缺或機器故障等[1]。其中,機器故障具有隨機、離散分布的特點,無法準確預估其發(fā)生時刻點。機器故障造成了當前機器不可用,也導致了初始調(diào)度方案失效。如不及時采取措施解決,就會造成生產(chǎn)紊亂,導致整個生產(chǎn)中斷,進而導致工件無法如期完成,對企業(yè)造成難以估量的損失。為避免此類情況的發(fā)生,決策者必須在有限的時間內(nèi)給出合理的重調(diào)度方式,快速生成調(diào)整代價小、響應迅速的調(diào)度方案,保證生產(chǎn)系統(tǒng)穩(wěn)定運行,在最大程度上挽回損失。重調(diào)度方式有多種:完全重調(diào)度、部分重調(diào)度、右移重調(diào)度等,在不同故障情形下采用何種重調(diào)度方式來生成新的調(diào)度方案,直接影響到車間生產(chǎn)穩(wěn)定性和生產(chǎn)效率,故而亟需最優(yōu)估計給定故障情形下的重調(diào)度方式,快速、經(jīng)濟、高效地生成重調(diào)度方案[2-3]。

在生產(chǎn)現(xiàn)場,由于生產(chǎn)環(huán)境復雜,現(xiàn)場調(diào)度時一般由調(diào)度員根據(jù)經(jīng)驗,主觀判斷給定故障情形的影響幅度,決策重調(diào)度方式,生成重調(diào)度方案。主觀決策具有不穩(wěn)定性,且調(diào)度員的經(jīng)驗水平不一致,難以保證重調(diào)度方式?jīng)Q策的最優(yōu)性。另一方面,制造執(zhí)行系統(tǒng)通過設(shè)備聯(lián)網(wǎng),收集車間生產(chǎn)運行信息,可實時呈現(xiàn)出生產(chǎn)現(xiàn)場的生產(chǎn)進度、目標達成度、人機料的使用狀況等信息。故而,在已知故障情形和了解車間運行狀態(tài)的前提下,可以通過重調(diào)度方式的智能決策,最大程度減少對初始調(diào)度方案的影響,提升車間作業(yè)穩(wěn)定性。

圍繞重調(diào)度方式?jīng)Q策,一些學者采用智能算法進行研究。他們可能事先預定一種重調(diào)度方式、或從多種重調(diào)度方式中隨機選一種;更多的是依據(jù)每種重調(diào)度方式,分別生成重調(diào)度方案,再根據(jù)評價標準選擇最優(yōu)。WANG等[4]將隱性干擾量定義為時間累計誤差(Time Accumulation Error,TAE),提出一種針對射頻識別技術(shù) (Radio Frequency IDentification,RFID)驅(qū)動的隱性干擾的重調(diào)度方式。喬非等[5]提出一種模糊Petri網(wǎng)模型,將該模型用做實際半導體生產(chǎn)線的重調(diào)度方式。SALADO等[6]使用文化基因算法(Memetic Algorithm,MA)找到一個減少重調(diào)度區(qū)域內(nèi)的能耗調(diào)度表,同時又可以保證時間約束,目標是通過重新安排最少任務(wù)數(shù)來盡可能恢復原始調(diào)度方案。吉衛(wèi)喜等[7]定義了多種重調(diào)度方式的判定方法、驅(qū)動機制和評價指標,使用智能算法求得多種重調(diào)度方案,再基于成本挑選出最優(yōu)重調(diào)度方案。劉壯等[8]考慮了3個決策指標,基于改進逼近理想解排序(Technique for Order Preference by Similarity to an Ideal Solution,TOPSIS),以多個可選調(diào)度方案集中選擇最優(yōu)。吳正佳等[9]根據(jù)故障機器的狀態(tài),構(gòu)建故障機器上剩余工件約束模型,提出插入重調(diào)度和完全重調(diào)度策略,使用遺傳算法求解,尋找最優(yōu)重調(diào)度方案。值得關(guān)注的是,直接指定重調(diào)度方式,與問題特征和個人經(jīng)驗的關(guān)聯(lián)很大,很難保證決策正確性;制定多種重調(diào)度方案后,再從中選優(yōu),能保證正確性,但也意味著巨大的計算工作量。

也有學者采用機器學習對重調(diào)度問題進行研究。YU[10]提出一種采用神經(jīng)網(wǎng)絡(luò)和遺傳算法的混合方法來解決擴展作業(yè)車間調(diào)度問題。其中遺傳算法用于優(yōu)化序列,神經(jīng)網(wǎng)絡(luò)用于優(yōu)化固定序列下的操作開始時間。WALTER等[11]針對車輛重調(diào)度問題,使用機器學習設(shè)計可以自動改進的算法,將其獲得的解與使用經(jīng)典算法的解進行比較,獲得最優(yōu)重調(diào)度方案。ZHAO[12]等提出機器故障下基于隨機森林的作業(yè)車間重調(diào)度方式?jīng)Q策模型。針對Job-Shop問題,使用隨機森林在兩種重調(diào)度方式中進行選擇,選擇出一個最優(yōu)的重調(diào)度方式。上述文獻主要針對重調(diào)度問題,關(guān)心的是重調(diào)度方案生成;只有少數(shù)文獻進行重調(diào)度方式?jīng)Q策,但僅在兩種重調(diào)度方式中進行了選擇。

綜上,重調(diào)度方式?jīng)Q策實質(zhì)是重調(diào)度優(yōu)化層次之上的一種模式?jīng)Q策,而現(xiàn)有研究集中在故障情形下的重調(diào)度方案生成,考慮重調(diào)度方式?jīng)Q策模型的研究相對較少。重調(diào)度方式?jīng)Q策研究主要有兩個難點:①生產(chǎn)過程中機器故障不可能頻頻發(fā)生,通過現(xiàn)實獲取全部學習樣本是不現(xiàn)實的。而在仿真時,如何產(chǎn)生數(shù)據(jù)樣本,以求覆蓋盡可能多的故障情形就顯得尤為重要。②機器故障與重調(diào)度方式之間存在某種內(nèi)部關(guān)系,如何挖掘合理的機器故障特征值來表征故障情形,以及使用機器學習將特征值與重調(diào)度方式之間的內(nèi)部關(guān)系對應起來,由此得到一個重調(diào)度方式?jīng)Q策模型,就顯得十分有必要。因此,本文提出一種融合遺傳算法與改進BP網(wǎng)絡(luò)的重調(diào)度方式?jīng)Q策模型,為不同的機器故障情形估計最優(yōu)重調(diào)度方式。

1 機器故障下重調(diào)度方式?jīng)Q策問題

機器故障是作業(yè)車間常見擾動之一。發(fā)生機器故障后,需要按照指定的重調(diào)度方式,在給定約束下對未完工或未開始工序進行重調(diào)度,以實現(xiàn)完工時間最小化、工序變動小、機器利用率大、準時交貨率最大化等目標。機器故障下柔性作業(yè)車間的重調(diào)度方式?jīng)Q策問題描述如下:

假定有N種重調(diào)度方式{n=1,…N},故障發(fā)生后尚有I個剩余工件需要加工{i=1,…I},每個工件至少有一道待加工工序,工件i的每道工序j有Mij可選機器(1≤|Mij|≤M),各工序在每臺可選機器上的加工時間不同。目標是決策合理的重調(diào)度方式,使其對加工過程產(chǎn)生的影響最小化。

在故障時刻點,故障機器存在3種情況:①故障機器正在加工,處于加工狀態(tài);②故障機器在空閑狀態(tài),后續(xù)有加工任務(wù);③故障機器在空閑狀態(tài),后續(xù)無加工任務(wù)。因為第3種不需要生產(chǎn)重調(diào)度,故不予考慮。

對于該問題,提出以下假設(shè):①故障每次只發(fā)生在一臺機器上,且故障時刻點和預計修復時間已知。②故障發(fā)生后,對故障機器立即執(zhí)行維修,無延遲,維修過程中該機器不可用。③故障發(fā)生后非故障機器上正在加工的任務(wù)繼續(xù)加工;故障機器上正在執(zhí)行的工序立即停止、已完成的部分工序報廢,該工序?qū)⒆鳛橐粋€新的工序重新執(zhí)行。

為便于對求解問題進行準確描述,引入下述符號和變量:

(1)參數(shù)

n為重調(diào)度方式(n∈N);

M為機器的集合{M={k|1,2…M};

I為工件的集合{I={i|1,2…I};

J為工序的集合{J={j|1,2…J};

L為一個極大的數(shù);

oij為第i工件的第j道工序操作;

Mij為工序oij的可選機器集合,Mij∈M;

pijk為第i工件的第j道工序在機器k的加工時間;

mnk為機器k的維護時間長度;

t0為故障時刻點;

mso為原調(diào)度方案的最大完工時間。

(2)決策變量

Xijk,重調(diào)度方案中,若第i工件的第j道工序(oij)在機器k上加工,則為1;否則為0;

Yijabk,重調(diào)度方案中,若在機器k上第i工件第j道工序的緊后工序是第a工件第b道工序,則為1;否則為0;

?ij,若操作oij在重調(diào)度方案和原調(diào)度方案選擇的加工機器不同,則為1;否則為0。

(3)關(guān)聯(lián)變量

ms為重調(diào)度方案的最大完工時間;

sij為重調(diào)度方案中第i工件第j道工序開始時間;

cij為重調(diào)度方案中第i工件第j道工序完成時間;

ci為第i工件的完成時間;

δ為最大完工時間之差;

γ為累計工序結(jié)束時間偏差值;

?為為工序變動成本。

1.1 未開始工序判定

基于初始調(diào)度方案,式(1)表示在故障時刻點判定所有工件所有工序的加工狀態(tài):已完成、正加工、未開始。對于正在加工工序,若是在非故障機上加工,待其加工完成即可,無需干預,若在故障機上加工,考慮加工質(zhì)量,已完成的部分工作直接報廢,本道工序轉(zhuǎn)變?yōu)槲撮_始工序,重新進行加工。其中,從機器方面考慮,未開始工序集(W)可分為在故障機器上(WF)和非故障機器上(Wnon-F);從受影響的工件方面考慮,未開始工序集(W)可分為直接、間接受影響的工件集(Win)和不受影響的工件集(Wnon-in)。

(1)

1.2 機器可用時間判定

在故障時刻點,若非故障機正在加工,則其可用時刻μk后移到在其正加工工序的完成時刻;若非故障機空閑,則當前可用,即μk=t0;若是故障機,則可用時刻為機器修復時間,即μk=t0+mnk。

1.3 不同重調(diào)度方式下的可用機器集

1.4 重調(diào)度方式?jīng)Q策模型

在給定故障情形下,以最大完工時間之差小、累計工序結(jié)束時間偏差值小和工序變動成本小為目標,從可選擇的重調(diào)度方式中,找出使上述3個目標綜合最優(yōu)的重調(diào)度方式。

重調(diào)度方式?jīng)Q策模型如下:

n*=argminn(α·δ+β·γ+τ·?),

(2)

δ=|ms-mso|,

(3)

(4)

(5)

右移重調(diào)度約束條件:

(6)

(7)

(8)

完全重調(diào)度約束條件:

(9)

(10)

cij≤sab-(3-Yijabk-Xijk-Xabk)·L,

?oij∈W,oab∈W,k∈Mij∩Mij。

(11)

部分重調(diào)度約束條件:

(12)

(13)

WF∪Wnon-F=W;

(14)

cij≤sab-(3-Yijabk-Xijk-Xabk)·L,

?oij∈W,oab∈W,k∈Mij∩Mij。

(15)

共有約束條件:

(16)

cij≥μk-(1-Xijk)·L;

(17)

sij≥ci,j-1, ?oi,j-1∈W;

(18)

ms≥cij,?oi,j∈W;

(19)

ms=maximaxj|oi,j∈W(cij)。

(20)

其中:式(2)表示重調(diào)度方式?jīng)Q策的目標函數(shù);式(3)～式(5)表示決策重調(diào)度方式的3個目標,分別為最大完工時間的差值、每道工序結(jié)束時間的差值和工序變動成本;式(6)表示在右移重調(diào)度中,受影響的工件的開始時間等于原始開始時間加上故障機修復時間;式(9)和式(12)表示一個工件的一道工序只能在一臺機器上加工;式(7)、式(10)、式(13)和式(14)表示一道工序的開始時間與加工時間之和等于結(jié)束時間;式(8)、式(11)和式(15)表示不能在任意一臺機器上同時進行oab和oij兩項操作;式(16)表示操作oij在重調(diào)度方案和原調(diào)度方案選擇的加工機器是否相同;式(17)表示需要重調(diào)度工序的完成時間至少等于機器可用時間;式(18)表示操作之間的優(yōu)先級關(guān)系;式(19)表示加工時間約束;式(20)表示重調(diào)度的最大完工時間。

右移重調(diào)度(Right Shift Rescheduling,RSR)調(diào)整了工序的開始和結(jié)束時間,加工順序不變,不考慮機器分配,故需用式(6)～式(8)和式(16)～式(20)描述;完全重調(diào)度(Total Rescheduling,TR)在故障時刻點針對未開始工序,生成新的加工機器表和時間表,加工時間和加工順序均有變化,故需用式(9)～式(11)和式(16)～式(20)描述;部分重調(diào)度(Partial Rescheduling,PR)針對故障機器上未開始加工工序,重新安排其加工機器,而其余機器上的加工工序的加工機器不變,加工時間和加工順序均有變化,故需用式 (12)～式(20)描述。

2 基于GA-BP神經(jīng)網(wǎng)絡(luò)的重調(diào)度方式?jīng)Q策

為實現(xiàn)不同故障情形下重調(diào)度方式的智能選擇,可基于大量數(shù)據(jù)樣本進行學習和測試,最終實現(xiàn)不同故障情形與重調(diào)度方式之間的智能估計。

然而,在現(xiàn)實的生產(chǎn)加工過程之中,圍繞故障情形的數(shù)據(jù)采集比較困難,生產(chǎn)現(xiàn)場可以提供的故障樣本數(shù)據(jù)量不足,所提供樣本也不可能涵蓋所有的故障情形,導致無法給每種故障情形提供預案。故而采用仿真手段,生成海量數(shù)據(jù)樣本,全路徑、全覆蓋不同故障情形。

后續(xù)內(nèi)容圍繞4個部分展開:重調(diào)度方式?jīng)Q策模型的學習及應用過程、機器故障下樣本集構(gòu)建、基于GA的BP網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計、基于遺傳算法(Genetic Algorithm,GA)的BP (back propagation)神經(jīng)權(quán)值閾值優(yōu)化。

2.1 重調(diào)度方式?jīng)Q策模型的學習及應用過程

重調(diào)度方式?jīng)Q策模型的具體流程如圖1所示,包括學習過程和應用過程。

(1)學習過程 在初始調(diào)度方案的基礎(chǔ)上,隨機發(fā)生機器故障,生成不同故障情形下的特征值數(shù)據(jù)?；诓煌卣{(diào)度方式,分別生成重調(diào)度方案,依據(jù)式(2)選取加權(quán)目標函數(shù)值最小的重調(diào)度方式,作為決策標簽。然后將帶有特征值-標簽的數(shù)據(jù)對輸入GA-BP重調(diào)度方式?jīng)Q策模型中,進行學習,直至分類準確率滿足需求,且趨于穩(wěn)定,結(jié)束訓練并進行測試。

(2)應用過程 在實際應用時,若發(fā)生機器故障,立即采集該故障情形下的特征值數(shù)據(jù),帶入到訓練好的GA-BP重調(diào)度方式?jīng)Q策模型中,估計到最優(yōu)的重調(diào)度方式,生成重調(diào)度方案,更新初始調(diào)度方案。

2.2 機器故障下樣本集構(gòu)建

大規(guī)模樣本生成是重調(diào)度方式學習的基礎(chǔ)。樣本數(shù)據(jù)應包括不同故障情形描述、不同重調(diào)度方式下的調(diào)度性能評價指標值及對應調(diào)度方案,并將所得到的數(shù)據(jù)進行特征和標簽處理。

(1)初始調(diào)度方案生成 重調(diào)度方案是在初始調(diào)度方案的基礎(chǔ)上調(diào)整得到的,傳統(tǒng)求解方法難以解決此類復雜工程問題,故使用智能算法求解。本文的初始調(diào)度方案使用遺傳算法優(yōu)化得到[13]。

(2)故障情形的生成 發(fā)生機器故障后,故障機器號、故障時刻點和故障修復時間已知。故障機器號k根據(jù)生成樣本數(shù)的規(guī)模,均勻分布在每一臺機器上。故障時刻點t0和故障修復時間mnk遵循均勻分布且兩者之和小于等于初始調(diào)度方案的完工時間,即t0+r≤mso。

(3)重調(diào)度方案生成 右移重調(diào)度在故障時刻點,將故障機器上受直接和間接影響的工序整體向右移動,移動過程中,各工件的加工順序和加工機器保持不變。完全重調(diào)度和部分重調(diào)度的機器分配和工件順序都需要調(diào)整,再次使用遺傳算法優(yōu)化[13],得到新的調(diào)度方案。

(4)樣本標簽的生成 根據(jù)重調(diào)度目標函數(shù),得出故障情形下的最優(yōu)重調(diào)度方式。根據(jù)權(quán)重系數(shù),分別計算3種重調(diào)度方式的目標值,選取目標值最小的重調(diào)度方式作為決策標簽。若為右移重調(diào)度則輸出1;部分重調(diào)度則輸出2;完全重調(diào)度則輸出3。

(5)樣本特征變量提取 確定了7個輸入特征,分別為:故障機器號、故障時刻點、故障修復時間、工件影響維度、工序影響維度、總剩余加工時間和故障時刻點故障機器是否正在加工。

其中,工件影響維度D指受影響加工工件數(shù)量與總工件數(shù)的比值,如式(21):

(21)

式中:αd為受影響加工工件數(shù)量,αD為加工工件總數(shù)量。

工序影響維度E指剩余未加工工序數(shù)量與總工序數(shù)的比值,如式(22):

(22)

式中:βd為剩余未加工工序的總數(shù)量,βD為加工工件總的工序數(shù)。

總剩余加工時間Tsj指從t0到mso的間隔時間,

Tsj=mso-t0。

(23)

Yzj指在故障時刻點,故障機器如果正在加工則為1,否則為0。

(24)

2.3 基于GA的BP網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計

作為一種人工神經(jīng)網(wǎng)絡(luò)模型,BP網(wǎng)絡(luò)由輸入層、隱含層和輸出層組成,其訓練過程包括信號前向傳遞和誤差反向傳播。其中前向傳遞負責計算實際值與重調(diào)度方式估計值之間的誤差,反向傳播表示根據(jù)輸出層誤差,利用梯度下降算法從后向前更新權(quán)值和閾值。式(25)～式(29)代表整個過程,f為隱含層激勵函數(shù),Yk和Ok為期望輸出和重調(diào)度方式估計輸出,ek,ωij,aj分別為誤差、權(quán)值和閾值,Hj為隱含層輸出,r為學習率。

(25)

(26)

ek=Yk-Ok,

(27)

(28)

(29)

BP網(wǎng)絡(luò)隱含層結(jié)構(gòu)的設(shè)計決定著網(wǎng)絡(luò)的規(guī)模和性能。神經(jīng)網(wǎng)絡(luò)可以認為將原始輸入數(shù)據(jù)在每一層隱含層上做多個二分類,而二分類的個數(shù)為該隱含層的節(jié)點數(shù)。神經(jīng)網(wǎng)絡(luò)的輸入層和輸出層通過隱含層連接,對于高維數(shù)據(jù)組,很難進行可視化處理。一方面,神經(jīng)網(wǎng)絡(luò)隱藏層的層數(shù)并不是越多越好。①隱藏層層數(shù)越多,需要學習的參數(shù)就越多,存在梯度爆炸與梯度消失問題,訓練時間與訓練難度就越大;②隱藏層層數(shù)越多,特征抽象程度會越高,更容易過擬合,導致對新數(shù)據(jù)集進行預測時效果較差,同時對數(shù)據(jù)量的要求也更大[14]。另一方面,在神經(jīng)網(wǎng)絡(luò)中,隱含層節(jié)點數(shù)的選擇也非常重要,它不僅對建立的神經(jīng)網(wǎng)絡(luò)模型的性能影響很大,還是訓練時出現(xiàn)“過擬合”的直接原因,會導致泛化能力差,預測精度降低[15]。

本文采用的最大隱含層層數(shù)為3層,但各層節(jié)點數(shù)范圍為[4,23],故存在20×20×20=8 000種組合。顯然,通過簡單調(diào)參很難找到滿意的隱含層結(jié)構(gòu)?？紤]到遺傳算法具有良好的全局和局部搜索能力,可以在短時間內(nèi)找到最優(yōu)解或高質(zhì)量的可行解。因此,使用遺傳算法,在如上參數(shù)范圍內(nèi)確定最優(yōu)的隱含層結(jié)構(gòu)。其中,每一個染色體代表一個隱含層,例如,[10,7,3],數(shù)組的長度代表隱含層的層數(shù),每一個數(shù)字依次表示該隱含層的節(jié)點數(shù)。具體步驟如下,其中,popsize和itermax分別代表種群數(shù)量、迭代次數(shù),New_sp代表新的種群。

算法1隱含層結(jié)構(gòu)優(yōu)化流程。

輸入:樣本集Q1;

輸出:最優(yōu)的隱含層結(jié)構(gòu)。

初始化種群

for i=1→itermax

for j=1→popsize

for k=1→ 5//訓練5次

訓練集Q11←Q1中隨機選擇70%

測試集Q12←Q1中剩余30%

whileek>θ//Q11進行訓練

計算ek,更新wlj,aj

end while

for l=1 to Q12//Q12進行測試

Ol=H·ωlj

el=Yl-Ol

end for

ρ=z-/z

end for

fitness(j)=(∑kρk)/5

end for

New_sp←選擇,交叉,變異

end for

(1)初始化 采用實數(shù)編碼的方式描述節(jié)點數(shù),其中節(jié)點數(shù)的范圍由式(30)確定,其中:g為隱藏層的節(jié)點數(shù),h為輸入層的節(jié)點數(shù),a為1到20的一個常數(shù)。故在范圍[4,23]內(nèi)隨機取整。若某一條染色體含有基因0,則表示沒有該隱含層。

(30)

(2)適應度 在測試樣本中,使用準確率作為適應度值。如式(31),其中:z為測試樣本的數(shù)量,z-為準確重調(diào)度方式估計的樣本數(shù)量。

(31)

(3)交叉 由于所選擇的兩條染色體的長度可能不同,對染色體長度低于3的染色體,補0使其長度達到3,隨機選擇交叉點進行單點交叉。例如,有兩條染色體,其中一條染色體為[9,6,0],其結(jié)構(gòu)比較好,而另一條染色體為[14,7,6],其節(jié)點個數(shù)比較好。則通過交叉第3個基因可以得到[14,7,0],包含好的隱含層結(jié)構(gòu)和對應節(jié)點個數(shù)。

(4)變異 對一條染色體有2種變異方法:①隨機選擇一個基因,在[4,23]內(nèi)隨機產(chǎn)生一個整數(shù)進行替換;②當染色體長度超過1,隨機選擇兩個基因交換位置。

2.4 基于GA的BP權(quán)值及閾值優(yōu)化

傳統(tǒng)的BP網(wǎng)絡(luò)由于權(quán)值和閾值具有隨機性,往往會陷入局部最優(yōu),模型的有效性難以保證。為了獲得更優(yōu)的重調(diào)度方式估計結(jié)果,采用遺傳算法優(yōu)化得到的最優(yōu)個體作為網(wǎng)絡(luò)的權(quán)值和閾值,在保證客觀性的同時,又可以避免陷入局部最優(yōu)。每條染色體包含網(wǎng)絡(luò)的所有權(quán)值和閾值。具體步驟如算法2所示,其中:bestfit代表每代最優(yōu)個體適應度值,c代表種群中的最優(yōu)個體。

算法2權(quán)值和閾值優(yōu)化流程。

輸入:網(wǎng)絡(luò)結(jié)構(gòu)(輸入輸出和隱含層結(jié)構(gòu));

輸出:最優(yōu)個體bestchorm。

計算染色體長度L

初始化種群

for j=1→popsize

fitness(j)=|Yk-Ok|

end for

for i=1→itermax

New_sp←選擇,交叉,變異

for j=1→popsize

fitness(j)=|Yk-Ok|

c=fitness(j)min

ifbestfit>fitness(c) then

bestfit=fitness(c)

bestchorm=c

end if

end for

end for

(1)初始化 采用實數(shù)編碼方式,由四部分組成,分別為輸入層與隱含層權(quán)值、隱含層閾值、隱含層與輸出層權(quán)值和輸出層閾值。遺傳算法求解得到的隱含層結(jié)構(gòu)為[16,5],輸入特征為7維,輸出1維,則其染色體的長度L=16×7+16+5×16+5+1×5+1=219。

(2)適應度 根據(jù)初始種群得到的網(wǎng)絡(luò)權(quán)值和閾值,使用訓練樣本進行訓練重調(diào)度方式估計,把重調(diào)度方式估計值與真實值的誤差絕對值作為適應度值。

(3)交叉 采用實數(shù)單點交叉法,隨機選擇兩條染色體,第i條和第j條在位置k交叉,如式(32);其中b為范圍[0,1]的隨機數(shù)。

rik=rik(1-b)+rjk·b。

(32)

(4)變異 由于染色體由4部分組成,故不考慮基因交換等變異方式,僅考慮單點變異,如式(33),其中:r為范圍[-1,1]的隨機數(shù)。

rik=rik(1+r)。

(33)

3 實驗

為檢驗決策器的分類效果,進行實驗驗證。首先選取單個案例,在給定的故障情形下生成特征值數(shù)據(jù)輸入決策器,驗證輸出方式是否與實際計算結(jié)果一致。然后進行大規(guī)模實驗,使用Mastrolilli M[16]文中的3組數(shù)據(jù)(mt06、abz5、la20),為每組案例生成大樣本數(shù)據(jù)集。數(shù)據(jù)來自 http://www.idsia.ch/～monaldo/fjsp.html。3個案例分別產(chǎn)生指定規(guī)模下的故障數(shù)據(jù)樣本集,驗證分類準確率。所提出算法使用MATLAB語言編寫,并在CPU為lntel(R) Core(TM) i5-4440 3.10 GHz的計算機上進行測試。

3.1 單案例重調(diào)度方式估計實驗

選取一個6工件6工序的案例,在10臺機器上加工,表1和表2為對應的機器表和加工時間表。

表1 機器表

表2 加工時間表

根據(jù)調(diào)度規(guī)則,使用遺傳算法求得初始調(diào)度方案,圖2a為初始調(diào)度方案甘特圖。

按照機器故障下樣本數(shù)據(jù)的生成方法,模擬實際加工車間故障情形,假定機器1在時刻點20發(fā)生故障,故障持續(xù)時間5,找出故障時刻點未加工工件的工序,如表3所示。

表3 工件未加工工序表

根據(jù)初始調(diào)度方案、未加工工序表和重調(diào)度時刻點,按照3種重調(diào)度方式的規(guī)則,得到如圖2b、圖2c和圖2d所示的重調(diào)度方案。

(1)輸入特征非常重要,直接影響重調(diào)度方式估計結(jié)果。為分析所選取特征值與標簽之間的重要程度關(guān)系,進行皮爾遜相關(guān)性分析,結(jié)果如表4所示。標粗體的數(shù)據(jù)值表示這兩個變量之間相關(guān)性顯著。

表4 皮爾遜相關(guān)性分析

(2)在權(quán)重系數(shù)的確定中,為規(guī)避人為主觀因素的影響,采用熵值法確定3個子目標的權(quán)重系數(shù)。使用熵值判斷子目標的離散程度,離散程度越大,該子目標對總目標的影響程度就越大。最終確定3個參數(shù)分別為α=0.30,β=0.31,τ=0.39。

(3)根據(jù)問題的規(guī)模和性質(zhì),在綜合考慮求解結(jié)果和計算時間的前提下,通過多次實驗對比,在優(yōu)化隱含層結(jié)構(gòu)中,設(shè)置種群數(shù)量為200、迭代次數(shù)為200、交叉率為0.8、變異率為0.2;求得最優(yōu)的隱含層結(jié)構(gòu)為[16,5],隱含層數(shù)為2層,第一層節(jié)點數(shù)為16,第二層節(jié)點數(shù)為5。同時在優(yōu)化權(quán)值閾值中,設(shè)置種群數(shù)量為100、迭代次數(shù)為100、交叉率為0.6、變異率為0.1。

通過3種重調(diào)度解決方案,得到的7個特征值數(shù)據(jù)如表5所示,在表中也給出3種重調(diào)度方式的目標函數(shù)值。同時,將這組樣本數(shù)據(jù)的特征值輸入訓練好的GA-BP決策模型中,所獲得的重調(diào)度方式估計輸出值為1,與實際計算得到的結(jié)果一致。

表5 模擬機器故障情形下的輸入和輸出值

傳統(tǒng)的重調(diào)度方法使用智能算法分別求解3種重調(diào)度方案,進而根據(jù)目標函數(shù)值選擇最優(yōu)重調(diào)度方案。而使用本文提出的GA-BP決策模型,快速選擇一種重調(diào)度方式,據(jù)此生成一種重調(diào)度方案。實驗結(jié)果表明,采用本文提出的先用決策模型得到最優(yōu)重調(diào)度方式,據(jù)此再生成重調(diào)度方案,該方法反應速度更快、計算量更少,能顯著提升機器故障下柔性作業(yè)車間的決策效率與反應能力。

3.2 大樣本實驗

為驗證模型的有效性,進行大規(guī)模訓練和測試。一般來說,數(shù)據(jù)集的規(guī)模會影響訓練結(jié)果,因此,本節(jié)分別在數(shù)據(jù)集為1 000、5 000、10 000、15 000和20 000的規(guī)模下進行測試。其中70%用作訓練樣本,30%用作測試樣本,訓練樣本和測試樣本隨機生成,每個樣本集獨立運行3次。同時,針對不同的數(shù)據(jù)規(guī)模,應用GA-BP與隨機森林(Random Forest,RF)[12]、決策樹 (Decision Tree,DT)、概率神經(jīng)網(wǎng)絡(luò)(Probabilistic Neural Network,PNN)作對比實驗。

PNN是徑向基網(wǎng)絡(luò)的一個分支,屬于前饋網(wǎng)絡(luò)的一種。它具有學習過程簡單、訓練速度快、分類更準確、容錯性好等優(yōu)點。從本質(zhì)上說,它屬于一種有監(jiān)督的網(wǎng)絡(luò)分類器。平滑因子設(shè)為1.5;DT本質(zhì)是一種分類方法,可以認為是if-then規(guī)則,能夠?qū)σ阎暮刑卣鲗傩院皖悇e屬性的數(shù)據(jù)進行處理,將相關(guān)度高的數(shù)據(jù)歸納到一個類別,形成擁有可讀規(guī)則的樹狀決策樹模型,具有速度快,準確性高等優(yōu)勢;RF是屬于集成學習的一種組合分類算法,核心思想是將若干個分類器(沒有強依賴關(guān)系、可并行生成)組合起來,投票得出最終的分類結(jié)果,得到一個分類性能顯著優(yōu)越的強分類器。分類器的規(guī)模為500個。

由表6可知,在3個案例集的測試中,與3種本質(zhì)為分類算法的機器學習方法相比,本文提出的GA-BP決策模型準確率更高、效果更好。得益于數(shù)據(jù)集是自生成的,數(shù)據(jù)樣本量足夠大、樣本特征在樣本空間的覆蓋程度足夠廣、各典型特征的覆蓋細致程度足夠細等優(yōu)點,可以突破每種機器學習算法在數(shù)據(jù)規(guī)模與數(shù)據(jù)合理性上的性能瓶頸。由圖3可知,隨著學習樣本數(shù)量的增加,不同算法的分類準確率都逐步上升。當樣本規(guī)模達到10 000時,GA-BP決策模型的分類準確率在3個案例中均保持在82%以上,不過當樣本數(shù)的規(guī)模擴大到20 000時,已學習到數(shù)據(jù)基本特征,盡管樣本規(guī)模擴大,準確率的提升卻較小,模型趨于穩(wěn)定。在重調(diào)度方式估計準確率上相對接近于GA-BP決策模型的是決策樹分類方法,樹的結(jié)構(gòu)隨著數(shù)據(jù)規(guī)模的增長逐漸穩(wěn)定且變得相對簡單,其余兩種機器學習方法重調(diào)度方式估計準確率相對較低。

表6 分類準確率 %

實驗同時發(fā)現(xiàn),當有很多種部分重調(diào)度方式時,如果各種重調(diào)度方式之間的差異不顯著,采用GA-BP決策模型的分類準確率會有所下降。這是由于研究問題的背景是柔性作業(yè)車間,不論是完全重調(diào)度還是部分重調(diào)度,都只能由可選加工機器承擔給定操作。該約束條件很大程度限制了機器分配,導致了調(diào)度方案的相似性,也致使分類準確率降低。表明當采用此類方法進行機器故障下柔性作業(yè)車間重調(diào)度方式?jīng)Q策時,所推薦的重調(diào)度方式數(shù)目不宜太多;各重調(diào)度方式間的差異越大,分類準確率越高。

4 結(jié)束語

本文針對機器故障下的柔性作業(yè)車間重調(diào)度方式?jīng)Q策問題,提出了融合遺傳算法與BP神經(jīng)網(wǎng)絡(luò)(GA-BP)的重調(diào)度方式?jīng)Q策模型,從3種重調(diào)度方式中估計最優(yōu)方式。

(1)通過隨機仿真產(chǎn)生大量故障情形,基于數(shù)學模型和智能算法產(chǎn)生機器故障下帶特征和標簽的大樣本數(shù)據(jù)集,提供一種成本低、在生產(chǎn)現(xiàn)場不能獲取海量樣本前提下的大規(guī)模數(shù)據(jù)生成方法。

(2)基于數(shù)據(jù)集,構(gòu)建GA-BP重調(diào)度方式?jīng)Q策模型,方便決策者管理使用。

通過將仿真、智能算法和機器學習相結(jié)合,使重調(diào)度方式?jīng)Q策更加科學合理,所作預案也更合理。后續(xù)研究可以考慮挖掘特征值,以便最大化表征問題,以及把更加科學有效的數(shù)據(jù)處理技術(shù)(例如數(shù)據(jù)降維、特征編碼等)和機器學習方法(例如關(guān)聯(lián)規(guī)則學習、強化學習等)相結(jié)合,來解決動態(tài)柔性作業(yè)車間調(diào)度問題。