生產(chǎn)調(diào)度和模具預(yù)防性維護(hù)集成優(yōu)化研究*

沈 露, 楊宏兵,2, 高 勝

(1.蘇州大學(xué) 機(jī)電工程學(xué)院，江蘇 蘇州 215006；2.廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣州 510006)

0 引言

傳統(tǒng)的生產(chǎn)調(diào)度研究通常不考慮機(jī)器模具等資源的故障和維護(hù)活動(dòng)引起的不可用時(shí)間問(wèn)題，在實(shí)際運(yùn)行中，故障隨時(shí)可能中斷產(chǎn)品的加工，嚴(yán)重地影響企業(yè)生產(chǎn)計(jì)劃的執(zhí)行，預(yù)防性維護(hù)活動(dòng)可以有效地控制資源不可用因素對(duì)企業(yè)生產(chǎn)進(jìn)程的影響，是生產(chǎn)調(diào)度領(lǐng)域的研究熱點(diǎn)。

文獻(xiàn)[1]對(duì)考慮預(yù)防性維護(hù)的單機(jī)系統(tǒng)進(jìn)行研究，應(yīng)用啟發(fā)式和分支定界法來(lái)最小化總完工時(shí)間，該問(wèn)題已被證明為NP難問(wèn)題。文獻(xiàn)[2]提出在并行機(jī)調(diào)度問(wèn)題中，研究基于固定維護(hù)時(shí)長(zhǎng)的周期性維護(hù)和集成維護(hù)兩種策略對(duì)模型的影響。文獻(xiàn)[3-4]在注塑作業(yè)車(chē)間集成生產(chǎn)調(diào)度和基于線性維護(hù)時(shí)長(zhǎng)的預(yù)防性維護(hù)活動(dòng)以期優(yōu)化最大完工時(shí)間。文獻(xiàn)[5]針對(duì)柔性作業(yè)車(chē)間，以最小完工時(shí)間為目標(biāo)研究了考慮不等周期的預(yù)防性維護(hù)活動(dòng)的調(diào)度問(wèn)題。

此外，不少學(xué)者聚焦于同時(shí)考慮生產(chǎn)排序和資源維護(hù)的多目標(biāo)優(yōu)化問(wèn)題，文獻(xiàn)[6]將維護(hù)成本，最大完工時(shí)間，加權(quán)完工時(shí)間，提前/拖期懲罰，和機(jī)器可得性同時(shí)作為目標(biāo)，利用多目標(biāo)遺傳算法求解。文獻(xiàn)[7]研究并行機(jī)問(wèn)題中的生產(chǎn)和維護(hù)活動(dòng)，比較兩種遺傳算法NSGA-II 和WSGA來(lái)同時(shí)優(yōu)化最大完工時(shí)間和系統(tǒng)可用性。文獻(xiàn)[8]進(jìn)一步研究文獻(xiàn)[7]提出的問(wèn)題，設(shè)計(jì)一種多目標(biāo)蟻群算法來(lái)同時(shí)優(yōu)化提前/拖期懲罰和系統(tǒng)不可得性。文獻(xiàn)[9]在單機(jī)系統(tǒng)調(diào)度中集成預(yù)防性維護(hù)活動(dòng)，設(shè)計(jì)改進(jìn)的多目標(biāo)遺傳算法進(jìn)而尋求生產(chǎn)和維護(hù)活動(dòng)之間的平衡。文獻(xiàn)[10]設(shè)計(jì)一種有效的DCRO算法來(lái)優(yōu)化帶維護(hù)約束的多目標(biāo)柔性作業(yè)車(chē)間調(diào)度問(wèn)題，之后，文獻(xiàn)[11]中進(jìn)一步提出DABC算法求解該問(wèn)題。從現(xiàn)有的研究文獻(xiàn)不難看出，以NSGA-II算法為代表的多目標(biāo)遺傳算法被廣泛應(yīng)用于調(diào)度與預(yù)防性維護(hù)多目標(biāo)集成優(yōu)化研究中，并取得了一定的研究成果。本文提出一種改進(jìn)的雙種群差分進(jìn)化算法 (ADPDE) 對(duì)多目標(biāo)集成優(yōu)化模型進(jìn)行求解，并在算法的優(yōu)劣性上與NSGA-II算法進(jìn)行分析和比較。此外，生產(chǎn)調(diào)度的相關(guān)研究通常假設(shè)生產(chǎn)過(guò)程中模具持續(xù)可用，不考慮實(shí)際生產(chǎn)中模具基于使用時(shí)間和役齡的墮化。在現(xiàn)有為數(shù)不多的調(diào)度與模具預(yù)防性維護(hù)集成優(yōu)化研究中也沒(méi)有同時(shí)考慮產(chǎn)品交貨期和設(shè)備利用率，而交貨期滿意度和設(shè)備利用率等是制造企業(yè)普遍關(guān)注的性能指標(biāo)，作為注塑、沖壓等車(chē)間批量生產(chǎn)活動(dòng)的關(guān)鍵資源，不同產(chǎn)品類(lèi)型批量之間的模具切換以及維護(hù)部門(mén)的模具維護(hù)計(jì)劃加大了生產(chǎn)調(diào)度活動(dòng)的復(fù)雜性，其對(duì)生產(chǎn)時(shí)間的占用，也是影響企業(yè)交貨期的重要因素。本文集成考慮帶墮化效應(yīng)的模具的預(yù)防性維護(hù)計(jì)劃以期同時(shí)優(yōu)化企業(yè)的交貨期和模具利用率，平衡生產(chǎn)和維護(hù)部門(mén)的沖突。為求解受模具維護(hù)約束的集成調(diào)度模型，本文提出基于區(qū)分可行解和不可行解的雙種群差分進(jìn)化算法對(duì)模型進(jìn)行求解。

