機器混合故障下柔性作業車間魯棒調度方法

侯婭楠，袁逸萍，巴智勇，李 明

（新疆大學機械工程學院，新疆 烏魯木齊 830047）

1 引言

柔性作業車間調度問題（Flexible job shop Scheduling Prob‐lem，FJSP）的特點是每一道工序的可選加工機器可能不唯一，相比傳統車間調度更加符合車間生產實際。然而在實際生產中常存在機器故障、緊急插單等多種不確定因素。機器故障作為主要的不確定因素，常導致實際生產和計劃產生偏差，并引起物料配送等相關生產環節的混亂，對生產過程帶來重大影響[1]。面對機器故障影響，如何制定出具有抗干擾能力魯棒性調度方案已成為生產調度研究的一個熱點。調度的魯棒性指調度在不確定環境下保持原有狀態或性能的能力，通常分為質的魯棒性和調度穩定魯棒性[2]。

實際制造車間機器包含退化故障與突發故障兩種失效模式[3]。因此在制定調度方案時考慮未來機器退化故障與突發故障干擾，研究機器混合故障下的柔性作業車間魯棒性調度問題對于現實車間調度計劃的制定與執行具有重要指導意義。

針對機器故障這一不確定因素，國內外學者做了大量研究，文獻[4]通過設計編程算法來插入空閑時間以應對隨機故障對調度的擾動；文獻[5]為提高調度魯棒性提出了不同的空閑時間插入策略；文獻[6]分析了機器隨機故障問題對多目標柔性作業車間調度的影響。

上述方法是通過插入緩沖時間的方式來增強調度的穩定性。另一種方法則是魯棒性替代測度方法，文獻[7]結合流水車間的特點，采用前攝優化理論，設計魯棒性代理指標和對應算法；文獻[8]考慮機器負載與故障的相關性，設計相應測度來近似調度方案的魯棒性。文獻[9]提出了相對偏差魯棒性指標和考慮空閑時間與負荷關系的魯棒性指標。除此之外，部分研究發現預防性維護（Preventive Maintenance，PM）可以有效防止機器發生退化故障，并在單機[10]、流水車間[11]、柔性作業車間[12]做了大量應用。

研究多涉及機器退化故障對調度魯棒性的影響，未綜合考慮退化故障和突發故障的混合作用對于調度魯棒性的影響，研究機器混合故障下的魯棒性調度方法對實際生產的指導更具全面性。預防性維護是根據機器的退化故障施行的，可有效改善機器的故障發生率，但無法完全避免故障的發生。

將混合故障拓展至柔性作業車間，同時考慮機器的退化故障和突發故障，根據機器因加工造成的退化故障制定預防性維護，對機器的突發故障添加適量緩沖時間，綜合考慮調度質和解的魯棒性，提出自適應預防性維護與緩沖插入策略，設計有效算法對集成調度問題求解，為車間提供更加穩定的調度方案。

2 混合故障下魯棒調度方法

2.1 混合故障描述

車間中機器發生的故障類型包含退化故障和突發故障，一般認為這兩種故障的失效函數服從不同參數的二參數威布爾分布[2]，該分布的概率密度函數，如式（1）所示：

式中：t—機器運行的第t時刻；β—形狀參數；η—尺度參數；二者與機器使用時間t無關。

機器在t時的刻退化失效模式下的可靠度，如式（2）所示：

機器在t時的刻突發失效模式下的可靠度，如式（3）所示：

2.2 基于退化故障的預防性維護添加

采用預防性維護可降低車間機器發生退化故障的概率，考慮到機器的退化可靠度約束，為方便計算，將可靠度維度轉化為時間維度，對式（2）做轉換可到式（4），可計算當機器達到可靠度閾值時對應的機器役齡Zk′。

式中：Rk′—可靠度閾值。

進而在役齡閾值處添加預防性維護活動，需要說明的是生產調度初步生成時，因工序約束和機器約束，導致計劃本身含有空閑時間。因此，預防性維護時段添加策略如下：

判斷預防性維護的位置狀態。若在加工連續的序列中，這時在此工序前直接插入，后續序列向右后移，以防止機器的可靠度超出閾值；若處于較小空閑時間中，則不能夠完全容納正常維護活動所需時間，需向右擴充，后續序列向右移動；當在完全空閑時間中，安排在前一工序之后，不影響后續加工任務。

2.3 基于機器突發故障概率的緩沖時間插入

