杜陽(yáng)宇，張 楓

(武漢理工大學(xué) 機(jī)電工程學(xué)院，武漢 430070)

傳統(tǒng)的柔性作業(yè)車(chē)間調(diào)度,往往根據(jù)經(jīng)驗(yàn)對(duì)設(shè)備進(jìn)行周期性維護(hù)。然而，在實(shí)際的調(diào)度過(guò)程中,每個(gè)設(shè)備具體工作時(shí)間不等、損壞狀況不一，這種維護(hù)策略不僅會(huì)造成人力物力的浪費(fèi)，并且還可能導(dǎo)致維護(hù)活動(dòng)與調(diào)度計(jì)劃的沖突，影響整個(gè)調(diào)度方案的執(zhí)行。因此，需要將二者進(jìn)行集成優(yōu)化。很多國(guó)內(nèi)外學(xué)者對(duì)這一問(wèn)題進(jìn)行了研究：馬慧民等[1]采用預(yù)防性維護(hù)和小修結(jié)合的維護(hù)策略，建立了調(diào)度和維護(hù)的聯(lián)合決策模型；崔維偉等[2]以單機(jī)系統(tǒng)為研究對(duì)象，考慮設(shè)備和工件的墮化效應(yīng),建立以完工時(shí)間最小和維修成本最低的多目標(biāo)聯(lián)合優(yōu)化模型；劉永等[3]提出的作業(yè)車(chē)間調(diào)度和維護(hù)的集成調(diào)度模型，維護(hù)周期和維護(hù)時(shí)間都是基于機(jī)器役齡約束的；張思源等[4]提出了基于NEH(nawaz enscore ham)思想的快速啟發(fā)式算法來(lái)解決考慮設(shè)備維護(hù)的流水車(chē)間調(diào)度問(wèn)題；金鋒赫等[5]等提出了基于設(shè)備可用時(shí)間的裝配作業(yè)車(chē)間調(diào)度規(guī)則；Khatami等[6]提出了維護(hù)活動(dòng)的次數(shù)和時(shí)間間隔不固定的協(xié)調(diào)模型；Al-Hinai等[7]則是在使用重調(diào)度方法時(shí),定義并比較了預(yù)測(cè)調(diào)度的魯棒性和穩(wěn)定性,提出了一種兩階段的混合遺傳算法(hybrid genetic algorithm,HGA)；Jabbarizadeh等[8]考慮混合車(chē)間作業(yè)和基于設(shè)備可用性約束的預(yù)防性維護(hù),使用了3種啟發(fā)式算法求解。

上述文獻(xiàn)在研究調(diào)度和預(yù)防性維護(hù)的集成問(wèn)題時(shí)，主要引入可靠模型作為控制因子，設(shè)備可靠度低于臨界值進(jìn)行維護(hù)，維護(hù)之后可靠度恢復(fù)如初。在實(shí)際調(diào)度作業(yè)中，任何一道工序的加工都不允許中斷，設(shè)備可靠度達(dá)到臨界值可能發(fā)生在連續(xù)作業(yè)的不同時(shí)期，因此作業(yè)完工之后設(shè)備的實(shí)際情況往往是不一致的，部分設(shè)備可能因?yàn)榭煽慷冗h(yuǎn)低于臨界值而發(fā)生嚴(yán)重故障。因此，筆者以柔性作業(yè)車(chē)間為研究目標(biāo)，假設(shè)設(shè)備發(fā)生故障的時(shí)間服從威布爾分布，建立以可靠度區(qū)間為決策變量，以最小化完工時(shí)間為目標(biāo)的集成模型。

1 問(wèn)題描述

1.1 柔性作業(yè)車(chē)間問(wèn)題描述

柔性作業(yè)車(chē)間調(diào)度問(wèn)題描述如下：車(chē)間有m臺(tái)加工設(shè)備，n個(gè)待加工工件，每個(gè)工件有一道或多道加工工序，每道工序都有一個(gè)或者多個(gè)設(shè)備可以加工，不同工件之間沒(méi)有加工順序約束，同一工件的不同工序之間存在加工順序約束，同一設(shè)備同一時(shí)刻只能加工一道工序。本文所研究的問(wèn)題基于如下假設(shè)：

(1)零時(shí)刻，所有設(shè)備均可用；

(2)加工過(guò)程不允許被中斷；

(3)維護(hù)活動(dòng)過(guò)程設(shè)備停工；