1 雙目標(biāo)集成調(diào)度模型

本文基于文獻(xiàn)[12]的集成調(diào)度模型以批量Flow Shop為研究對(duì)象，調(diào)度期內(nèi)有N種產(chǎn)品順序在M臺(tái)機(jī)器上進(jìn)行加工，每種產(chǎn)品j按固定等批量劃分批次，假設(shè)模具的維護(hù)時(shí)間與模具的當(dāng)前役齡amjk相關(guān)，如圖1所示，模具必須在役齡到達(dá)閾值MA之前執(zhí)行維護(hù)活動(dòng)。

圖1 基于役齡的線性維護(hù)時(shí)長(zhǎng)

從生產(chǎn)實(shí)際的角度，同時(shí)以企業(yè)普遍關(guān)注的交貨期滿意度和設(shè)備利用率為目標(biāo)建立集成優(yōu)化模型，最小化提前/拖后懲罰和最大化模具利用率，定義如下：

(1)

(2)

其中Dj，Tj，αj，βj，Ij分別為產(chǎn)品j的交貨期，完工時(shí)間，提前懲罰系數(shù)，拖期懲罰系數(shù)和模具維護(hù)次數(shù)。

2 改進(jìn)雙種群差分進(jìn)化算法

標(biāo)準(zhǔn)差分進(jìn)化算法[13]操作簡(jiǎn)單，且具有良好的一致性和優(yōu)化性能，在約束優(yōu)化問(wèn)題中應(yīng)用較多。

2.1 差分進(jìn)化算法

差分進(jìn)化算法和其他進(jìn)化算法相似有變異，交叉和選擇三個(gè)操作，交叉變異產(chǎn)生新的試驗(yàn)個(gè)體，選擇算子決定進(jìn)入下一代的個(gè)體選擇。差分進(jìn)化算法[14]對(duì)包含Np個(gè)個(gè)體Xi(t),i=1,2,…,Np的種群進(jìn)行隨機(jī)搜索求解，其中Np表示種群規(guī)模，t表示種群的迭代次數(shù)。