針對車間機器不可避免的突發故障，基于機器突發故障概率，在每一道工序后加入一定的緩沖時間，以吸收機器突發故障對于調度計劃的干擾。

機器k加工oij時發生突發故障的概率p[ijk]如下：

式中：aij—工序oij開工時機器k的役齡；bij—工序oij完工時機器k役齡。

機器k加工oij時發生突發故障插入的緩沖時間I[i，j，k]如下：

式中：tr—平均修復時間。

由于工件的工藝約束和機器約束，導致調度計劃中產生無法避免的空閑時間。在緩沖時間插入過程中，采取閾值法進行靈活插入。當所需緩沖時間小于自有空閑時間，則在當前工序后插入緩沖。否則，不做插入操作。

3 問題描述與模型求解

3.1 柔性作業車間問題描述及假設

FJSP包含n個工件和m臺機器，各工件包含i道工序，每道工序可在一臺或多臺機器上加工，對應的加工時間可能不同。

對所研究內容做以下假設：

（1）工件的加工工藝流程是已知的；

（2）機器故障只發生在機器加工期間，修復后可繼續加工；

（3）機器發生退化故障或突發故障均采取小修，但小修時間不同。小修僅使機器恢復運轉，不改變機器的可靠度；

（4）預防性維護不可中斷當前工序。

3.2 數學建模

表1 符號表示及其說明Tab.1 Symbol Representation and its Description

式（7）表示目標函數，為質的魯棒性值與解的魯棒性值的線性加權組合，α1+α2=1；式（9）~式（10）表示在預測調度中的工序開始時間和完成時間對應的工件工藝約束和機器加工約束；式（12）為機器的可靠度約束；式（13）~式（14）為混合故障下實際調度的工序的加工時間約束；（16）表示工序和機器一一對應；式（18）表示實際最大完工時間。

3.3 求解算法

采用改進的遺傳算法來進行模型求解，算法步驟如下：

（1）參數初始化，采用隨機初始化方法，基于工序和機器編碼方式，生成初始種群；

（2）考慮機器的可靠度約束，在種群染色體編碼中自適應的加入預防性維護序列，得到柔性作業車間預防性維護調度；

（3）基于機器突發故障率，計算緩沖時間插入量I[i,j]，插入緩沖時間序列，得到預防性維護魯棒調度；

（4）隨機生成隨機數rand，如果rand大于退化故障概率，故障矩陣中對應元素為1（發生退化故障），若rand 大于突發故障概率，則矩陣對應元素為2（發生突發故障），如果同時滿足則隨機生成1或2。最終生成混合故障矩陣；

（5）計算種群個體在混合故障下的魯棒性值，進行概率分配與適應度排序；

（6）判斷是否達到迭代次數。得到調度模型最優解，結束。否則執行（7）；

（7）對種群進行遺傳操作（選擇、交叉和變異），生成新的種群，繼續執行（2）。

算法具體操作，如圖1所示。

圖1 算法流程圖Fig.1 Framework of the Algorithm

3.3.1 染色體編碼與解碼

由于FJSP中各工序可選加工機器不唯一，要解決的問題包括：確定工序的機器選擇；確定各機器工序的加工順序；確定預防性維護位置；確定緩沖大小和位置；因此采用基于工序和機器的四層編碼方式，染色體編碼方式圖，如圖2所示。

圖2 染色體編碼方式圖Fig.2 Chromosome Coding Pattern

現有3臺機器，3個工件，且每個工件包含3 道工序。

工件號出現的次數表示對應工件的工序號，如第一個3表示工件3的第一道工序，其對應的機器碼為1，則在可選機器集{M1，M2}的第一個機器上加工，即在M1上。

染色體先由工序序列和機器序列組成，考慮到機器的可靠度約束與突發故障概率，對初始染色體進行擴充，轉變成由工序、機器、維護和緩沖時間序列四部分組成的新染色體，染色體長度為工序總數的四倍。

圖2中維護染色體的三個1分別表示在o23、o13、o33后添加預防性維護。相應的緩沖染色體基因為1表示在對應工序后添加緩沖時間，為0則不添加。工序染色體、機器染色體、維護染色體和緩沖染色體4部分編碼構成一條完整染色體，即所求柔性作業車間問題的一個可行解。

3.3.2 個體的適應度函數和初始種群

適應度函數是種群個體優劣評價的關鍵，采用適應度函數非線性排序法進行個體適應度評價，適應度值函數如下：

按上述適應度值計算方法對種群中個體成員進行降序排列，進而分配概率。此時，概率則表示種群個體的適應度值即新的個體適應度值。

