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

（新疆大學(xué)機(jī)械工程學(xué)院，新疆 烏魯木齊 830047）

1 引言

柔性作業(yè)車間調(diào)度問題（Flexible job shop Scheduling Prob‐lem，F(xiàn)JSP）的特點(diǎn)是每一道工序的可選加工機(jī)器可能不唯一，相比傳統(tǒng)車間調(diào)度更加符合車間生產(chǎn)實(shí)際。然而在實(shí)際生產(chǎn)中常存在機(jī)器故障、緊急插單等多種不確定因素。機(jī)器故障作為主要的不確定因素，常導(dǎo)致實(shí)際生產(chǎn)和計(jì)劃產(chǎn)生偏差，并引起物料配送等相關(guān)生產(chǎn)環(huán)節(jié)的混亂，對(duì)生產(chǎn)過程帶來重大影響[1]。面對(duì)機(jī)器故障影響，如何制定出具有抗干擾能力魯棒性調(diào)度方案已成為生產(chǎn)調(diào)度研究的一個(gè)熱點(diǎn)。調(diào)度的魯棒性指調(diào)度在不確定環(huán)境下保持原有狀態(tài)或性能的能力，通常分為質(zhì)的魯棒性和調(diào)度穩(wěn)定魯棒性[2]。

實(shí)際制造車間機(jī)器包含退化故障與突發(fā)故障兩種失效模式[3]。因此在制定調(diào)度方案時(shí)考慮未來機(jī)器退化故障與突發(fā)故障干擾，研究機(jī)器混合故障下的柔性作業(yè)車間魯棒性調(diào)度問題對(duì)于現(xiàn)實(shí)車間調(diào)度計(jì)劃的制定與執(zhí)行具有重要指導(dǎo)意義。

針對(duì)機(jī)器故障這一不確定因素，國內(nèi)外學(xué)者做了大量研究，文獻(xiàn)[4]通過設(shè)計(jì)編程算法來插入空閑時(shí)間以應(yīng)對(duì)隨機(jī)故障對(duì)調(diào)度的擾動(dòng)；文獻(xiàn)[5]為提高調(diào)度魯棒性提出了不同的空閑時(shí)間插入策略；文獻(xiàn)[6]分析了機(jī)器隨機(jī)故障問題對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度的影響。

上述方法是通過插入緩沖時(shí)間的方式來增強(qiáng)調(diào)度的穩(wěn)定性。另一種方法則是魯棒性替代測(cè)度方法，文獻(xiàn)[7]結(jié)合流水車間的特點(diǎn)，采用前攝優(yōu)化理論，設(shè)計(jì)魯棒性代理指標(biāo)和對(duì)應(yīng)算法；文獻(xiàn)[8]考慮機(jī)器負(fù)載與故障的相關(guān)性，設(shè)計(jì)相應(yīng)測(cè)度來近似調(diào)度方案的魯棒性。文獻(xiàn)[9]提出了相對(duì)偏差魯棒性指標(biāo)和考慮空閑時(shí)間與負(fù)荷關(guān)系的魯棒性指標(biāo)。除此之外，部分研究發(fā)現(xiàn)預(yù)防性維護(hù)（Preventive Maintenance，PM）可以有效防止機(jī)器發(fā)生退化故障，并在單機(jī)[10]、流水車間[11]、柔性作業(yè)車間[12]做了大量應(yīng)用。

研究多涉及機(jī)器退化故障對(duì)調(diào)度魯棒性的影響，未綜合考慮退化故障和突發(fā)故障的混合作用對(duì)于調(diào)度魯棒性的影響，研究機(jī)器混合故障下的魯棒性調(diào)度方法對(duì)實(shí)際生產(chǎn)的指導(dǎo)更具全面性。預(yù)防性維護(hù)是根據(jù)機(jī)器的退化故障施行的，可有效改善機(jī)器的故障發(fā)生率，但無法完全避免故障的發(fā)生。