標(biāo)準(zhǔn)差分進(jìn)化算法是在父代個(gè)體之間差分矢量的基礎(chǔ)上進(jìn)行變異操作的，由父代兩個(gè)不同隨機(jī)個(gè)體相減得到的差分矢量加到隨機(jī)選擇的第三個(gè)個(gè)體上, 生成一變異個(gè)體。該過(guò)程即為變異，如公式(3)所示：

Vi(t)=Xi1(t)+F(Xi2(t)-Xi3(t))

(3)

其中，i=1,2,…,Np，i1,i2,i3為從{1,2,…,Np}隨機(jī)選擇的整數(shù)，且i≠i1≠i2≠i3，F(xiàn)表示縮放因子。

執(zhí)行差分變異操作后，對(duì)父代個(gè)體，和得到的變異個(gè)體進(jìn)行交叉操作以生成試驗(yàn)個(gè)體，如公式(4)所示：

(4)

其中，CR控制交叉率，rand(0,1)是(0,1)間的隨機(jī)值。

2.2 改進(jìn)雙種群差分進(jìn)化算法

為了提高標(biāo)準(zhǔn)差分進(jìn)化算法的求解性能，本文基于雙種群差分進(jìn)化算法[15]中區(qū)分可行解和不可行解并分別存儲(chǔ)的雙種群處理機(jī)制，設(shè)計(jì)了一種改進(jìn)的雙種群差分進(jìn)化算法，在新的算法中進(jìn)一步改進(jìn)了變異交叉機(jī)制，同時(shí)利用全局最優(yōu)解參與種群進(jìn)化加快算法收斂速度，以期提高算法的求解性能。

2.2.1 編碼

染色體包括兩個(gè)部分：第一部分為基于子批量排序的實(shí)數(shù)編碼，第二部分為二進(jìn)制維護(hù)決策變量，0表示當(dāng)前工序后不進(jìn)行模具維護(hù)，1則表示執(zhí)行維護(hù)。2種工件分別擁有2和3個(gè)子批量在3臺(tái)設(shè)備上依次加工，如{2 1 4 5 3 0 0 1 0 0 1 0 1 0 0 1 1 1 1 0}，染色體前部分是總計(jì)5個(gè)子批量的隨機(jī)排序{2 1 4 5 3}，每個(gè)子批量對(duì)應(yīng)3個(gè)模具的維護(hù)決策變量因而染色體第二部分{0 0 1 0 0 1 0 2 0 0 1 1 1 1 0}包括5×3個(gè)基因序列，表示對(duì)第一個(gè)子批量只在最后一道工序之后進(jìn)行模具維護(hù)(二進(jìn)制編碼第3位為1前兩位為0)，以此類(lèi)推。

2.2.2 改進(jìn)的變異操作

在種群進(jìn)化過(guò)程中引入不可行解和全局最優(yōu)解的參與，以可行解作為目標(biāo)個(gè)體提出改進(jìn)的雙種群差分進(jìn)化算法，將整個(gè)算法過(guò)程分為三個(gè)階段，每個(gè)階段均采用差別的變異交叉策略，提高算法的尋優(yōu)能力。

(1)種群初始化，區(qū)分可行解和不可行解后，如果當(dāng)前可行解集Pf規(guī)模小于Nf，應(yīng)用公式(3)中的標(biāo)準(zhǔn)差分進(jìn)化算法的變異方法。

(2)可行解集規(guī)模到達(dá)Nf，且迭代次數(shù)t<0.5×T時(shí)在可行解集Pf和全局最優(yōu)解集gbest的并集中隨機(jī)選擇兩個(gè)可行解，不可行解集Pc中隨機(jī)選擇一個(gè)不可行解，應(yīng)用公式(5)，通過(guò)保留部分不可行解參與種群進(jìn)化來(lái)避免算法早熟。

Vi(t)=Xi1(t)+F(gi1(t)-Xi2(t))

(5)

其中，Xi1(t),Xi2(t)∈[Pf;gbest],gi1(t)∈Pc，T為最大迭代次數(shù)。

