杜陽宇，張 楓

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

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

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

1 問題描述

1.1 柔性作業(yè)車間問題描述

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

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

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

(3)維護活動過程設(shè)備停工；

(4)維護活動在工序完工之后進行；

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

1.2 設(shè)備維護描述

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

(1)

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

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

(2)

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

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

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

(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之后進行維護，此時設(shè)備狀態(tài)處于圖1中的區(qū)域B。

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

(3)

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

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

1.3 設(shè)備退化描述

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

×?

(4)

uijk=pijk+αkpijk

(5)

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

2 模型建立

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

(6)

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

(7)

(8)

(9)

(10)

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

3 算法設(shè)計

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

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

圖2 算法流程圖

3.1 編碼和解碼

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

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

第二層基因確定加工設(shè)備。將所有工件的工序依次排列，每道工序?qū)?yīng)一個加工設(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。

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

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

3.2 初始化

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

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

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

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

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

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

3.3 遺傳算子

3.3.1 選擇算子

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

3.3.2 交叉算子

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

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

(1)隨機生成兩個父代交叉點如圖4所示。

圖4 POX交叉(一)

(2)交叉父代染色體中a,b之間的基因,分別復(fù)制給兩個子代染色體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交叉(四)

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

3.3.3 變異算子

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

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

3.4 鄰域搜索算法

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

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

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

3.5 終止準則

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

4 計算實例

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

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

(12)

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

表1 維護參數(shù)表

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

表2 MK01算例完成時間對比表

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

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

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

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

5 結(jié)論

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

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

參考文獻：

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

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

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

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

[5] 金鋒赫,孔繁森,金東園.基于設(shè)備可用時間約束的裝配作業(yè)車間調(diào)度規(guī)則[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] 朱傳軍,邱文,張超勇,等.多目標柔性作業(yè)車間穩(wěn)健性動態(tài)調(diào)度研究[J].中國機械工程,2017(2):173-182.

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

[12] 李素粉,朱云龍,尹朝萬.具有隨機加工時間和機器故障的流水車間調(diào)度[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.