將混合故障拓展至柔性作業(yè)車間，同時(shí)考慮機(jī)器的退化故障和突發(fā)故障，根據(jù)機(jī)器因加工造成的退化故障制定預(yù)防性維護(hù)，對(duì)機(jī)器的突發(fā)故障添加適量緩沖時(shí)間，綜合考慮調(diào)度質(zhì)和解的魯棒性，提出自適應(yīng)預(yù)防性維護(hù)與緩沖插入策略，設(shè)計(jì)有效算法對(duì)集成調(diào)度問題求解，為車間提供更加穩(wěn)定的調(diào)度方案。

2 混合故障下魯棒調(diào)度方法

2.1 混合故障描述

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

式中：t—機(jī)器運(yùn)行的第t時(shí)刻；β—形狀參數(shù)；η—尺度參數(shù)；二者與機(jī)器使用時(shí)間t無關(guān)。

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

機(jī)器在t時(shí)的刻突發(fā)失效模式下的可靠度，如式（3）所示：

2.2 基于退化故障的預(yù)防性維護(hù)添加

采用預(yù)防性維護(hù)可降低車間機(jī)器發(fā)生退化故障的概率，考慮到機(jī)器的退化可靠度約束，為方便計(jì)算，將可靠度維度轉(zhuǎn)化為時(shí)間維度，對(duì)式（2）做轉(zhuǎn)換可到式（4），可計(jì)算當(dāng)機(jī)器達(dá)到可靠度閾值時(shí)對(duì)應(yīng)的機(jī)器役齡Zk′。

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

進(jìn)而在役齡閾值處添加預(yù)防性維護(hù)活動(dòng)，需要說明的是生產(chǎn)調(diào)度初步生成時(shí)，因工序約束和機(jī)器約束，導(dǎo)致計(jì)劃本身含有空閑時(shí)間。因此，預(yù)防性維護(hù)時(shí)段添加策略如下：

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

2.3 基于機(jī)器突發(fā)故障概率的緩沖時(shí)間插入

針對(duì)車間機(jī)器不可避免的突發(fā)故障，基于機(jī)器突發(fā)故障概率，在每一道工序后加入一定的緩沖時(shí)間，以吸收機(jī)器突發(fā)故障對(duì)于調(diào)度計(jì)劃的干擾。

機(jī)器k加工oij時(shí)發(fā)生突發(fā)故障的概率p[ijk]如下：

式中：aij—工序oij開工時(shí)機(jī)器k的役齡；bij—工序oij完工時(shí)機(jī)器k役齡。

機(jī)器k加工oij時(shí)發(fā)生突發(fā)故障插入的緩沖時(shí)間I[i，j，k]如下：

式中：tr—平均修復(fù)時(shí)間。

由于工件的工藝約束和機(jī)器約束，導(dǎo)致調(diào)度計(jì)劃中產(chǎn)生無法避免的空閑時(shí)間。在緩沖時(shí)間插入過程中，采取閾值法進(jìn)行靈活插入。當(dāng)所需緩沖時(shí)間小于自有空閑時(shí)間，則在當(dāng)前工序后插入緩沖。否則，不做插入操作。

3 問題描述與模型求解

3.1 柔性作業(yè)車間問題描述及假設(shè)

FJSP包含n個(gè)工件和m臺(tái)機(jī)器，各工件包含i道工序，每道工序可在一臺(tái)或多臺(tái)機(jī)器上加工，對(duì)應(yīng)的加工時(shí)間可能不同。

對(duì)所研究?jī)?nèi)容做以下假設(shè)：

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

（2）機(jī)器故障只發(fā)生在機(jī)器加工期間，修復(fù)后可繼續(xù)加工；

（3）機(jī)器發(fā)生退化故障或突發(fā)故障均采取小修，但小修時(shí)間不同。小修僅使機(jī)器恢復(fù)運(yùn)轉(zhuǎn)，不改變機(jī)器的可靠度；

（4）預(yù)防性維護(hù)不可中斷當(dāng)前工序。

3.2 數(shù)學(xué)建模

表1 符號(hào)表示及其說明Tab.1 Symbol Representation and its Description

式（7）表示目標(biāo)函數(shù)，為質(zhì)的魯棒性值與解的魯棒性值的線性加權(quán)組合，α1+α2=1；式（9）~式（10）表示在預(yù)測(cè)調(diào)度中的工序開始時(shí)間和完成時(shí)間對(duì)應(yīng)的工件工藝約束和機(jī)器加工約束；式（12）為機(jī)器的可靠度約束；式（13）~式（14）為混合故障下實(shí)際調(diào)度的工序的加工時(shí)間約束；（16）表示工序和機(jī)器一一對(duì)應(yīng)；式（18）表示實(shí)際最大完工時(shí)間。