(3)在算法的最后階段，在Pf和gbest的并集中隨機(jī)選擇兩個(gè)可行解，gbest中隨機(jī)選擇一個(gè)不可行解，應(yīng)用公式(6)，全局最優(yōu)解直接參與進(jìn)化加快算法收斂速度。

Vi(t)=Xi1(t)+F(gi1(t)-Xi2(t))

(6)

其中:Xi1(t),Xi2(t)∈[Pf;gbest],gi1∈gbest。

上述方法均針對(duì)生產(chǎn)排序問(wèn)題，此外，在維護(hù)決策中隨機(jī)選擇一點(diǎn)進(jìn)行單點(diǎn)變異，如果選中的基因值為1，轉(zhuǎn)換為0，反之亦然。

2.2.3 改進(jìn)的交叉操作

不同于第一階段采用公式(4)中的標(biāo)準(zhǔn)差分交叉方法，算法的后兩階段，改進(jìn)雙種群差分進(jìn)化算法在變異個(gè)體和不可行解或全局最優(yōu)解之間直接進(jìn)行交叉操作，試驗(yàn)個(gè)體直接繼承變異個(gè)體或不可行解與全局最優(yōu)解的基因，以充分保留不可行解和全局最優(yōu)解的優(yōu)良性能如公式(7)：

(7)

染色體第一部分的實(shí)數(shù)編碼在上述變異交叉操作后難以保持整數(shù)形式，根據(jù)相對(duì)位置排序法將對(duì)應(yīng)基因位置的值轉(zhuǎn)換為整數(shù)排序。

2.2.4 選擇

與采用貪婪策略進(jìn)行選擇的標(biāo)準(zhǔn)差分進(jìn)化算法相比, 選擇操作由于采用了雙群體搜索機(jī)制而變得更為復(fù)雜。通過(guò)前述交叉、 變異產(chǎn)生新的個(gè)體后, 將采用不同策略來(lái)進(jìn)行選擇操作, 以產(chǎn)生新一代的可行種群與不可行種群。方法如下:

(1)可行解集規(guī)模與當(dāng)前生成的可行解個(gè)數(shù)之和不足Nf時(shí)，直接將可行解插入可行解集Pf；否則基于優(yōu)化目標(biāo)對(duì)兩者的并集進(jìn)行非支配排序，選擇前Nf個(gè)個(gè)體更新可行解集。

(2)不可行解集規(guī)模與當(dāng)前生成的不可行解個(gè)數(shù)之和不足Nc時(shí)，直接將不可行解插入不可行解集Pc；否則基于約束違反程度[16]對(duì)兩者的并集進(jìn)行非支配排序，選擇前Nc個(gè)個(gè)體更新可行解集。

2.3 算法流程

改進(jìn)雙種群差分進(jìn)化算法的步驟如下：

步驟1： 設(shè)置初始種群規(guī)模Np，可行解集Pf規(guī)模Nf，不可行解集Pc規(guī)模Nc，變異因子F，交叉因子CR，最大迭代次數(shù)T等參數(shù)，種群初始化。

步驟2： 計(jì)算個(gè)體的目標(biāo)值及約束違反程度，將可行解與不可行解插入相應(yīng)種群，初始化全局最優(yōu)解gbest。

步驟3：進(jìn)行標(biāo)準(zhǔn)差分進(jìn)化變異交叉如公式(3)、公式(4)，更新Pf，Pc，gbest。

步驟4：如果t<0.5×T，執(zhí)行公式(5)、公式(7)的變異交叉操作，更新Pf，Pc，gbest。

步驟5：如果0.5×T≤t

步驟6：終止條件t=T滿足時(shí)，輸出最優(yōu)解gbest。

算法流程如圖2所示。

圖2 ADPDE算法流程圖

3 算例分析