(4)維護(hù)活動(dòng)在工序完工之后進(jìn)行；

(5)維護(hù)后設(shè)備恢復(fù)到開(kāi)始加工時(shí)的狀態(tài)。

1.2 設(shè)備維護(hù)描述

隨著設(shè)備的運(yùn)轉(zhuǎn)，役齡不斷增大，設(shè)備可靠度就會(huì)逐漸下降，因此要對(duì)設(shè)備進(jìn)行維護(hù)活動(dòng)。假設(shè)生產(chǎn)設(shè)備的故障服從威布爾分布λ(t)，如式(1)所示：

(1)

式中：β(β>1)為形狀參數(shù)，不同的取值決定不同的分布曲線(xiàn)形狀；η為尺度參數(shù)，不同取值影響分布曲線(xiàn)的縮放比例[9]。t為設(shè)備役齡。

可靠度函數(shù)R(t)如式(2)所示：

(2)

筆者引入可靠度閾值區(qū)間[D[s]，D[l]]作為設(shè)備維護(hù)的控制因子。D[s]為設(shè)備可靠度的起始值，D[l]為設(shè)備可靠度的臨界值。設(shè)備可靠度和役齡的關(guān)系如圖1所示，[T[s],T[l]]為可靠度區(qū)間對(duì)應(yīng)的設(shè)備役齡區(qū)間。

圖1 可靠度區(qū)間維護(hù)策略示意圖

設(shè)備維護(hù)的條件分為以下兩種情況：

(1)工序Oij完工之后，設(shè)備k的役齡t∈[T[s],T[l]]，設(shè)備狀態(tài)處于圖1中的區(qū)域A；

(2)假設(shè)Oqh和Oij是設(shè)備k上將要加工的相鄰的兩道工序(Oqh在前)，工序Oqh完工之后，設(shè)備k的役齡tT[l]，那么就必須在工序Oqh之后進(jìn)行維護(hù)，此時(shí)設(shè)備狀態(tài)處于圖1中的區(qū)域B。

在區(qū)域A，B中，設(shè)備的可靠度不同，損壞程度也不一致，因此維護(hù)時(shí)間符合不同的函數(shù)關(guān)系如式(3)，a為基礎(chǔ)時(shí)間，b為系數(shù)。

(3)

在式(3)中，設(shè)備役齡處于區(qū)域A時(shí)，維護(hù)時(shí)間長(zhǎng)于基礎(chǔ)時(shí)間，且時(shí)間函數(shù)是關(guān)于役齡差值的二次函數(shù)；設(shè)備役齡處于區(qū)域B時(shí)，維護(hù)時(shí)間短于基礎(chǔ)時(shí)間，且時(shí)間函數(shù)是關(guān)于役齡差值的一次函數(shù)。當(dāng)設(shè)備可靠度低于可靠度界限時(shí)，設(shè)備需要更多的時(shí)間維護(hù)，才能恢復(fù)役齡為0時(shí)刻的可靠度。

D[l]為可靠度臨界值，不允許可靠度低于D[l]，否則會(huì)導(dǎo)致設(shè)備出現(xiàn)嚴(yán)重故障。

1.3 設(shè)備退化描述

設(shè)備在不斷的加工過(guò)程中會(huì)產(chǎn)生退化。工序Oij在設(shè)備k上的退化函數(shù)如式(4)所示，實(shí)際加工時(shí)間如式(5)所示。

×?

(4)

uijk=pijk+αkpijk

(5)

式中：Tijk為工序Oij加工完成時(shí)設(shè)備的役齡；pijk為工序Oij在設(shè)備k上的標(biāo)準(zhǔn)加工時(shí)間；αk為退化因子；?為退化權(quán)值。

2 模型建立

根據(jù)最大完工時(shí)間最小的要求及相應(yīng)的約束條件建立如下數(shù)學(xué)模型：

(6)

s.t.ei(j-1)≤sij

(7)

(8)

(9)

(10)

式(6)為目標(biāo)函數(shù)，最大完工時(shí)間最??；式(7)表示兩道工序之間的約束；式(8)表示加工時(shí)間的約束；式(9)表示設(shè)備的役齡約束；式(10)表示加工約束。

3 算法設(shè)計(jì)

筆者采用改進(jìn)的遺傳算法，在傳統(tǒng)遺傳算法的基礎(chǔ)上結(jié)合了基于工件順序的鄰域搜索算法，同時(shí)優(yōu)化初始解，加快了收斂的速度。