3.3 求解算法

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

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

（2）考慮機(jī)器的可靠度約束，在種群染色體編碼中自適應(yīng)的加入預(yù)防性維護(hù)序列，得到柔性作業(yè)車間預(yù)防性維護(hù)調(diào)度；

（3）基于機(jī)器突發(fā)故障率，計(jì)算緩沖時(shí)間插入量I[i,j]，插入緩沖時(shí)間序列，得到預(yù)防性維護(hù)魯棒調(diào)度；

（4）隨機(jī)生成隨機(jī)數(shù)rand，如果rand大于退化故障概率，故障矩陣中對(duì)應(yīng)元素為1（發(fā)生退化故障），若rand 大于突發(fā)故障概率，則矩陣對(duì)應(yīng)元素為2（發(fā)生突發(fā)故障），如果同時(shí)滿足則隨機(jī)生成1或2。最終生成混合故障矩陣；

（5）計(jì)算種群個(gè)體在混合故障下的魯棒性值，進(jìn)行概率分配與適應(yīng)度排序；

（6）判斷是否達(dá)到迭代次數(shù)。得到調(diào)度模型最優(yōu)解，結(jié)束。否則執(zhí)行（7）；

（7）對(duì)種群進(jìn)行遺傳操作（選擇、交叉和變異），生成新的種群，繼續(xù)執(zhí)行（2）。

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

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

3.3.1 染色體編碼與解碼

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

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

現(xiàn)有3臺(tái)機(jī)器，3個(gè)工件，且每個(gè)工件包含3 道工序。

工件號(hào)出現(xiàn)的次數(shù)表示對(duì)應(yīng)工件的工序號(hào)，如第一個(gè)3表示工件3的第一道工序，其對(duì)應(yīng)的機(jī)器碼為1，則在可選機(jī)器集{M1，M2}的第一個(gè)機(jī)器上加工，即在M1上。

染色體先由工序序列和機(jī)器序列組成，考慮到機(jī)器的可靠度約束與突發(fā)故障概率，對(duì)初始染色體進(jìn)行擴(kuò)充，轉(zhuǎn)變成由工序、機(jī)器、維護(hù)和緩沖時(shí)間序列四部分組成的新染色體，染色體長(zhǎng)度為工序總數(shù)的四倍。

圖2中維護(hù)染色體的三個(gè)1分別表示在o23、o13、o33后添加預(yù)防性維護(hù)。相應(yīng)的緩沖染色體基因?yàn)?表示在對(duì)應(yīng)工序后添加緩沖時(shí)間，為0則不添加。工序染色體、機(jī)器染色體、維護(hù)染色體和緩沖染色體4部分編碼構(gòu)成一條完整染色體，即所求柔性作業(yè)車間問題的一個(gè)可行解。

3.3.2 個(gè)體的適應(yīng)度函數(shù)和初始種群

適應(yīng)度函數(shù)是種群個(gè)體優(yōu)劣評(píng)價(jià)的關(guān)鍵，采用適應(yīng)度函數(shù)非線性排序法進(jìn)行個(gè)體適應(yīng)度評(píng)價(jià)，適應(yīng)度值函數(shù)如下：

按上述適應(yīng)度值計(jì)算方法對(duì)種群中個(gè)體成員進(jìn)行降序排列，進(jìn)而分配概率。此時(shí)，概率則表示種群個(gè)體的適應(yīng)度值即新的個(gè)體適應(yīng)度值。

4 數(shù)值實(shí)驗(yàn)與分析

為驗(yàn)證同時(shí)考慮退化故障與突發(fā)故障兩種失效模式的混合故障下魯棒性調(diào)度方法和算法可行性，做相應(yīng)測(cè)試。