在工程約束優(yōu)化問(wèn)題中，通常構(gòu)造罰函數(shù)應(yīng)用遺傳算法進(jìn)行求解，改進(jìn)雙種群差分進(jìn)化算法通過(guò)分別保存可行解集和不可行解集利用不可行解參與進(jìn)化來(lái)避免罰函數(shù)的構(gòu)造。為證明算法的有效性，現(xiàn)將改進(jìn)的雙種群差分進(jìn)化算法與NSGA-II算法在內(nèi)存2G，主頻2.4GHz的Intel Core i3的Win7系統(tǒng)中通過(guò)MATLAB 7.8.0 (R2009a)平臺(tái)進(jìn)行比較，在6個(gè)假設(shè)性的問(wèn)題中，可歸類(lèi)為三類(lèi)問(wèn)題(3×5, 4×5, 5×5)，每類(lèi)問(wèn)題包含2種子批量規(guī)模，種群規(guī)模設(shè)定為100，NAGA-II 的變異因子為0.9，交叉因子為0.1，ADPDE的變異交叉因子分別為0.7和0.9，終止條件設(shè)定為種群進(jìn)化代數(shù)滿1000，每種算法在每個(gè)問(wèn)題中運(yùn)行20次。

Zitzler[17]等提出的C矩陣是多目標(biāo)優(yōu)化問(wèn)題中評(píng)價(jià)Pareto曲線優(yōu)劣的著名指標(biāo)，C(A,B)的值表示前沿B中被前沿A的至少一個(gè)個(gè)體支配的個(gè)體占總體的比例。

(8)

C(A,B)=1表示中所有解都至少被中的一個(gè)解支配；相反地，C(A,B)=0表示B中沒(méi)有解被A中的任一解支配。因此，C(A,B)越接近0，表示Pareto前沿B相對(duì)于A來(lái)說(shuō)越好。

對(duì)每個(gè)問(wèn)題兩種算法均運(yùn)行20次對(duì)比結(jié)果，表1總結(jié)了兩種算法20次運(yùn)行所得最優(yōu)解集的最大，最小和平均解個(gè)數(shù)，從表格中可以發(fā)現(xiàn)最大，最小，平均值方面ADPDE均優(yōu)于NSGA-II；表格2總結(jié)了兩種算法20次運(yùn)行所得C值的最大，最小和平均值，從表格中可以發(fā)現(xiàn)最大，最小，平均值方面ADPDE均優(yōu)于NSGA-II，ADPDE求解的Pareto前沿明顯優(yōu)于NSGA-II。上述分析結(jié)果表明ADPDE求解本文提出的約束優(yōu)化問(wèn)題時(shí)，在不同的問(wèn)題規(guī)模下求得的最優(yōu)解的個(gè)數(shù)和質(zhì)量均優(yōu)于NSGA-II算法。

表1 兩種算法運(yùn)行20次所求非支配解個(gè)數(shù)的最大值，平均值和最小值

表2 兩種算法運(yùn)行20次所求非支配解集覆蓋率的最大值，平均值和最小值

(a) 問(wèn)題 1

(b) 問(wèn)題 2

(c) 問(wèn)題3

(d) 問(wèn)題4

(e) 問(wèn)題5

(f) 問(wèn)題6圖3 ADPDE和NSGA-II運(yùn)行20次后返回的非支配解集

在表格3中，比較兩種算法的運(yùn)行時(shí)間，鑒于差分進(jìn)化算法操作簡(jiǎn)單，改進(jìn)的交叉策略的進(jìn)一步優(yōu)化，ADPDE的運(yùn)行速度明顯優(yōu)于NSGA-II，問(wèn)題的規(guī)模越大，變量越多，ADPDE的優(yōu)越性越凸顯。

表3 比較ADPDE和NSGA-II的運(yùn)行時(shí)間(s)

4 結(jié)束語(yǔ)