遺傳算法全局搜索能力較強(qiáng)，不僅可以快速地將解空間中的全體解搜索出，而且不會(huì)出現(xiàn)局部最優(yōu)解快速下降的情況。但是遺傳算法的局部搜索能力較差，因此單純的遺傳算法比較費(fèi)時(shí)，在算法后期搜索效率較低。為了提高遺傳算法的局部搜索能力，筆者將鄰域搜索算法引入遺傳算法中，構(gòu)建出改進(jìn)的遺傳算法，可以有效提高收斂速度。算法流程如圖2所示。

圖2 算法流程圖

3.1 編碼和解碼

筆者采用基于工序、設(shè)備和維護(hù)的3層基因編碼方式，每層基因長(zhǎng)度均為工序總數(shù)。

第一層基因確定工序順序。每個(gè)工件的工序均由該工件號(hào)表示，第幾次出現(xiàn)表示第幾道工序。如基因段[1 3 5 2 3 5 2]表示工序O11,O31,O51,O21,O32,O52,O22。

第二層基因確定加工設(shè)備。將所有工件的工序依次排列，每道工序?qū)?yīng)一個(gè)加工設(shè)備。如工件1有四道工序，工件2有3道工序，則[1 2 1 3 5 3 2]表示O11,O12,O13,O14的加工設(shè)備為1,2,1,3；O21,O22,O23的加工設(shè)備為5,3,2。

第三層基因確定工序完成之后是否需要維護(hù)以及維護(hù)的時(shí)間。若維護(hù)，則是對(duì)應(yīng)的維護(hù)時(shí)間，否則為0。

解碼時(shí)根據(jù)前兩層編碼確定調(diào)度順序和使用設(shè)備，根據(jù)第三層基因插入維護(hù)活動(dòng)及維護(hù)時(shí)間。

3.2 初始化

遺傳算法的初始解優(yōu)劣直接影響收斂的速度和最終解的質(zhì)量，采用基于設(shè)備時(shí)間最短的方法[10-11]提高初始解的質(zhì)量。

(1)將所有工件工序依次排列生成一個(gè)序列，把生成的序列隨機(jī)亂序排列，生成第一層基因的初始編碼,即工序順序編碼，如[1 2 1 3 5 3 …]。

(2)依據(jù)已經(jīng)確認(rèn)的工序順序編碼，安排第一道工序的加工設(shè)備。首先在可以加工該工序的所有設(shè)備中選取時(shí)間最短的設(shè)備分配給該工序，假設(shè)加工時(shí)間為t。然后所有工序在各自可加工設(shè)備上的加工時(shí)間全部增加t。

(3)每分配一道工序，后續(xù)工序?qū)?yīng)的設(shè)備就要增加該工序的加工時(shí)間，再選擇加工時(shí)間最短的設(shè)備。依次為每道工序選擇加工設(shè)備，生成第二層基因的初始解。假設(shè)工序[1 2 1 3 5 3]在3個(gè)設(shè)備上的加工時(shí)間如圖3所示，則這6道工序選擇的設(shè)備依次是1,3,2,2,2,3。

圖3 設(shè)備時(shí)間最短法選擇設(shè)備流程

(4)第三層基因的初始解全部設(shè)置為0。至此，3部分的基因初始化完成。

3.3 遺傳算子

3.3.1 選擇算子

選擇操作是把父代中的一部分染色體選中并產(chǎn)生子代染色體,適應(yīng)度越大的個(gè)體越有可能被選中。筆者采用錦標(biāo)賽法來(lái)進(jìn)行子代的選擇[12],目標(biāo)值即為適應(yīng)值。

3.3.2 交叉算子

第一層基因編碼,為避免出現(xiàn)非法子串的產(chǎn)生,隨機(jī)選擇兩個(gè)交叉點(diǎn)a,b,兩個(gè)父代P1,P2,在交叉點(diǎn)之內(nèi)的基因進(jìn)行互換交叉,生成兩個(gè)新的子代C1,C2。

第二層基因編碼采用POX的交叉方法,生成子代染色體C1,C2，具體步驟如下：

(1)隨機(jī)生成兩個(gè)父代交叉點(diǎn)如圖4所示。

圖4 POX交叉(一)

(2)交叉父代染色體中a,b之間的基因,分別復(fù)制給兩個(gè)子代染色體C2,C1,結(jié)果如圖5所示。

圖5 POX交叉(二)