選取柔性作業(yè)車間基準(zhǔn)案例9 個(gè)，分別是Brandimarte 設(shè)計(jì)的3個(gè)案例（mk01、mk04、mk05）和hurink設(shè)計(jì)的6個(gè)案例（mt06、mt10、mt20、la01、la06、la11）。根據(jù)問題特點(diǎn)，結(jié)合文獻(xiàn)[11]，適當(dāng)調(diào)整算例參數(shù)，涉及的調(diào)度參數(shù)包含退化失效與突發(fā)失效對(duì)應(yīng)的形狀參數(shù)β、尺度參數(shù)η、故障持續(xù)時(shí)間tr，機(jī)器維護(hù)時(shí)間tp，取值，如表2所示。機(jī)器的可靠度閾值Rk′=0.85，通過式（4）可得對(duì)應(yīng)的役齡閾值Zk′=20.16。

表2 調(diào)度參數(shù)Tab.2 Scheduling Parameters

將此調(diào)度方法分別與傳統(tǒng)調(diào)度方法和考慮預(yù)防性維護(hù)的調(diào)度方法進(jìn)行比較。在傳統(tǒng)調(diào)度方法中，模型考慮退化故障，用工序加權(quán)總松弛時(shí)間之和來衡量調(diào)度方案的魯棒性，不考慮加入緩沖時(shí)間[8]。在考慮預(yù)防性維護(hù)的調(diào)度方法中，工序調(diào)度與預(yù)防性維護(hù)聯(lián)合決策，且不考慮加入緩沖時(shí)間[12]。

設(shè)置種群規(guī)模為300，交叉率為0.7，變異概率為0.1，迭代次數(shù)100。程序使用Matlab2014b，在8G內(nèi)存、2.40GHz的CPU上運(yùn)行。利用第3節(jié)step4的方式產(chǎn)生5000組機(jī)器混合故障實(shí)例，對(duì)三種方法所得的調(diào)度的最優(yōu)調(diào)度解進(jìn)行測(cè)試。

為體現(xiàn)算法的穩(wěn)定性，將算法運(yùn)行20次取平均值。分別記傳統(tǒng)調(diào)度、維護(hù)調(diào)度和所提魯棒性調(diào)度的質(zhì)的魯棒性指標(biāo)依次為MP1、MP2和MP3，解的魯棒性指標(biāo)依次為MR1、MR2和MR3。計(jì)算結(jié)果，如表3所示?？梢钥闯鲷敯粜哉{(diào)度解的期望完工時(shí)間略微高于其他兩種調(diào)度方法，然而工序完工時(shí)間偏差總和確遠(yuǎn)低于MR1和MR2。

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

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

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

表4 不同規(guī)模案例的結(jié)果對(duì)比Tab.4 Comparison of Results in Cases of Different Sizes

案例Mk01使用所提魯棒調(diào)度方法求得的最優(yōu)魯棒性調(diào)度解，案例包括6臺(tái)機(jī)器，10個(gè)工件，共計(jì)55道工序，如圖3所示。編號(hào)601為工序編號(hào)，表示6號(hào)工件的第1道工序。PM為各加工機(jī)器的預(yù)防性維護(hù)工作，灰色矩形方塊為工序后所添加的緩沖時(shí)間。

圖3 Mk01最優(yōu)調(diào)度解甘特圖Fig.3 Optimal Scheduling Solution Gantt Diagram of Mk01

5 結(jié)語

將機(jī)器在生產(chǎn)運(yùn)行中發(fā)生的混合故障引入到柔性作業(yè)車間魯棒性調(diào)度問題的模型中，綜合考慮質(zhì)的魯棒性與解的魯棒性指標(biāo)，通過算法對(duì)機(jī)器預(yù)防性維護(hù)、緩沖時(shí)間和車間調(diào)度進(jìn)行了有效的集成與優(yōu)化，最終得出柔性作業(yè)車間魯棒調(diào)度方案。對(duì)多個(gè)不同規(guī)模案例的測(cè)試驗(yàn)證了所提魯棒性調(diào)度方法是有效的，綜合指標(biāo)的改善程度相對(duì)傳統(tǒng)調(diào)度與預(yù)防性維護(hù)調(diào)度較大，且隨著問題規(guī)模的增加，改善程度也相應(yīng)提高。后期將深入研究機(jī)器混合故障下的魯棒性替代測(cè)度，以及混合故障環(huán)境下作業(yè)車間重調(diào)度時(shí)機(jī)和策略。