本文提出Flow Shop生產(chǎn)調(diào)度與模具預(yù)防性維護(hù)的集成優(yōu)化問(wèn)題，同時(shí)考慮提前/拖后完工時(shí)間和模具利用率雙目標(biāo)來(lái)平衡兩者間的矛盾，基于不可行解的優(yōu)良特性設(shè)計(jì)改進(jìn)的雙種群差分進(jìn)化算法求解該約束優(yōu)化問(wèn)題。比較ADPDE與NSGA-II的實(shí)驗(yàn)數(shù)據(jù)結(jié)果，不僅ADPDE所獲得的C值最大，最小，平均值均優(yōu)于NSGA-II算法，ADPDE算法的Pareto前沿相比較NSGA-II算法也更靠近Pareto最優(yōu)前沿，ADPDE算法所得到的解明顯優(yōu)于NSGA-II算法，在保證解的優(yōu)越性的同時(shí)有效提高了算法的運(yùn)行速度。驗(yàn)證了本文提出的改進(jìn)的雙種群差分進(jìn)化算法求解所建模型的有效性。

完善集成優(yōu)化模型的實(shí)際生產(chǎn)因素如其他資源的維護(hù)活動(dòng)，同時(shí)考慮批量分割問(wèn)題將是下一步的研究方向，以進(jìn)一步提高生產(chǎn)效率和最大程度滿足交期的要求。

[1] X Qi, T Chen, F Tu. Scheduling the maintenance on single machine[J]. Journal of the Operational Research Society, 1999, 50(10):1071-1078.

[2] K Sun, H Li. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines[J]. International Journal of Production Economics, 2010, 124 (1):151-158.

[3] C S Wong, F T S Chan, S H Chung. A genetic algorithm approach for production scheduling with mould maintenance consideration[J]. International Journal of Production Research, 2012, 2011(20):5683-5697.

[4] C S Wong, F T S Chan, S H Chung. A joint production scheduling approach considering multiple resources and preventive maintenance tasks[J]. International Journal of Production Research, 2013, 51(3):1-14.

[5] 查靚, 金花, 潘志成, 等.基于順序相關(guān)調(diào)整時(shí)間的FJSP與設(shè)備維護(hù)計(jì)劃集成優(yōu)化[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2016(5):155-160.

[6] Y Jin, Z Jiang, W Hou. Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine[J]. International Journal of Advanced Manufacturing Technology, 2008, 39(9):954-964.

[7] Berrichi A, Amodeo L, Yalaoui F, et al. Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem[J]. Journal of Intelligent Manufacturing, 2009, 20(4): 389.

[8] Berrichi A, Yalaoui F. Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2013, 68(9): 2295-2310.

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

[10] JQ Li, QK Pan. Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity[J]. Applied Soft Computing, 2012, 12(9): 2896-2912.

[11] JQ Li, QK Pan, MF Tasgetiren. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling, 2014, 38(3):1111-1132.

[12] Lu Shen, Hongbing Yang, Sheng Gao, et al. Production Scheduling with Mould Maintenance in Flow Shop [C]. Proceedings of the 2016 4thInternational Conference on Sensors, Mechatronics and Automation, 2016, (136):730-733.

[13] E Mezura-Montes, CAC Coello. Constraint handling in nature-inspired numerical optimization: past, present and future[J]. Swarm and Evolutionary Computation, 2011, 1(4): 173-194.

[14] S Das, PN Suganthan. Differential evolution: A survey of the state-of-the-art[J]. IEEE Trans on Evolutionary Computation 2011,15(1): 4-31.

[15] 孟紅云, 張小華, 劉三陽(yáng). 用于約束多目標(biāo)優(yōu)化問(wèn)題的雙種群差分進(jìn)化算法[J].計(jì)算機(jī)學(xué)報(bào), 2008, 31(2):228-235.

[16] K Deb. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics & Engineering, 2000, 186(2-4): 311-338.

[17] E Zitzler, L Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271.

[18] C GarcíaMartínez, O Cordón, F Herrera. An Empirical Analysis of Multiple Objective Ant Colony Optimization Algorithms for the Bi-criteria TSP[J]. European Journal of Operational Research, 2007, 180(1): 116-148.

[19] E Zitzler, K Deb, L Thiele. Comparison of multiobjective evolutionary algorithms: empirical results[J]. Evolutionary Computation, 2000, 8(2): 173.