(3)將P1中與C2ab段基因相同的編碼刪除；將P2中與C1ab段基因相同的編碼刪除,結(jié)果如圖6所示。

圖6 POX交叉(三)

(4)將P1中剩余的基因編碼依次填入C2的空余部分；P2,C1執(zhí)行相同的操作,結(jié)果如圖7所示。

圖7 POX交叉(四)

第三層基因編碼記錄機(jī)器的維護(hù)情況,不參與交叉和變異。

3.3.3 變異算子

遺傳算法解決柔性作業(yè)車(chē)間調(diào)度問(wèn)題時(shí)常使用的變異算子有插入變異、逆轉(zhuǎn)變異和交換變異等。

為防止出現(xiàn)違法的染色體,第一部分基因編碼,隨機(jī)選擇一個(gè)變異點(diǎn),再重新選擇一個(gè)不同的機(jī)器子集；第二部分則從染色體中隨機(jī)選取兩個(gè)變異點(diǎn),互換兩個(gè)位置的基因。

3.4 鄰域搜索算法

筆者對(duì)染色體中第一層基因和第二層基因采用不同的搜索策略。

(1)針對(duì)第一層基因，采用基于工件交換的搜索策略。隨機(jī)選擇兩個(gè)不同的工件，將一條染色體中兩個(gè)工件的所有工序交換位置。如果工序數(shù)量不一致，則工序數(shù)量少的工件從左往右依次與工序多的工件交換位置。

(2)針對(duì)第二層基因，采用基于最小時(shí)間的搜索策略。隨機(jī)選擇一段編碼基因，在每道工序的可選設(shè)備中選擇加工時(shí)間最小的設(shè)備代替當(dāng)前設(shè)備。

3.5 終止準(zhǔn)則

整個(gè)算法在迭代的過(guò)程中呈現(xiàn)收斂的趨勢(shì),迭代終止條件為：目標(biāo)值達(dá)到預(yù)期的設(shè)定值,或者迭代次數(shù)達(dá)到預(yù)期設(shè)定值。最小目標(biāo)值對(duì)應(yīng)的染色體即為最佳調(diào)度方案。本文的終止條件為迭代500次。

4 計(jì)算實(shí)例

目前調(diào)度車(chē)間常采用固定周期維護(hù)策略和可靠度單值控制維護(hù)策略對(duì)設(shè)備進(jìn)行周期性維護(hù)。為驗(yàn)證本文模型的有效性，將筆者提出的可靠度區(qū)間控制維護(hù)策略(策略一)與可靠度單值控制維護(hù)策略(策略二)和固定周期維護(hù)策略(策略三)進(jìn)行了對(duì)比。

策略一的維護(hù)時(shí)間與役齡的函數(shù)關(guān)系見(jiàn)式(3)。為了使3種維護(hù)策略的對(duì)比更加符合實(shí)際情況，策略二的可靠度單值取策略一的可靠度區(qū)間中值，策略三的維護(hù)周期為20個(gè)時(shí)間單位,策略二、三的維護(hù)時(shí)間求取方法如式(12)所示：

(12)

3種策略的維護(hù)參數(shù)如表1所示。

表1 維護(hù)參數(shù)表

實(shí)例采用文獻(xiàn)[13]中的MK01算例，策略三直接使用該算例的最優(yōu)調(diào)度方案。該方案對(duì)應(yīng)的標(biāo)準(zhǔn)算例工時(shí)和本文模型的工時(shí)如表2所示。

表2 MK01算例完成時(shí)間對(duì)比表

參數(shù)設(shè)置如下：種群規(guī)模為50，最大迭代次數(shù)為500，交叉概率為0.85，變異概率為0.15，威布爾分布中β=3，η=60，退化權(quán)值為0.2。3種維護(hù)策略的計(jì)算結(jié)果如表3所示。

表3 計(jì)算結(jié)果對(duì)比

從表3可以看出，策略一的最優(yōu)調(diào)度方案完成時(shí)間為45.75個(gè)時(shí)間單位,維護(hù)次數(shù)為4次，相較于策略二完工時(shí)間減少了1.27個(gè)時(shí)間單位；相較于維護(hù)策略三，完工時(shí)間減少3.75個(gè)時(shí)間單位,并且維護(hù)次數(shù)減少兩次。3種維護(hù)策略的甘特圖如圖8～圖10所示。