4 數值實驗與分析

為驗證同時考慮退化故障與突發故障兩種失效模式的混合故障下魯棒性調度方法和算法可行性，做相應測試。

選取柔性作業車間基準案例9 個，分別是Brandimarte 設計的3個案例（mk01、mk04、mk05）和hurink設計的6個案例（mt06、mt10、mt20、la01、la06、la11）。根據問題特點，結合文獻[11]，適當調整算例參數，涉及的調度參數包含退化失效與突發失效對應的形狀參數β、尺度參數η、故障持續時間tr，機器維護時間tp，取值，如表2所示。機器的可靠度閾值Rk′=0.85，通過式（4）可得對應的役齡閾值Zk′=20.16。

表2 調度參數Tab.2 Scheduling Parameters

將此調度方法分別與傳統調度方法和考慮預防性維護的調度方法進行比較。在傳統調度方法中，模型考慮退化故障，用工序加權總松弛時間之和來衡量調度方案的魯棒性，不考慮加入緩沖時間[8]。在考慮預防性維護的調度方法中，工序調度與預防性維護聯合決策，且不考慮加入緩沖時間[12]。

設置種群規模為300，交叉率為0.7，變異概率為0.1，迭代次數100。程序使用Matlab2014b，在8G內存、2.40GHz的CPU上運行。利用第3節step4的方式產生5000組機器混合故障實例，對三種方法所得的調度的最優調度解進行測試。

為體現算法的穩定性，將算法運行20次取平均值。分別記傳統調度、維護調度和所提魯棒性調度的質的魯棒性指標依次為MP1、MP2和MP3，解的魯棒性指標依次為MR1、MR2和MR3。計算結果，如表3所示。可以看出魯棒性調度解的期望完工時間略微高于其他兩種調度方法，然而工序完工時間偏差總和確遠低于MR1和MR2。

表3 三種方法的魯棒性指標比較Tab.3 Comparison of Robustness Indexes of Three Methods

為了更好的定量評價本文調度方法的改善程度，采用GJL（改進率）來衡量算法的有效性，TtP+R、TpP+R、TrP+R分別表示三種方法的解的總目標函數值，GJL1?MP=(MP3?MP1)/MP1表示魯棒性調度方法相對于傳統調度方法在質的魯棒性上下降的百分比。GJL1?MR=(MR3?MR1)/MR1則表示相對于傳統調度方法在解的魯棒性上下降的百分比。所提方法相比傳統調度方法在綜合魯棒性指標上的改善程度用GJL1?TP+R=(GJL1?MP+GJL1?MR)/2表示，同上可得相對于預防維護調度方法的改進率GJL2?MP、GJL2?MR、GJL2?TP+R。

表4給出了當α1=0.5，α2=0.5時，三種算法得到的數據結果。根據表4中數據可得，魯棒性調度解相比傳統方法和維護調度雖然在質的魯棒性改善程度上下降了平均4.6%和2.2%；但卻使調度解的解的魯棒性提高了大約45.7%和30%，在總目標上分別改善了25.2%和16.1%。這說明考慮維護與緩沖的魯棒調度方法對于機器混合故障所造成的工序加工時間波動具有一定的免疫功能。還可以發現隨著案例規模的增加，改善程度也相對增加。

表4 不同規模案例的結果對比Tab.4 Comparison of Results in Cases of Different Sizes

案例Mk01使用所提魯棒調度方法求得的最優魯棒性調度解，案例包括6臺機器，10個工件，共計55道工序，如圖3所示。編號601為工序編號，表示6號工件的第1道工序。PM為各加工機器的預防性維護工作，灰色矩形方塊為工序后所添加的緩沖時間。

圖3 Mk01最優調度解甘特圖Fig.3 Optimal Scheduling Solution Gantt Diagram of Mk01

5 結語

將機器在生產運行中發生的混合故障引入到柔性作業車間魯棒性調度問題的模型中，綜合考慮質的魯棒性與解的魯棒性指標，通過算法對機器預防性維護、緩沖時間和車間調度進行了有效的集成與優化，最終得出柔性作業車間魯棒調度方案。對多個不同規模案例的測試驗證了所提魯棒性調度方法是有效的，綜合指標的改善程度相對傳統調度與預防性維護調度較大，且隨著問題規模的增加，改善程度也相應提高。后期將深入研究機器混合故障下的魯棒性替代測度，以及混合故障環境下作業車間重調度時機和策略。