對(duì)比圖8～圖10可看出，相較于策略三，策略一和策略二中的維護(hù)是基于設(shè)備實(shí)際加工時(shí)間的維護(hù)，更有針對(duì)性。對(duì)比圖8和圖9，策略一不僅完工時(shí)間更短，并且對(duì)于不同役齡的設(shè)備采用時(shí)間不等的維護(hù)，維護(hù)時(shí)間更加靈活。綜上所述，對(duì)比3種維護(hù)策略，本文的維護(hù)策略?xún)?yōu)于其他兩種維護(hù)策略。

5 結(jié)論

針對(duì)設(shè)備退化和預(yù)防性維護(hù)的柔性作業(yè)車(chē)間調(diào)度問(wèn)題，采用基于可靠度區(qū)間的維護(hù)策略，考慮設(shè)備退化和役齡之間的關(guān)系，以最大完工時(shí)間最小為目標(biāo)，建立了生產(chǎn)調(diào)度和預(yù)防性維護(hù)相結(jié)合的優(yōu)化模型。在遺傳算法基礎(chǔ)上，改進(jìn)編碼方式和初始化方法，并且加入鄰域搜索的過(guò)程，提高了局部搜索的能力。使用MK01基準(zhǔn)測(cè)試實(shí)例，通過(guò)對(duì)比傳統(tǒng)的固定周期維護(hù)策略和可靠度單值維護(hù)策略，驗(yàn)證了本文模型和算法的有效性，充分說(shuō)明了使用本文的集成模型可以有效提高設(shè)備的加工效率，減少資源浪費(fèi)。

圖8 可靠度區(qū)間調(diào)度甘特圖

參考文獻(xiàn)：

[1] 馬慧民,葉健飛.柔性車(chē)間調(diào)度與設(shè)備維護(hù)的聯(lián)合優(yōu)化研究[J].機(jī)械設(shè)計(jì)與制造,2015(7):248-250.

[2] 崔維偉,陸志強(qiáng),潘爾順.基于多目標(biāo)優(yōu)化的生產(chǎn)調(diào)度與設(shè)備維護(hù)集成研究[J].計(jì)算機(jī)集成制造系統(tǒng)，2014(6):1398-1404.

[3] 劉永,楊明順,高新勤,等.基于機(jī)器役齡約束的車(chē)間作業(yè)與預(yù)防維修的集成調(diào)度[J].制造業(yè)自動(dòng)化,2016(11):70-74.

[4] 張思源,陸志強(qiáng),崔維偉.考慮設(shè)備周期性維護(hù)的流水車(chē)間生產(chǎn)調(diào)度優(yōu)化算法[J].計(jì)算機(jī)集成制造系統(tǒng),2014,20(6):1379-1387.

[5] 金鋒赫,孔繁森,金東園.基于設(shè)備可用時(shí)間約束的裝配作業(yè)車(chē)間調(diào)度規(guī)則[J].計(jì)算機(jī)集成制造系統(tǒng),2008(9):1727-1732.

[6] Khatami M，Zegordi Sh. Coordinative Production and Maintence Scheduling Problem with Flexible Maintenance Time Intervals[J].Journal of Intelligent Manufacturing,2017,28(4):857-867.

[7] Al-Hinai N, ElMekkawy T Y. Robust and Stable Flexible Job Shop Scheduling with Random Machine Breakdowns Using a Hybrid Genetic Algorithm[J].International Journal of Production Economics,2011,132(2):279-291.

[8] Jabbarizadeh F, Zandieh M, Talebi D. Hybrid Flexible Flowshops with Sequence-dependent Setup Times and Machine Availability Constraints[J].Computer & Industrial Engineering,2009,57(3):949-957.

[9] Moubray J. Reliability-centred Maintenance [M]. Amsterdam:Elsevier，1997.

[10] 朱傳軍,邱文,張超勇,等.多目標(biāo)柔性作業(yè)車(chē)間穩(wěn)健性動(dòng)態(tài)調(diào)度研究[J].中國(guó)機(jī)械工程,2017(2):173-182.

[11] 祁文博，郭順生，趙國(guó)，等.改進(jìn)初始化方法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].數(shù)字制造科學(xué)，2017，15(4)：192-196.

[12] 李素粉,朱云龍,尹朝萬(wàn).具有隨機(jī)加工時(shí)間和機(jī)器故障的流水車(chē)間調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng),2005(10):1425-1429.

[13] Brandimarte P. Routing and Scheduling in a Flexible Job Shop by Tabu Search[J]. Annals of Operations Research,1993,41(3):157-183.