衰退流水車間生產(chǎn)與預(yù)防性維護(hù)調(diào)度研究

陳陽(yáng) 譚園園

摘要：針對(duì)實(shí)際生產(chǎn)中調(diào)度與維修計(jì)劃相互影響的問題。以衰退流水車間為研究對(duì)象，考慮設(shè)備的退化和預(yù)防性維護(hù)限制，決策工件調(diào)度計(jì)劃和設(shè)備的預(yù)防性維護(hù)計(jì)劃。建立了不確定環(huán)境下以最小化最大工件完工時(shí)間和最小化平均設(shè)備空閑時(shí)間為目標(biāo)的數(shù)學(xué)模型?；诜侵渑判蜻z傳算法（Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ），為避免算法陷入局部最優(yōu)前沿，提出了混合多樣性解的多目標(biāo)優(yōu)化算法。不同規(guī)模的算例應(yīng)用改進(jìn)算法與原NSGA-Ⅱ算法進(jìn)行求解，對(duì)比結(jié)果表明所設(shè)計(jì)算法在收斂性、多樣性方面上表現(xiàn)更好。

關(guān)鍵詞：流水車間;設(shè)備衰退;預(yù)防性維護(hù);多目標(biāo)優(yōu)化;NSGA-Ⅱ算法

中圖分類號(hào)：TP302 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）03-0237-03

1 概述

生產(chǎn)與維護(hù)調(diào)度因其問題的復(fù)雜性和目標(biāo)的沖突性，受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。針對(duì)維護(hù)不可用期固定的調(diào)度問題，Kubzin[1]研究了雙機(jī)的開放車間調(diào)度和流水車間調(diào)度，考慮了設(shè)備在生產(chǎn)期內(nèi)存在不可用期的限制，證明了流水車間調(diào)度下該問題的NP難性。Wang[2]研究了并行機(jī)在確定的周期維護(hù)策略下，以最大化按時(shí)完工數(shù)量為目標(biāo)，設(shè)計(jì)了具有向后調(diào)整和兩階段前瞻性策略的啟發(fā)式算法。Hugo[3]將預(yù)防性維護(hù)作為M臺(tái)設(shè)備無等待流水車間調(diào)度的約束，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，設(shè)計(jì)了具有最大維護(hù)水平間隔的預(yù)防性維護(hù)操作以保證調(diào)度期內(nèi)最少維護(hù)次數(shù)。Ma[4]對(duì)單機(jī)、并行機(jī)、流水車間及作業(yè)車間環(huán)境下確定不可用期的問題做出了綜述。 針對(duì)問題實(shí)際特點(diǎn)及現(xiàn)有方法的不足，本文考慮設(shè)備退化對(duì)加工時(shí)間的影響，建立了加T時(shí)間與工件開.工時(shí)間，以最小化最大完工時(shí)間和最小化平均設(shè)備空閑時(shí)間為優(yōu)化目標(biāo)，考慮設(shè)備的不定期靈活維護(hù)，決策工件加工順序和設(shè)備預(yù)防性維護(hù)計(jì)劃。

2 問題描述

2.1 流水車間調(diào)度問題

調(diào)度期內(nèi)有n個(gè)工件，m臺(tái)設(shè)備，每一道生產(chǎn)工序僅有一臺(tái)設(shè)備，每個(gè)工件依次在m臺(tái)設(shè)備上加工，工件在每臺(tái)設(shè)備上的加工順序相同，每個(gè)工件在每臺(tái)設(shè)備上只能被加工一次。

2.2 設(shè)備故障

設(shè)備的失效函數(shù)服從威布爾分布，設(shè)備的故障率函數(shù)λ（t）是關(guān)于時(shí)間t的增函數(shù)，如式（1）所示：式（5）～（6）分別表示最小化完工時(shí)間和最小化平均設(shè)備空閑時(shí)間兩個(gè)目標(biāo)約束式（7）～（8）表示設(shè)備生產(chǎn)約束;約束式（9）表示機(jī)器役齡的累積，在預(yù)防性維護(hù)之后役齡歸零;約束式（10）表示預(yù)防性維護(hù)策略，式（11） -（13）表示工序與位置一一對(duì)應(yīng)。

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

本文基于Deb等[s]提出的NSGA-Ⅱ算法，根據(jù)問題模型特點(diǎn)，提出了混合多樣性解的保留策略，計(jì)算種群中個(gè)體與高質(zhì)量解的最小歐幾里得距離，將種群按照最小歐幾里得距離由大到小排序，選擇排序占前的個(gè)體作為多樣性解填人篩選集擴(kuò)大種群搜索范圍，避免算法過早地陷入局部最優(yōu)。本文算法標(biāo)記為I-NSGA-II。

4.1 編碼與解碼

本文研究問題涉及工件生產(chǎn)順序和設(shè)備維護(hù)兩部分，生產(chǎn)部分采用1-n整數(shù)編碼。維護(hù)部分采用矩陣表示預(yù)防性維護(hù)的位置，n個(gè)工件m臺(tái)設(shè)備的流水車間的維護(hù)矩陣Dpm表示為：

4.2 交叉、變異算子

對(duì)于流水車間問題，順序交叉（Order Crossover，OX）可以保留工件位置關(guān)系，保證生成可行性解，故本文采用順序交叉方式。以11個(gè)工件的交叉為例，如圖1。變異算子采用交換變異（Exchange Mutation，EM）在一條染色體上隨機(jī)選擇兩個(gè)基因位，交換這兩個(gè)基因位，構(gòu)成新的染色體。

5 仿真實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

本文采用C++編程實(shí)現(xiàn)算法，參照文獻(xiàn)[6]，[7]設(shè)置參數(shù)如下：最大迭代次數(shù)為100，交叉概率Pc= 0.9，變異概率Pn=0.1，tr=5，tp0= 15，RL= 0.8，p=2，η=150，pok，i=U（15，29），tp0=15，a0= 0.01。問題規(guī)模分別是lOx6、15x8、20xl0、30x15。

為清楚展示本文研究問題，在此給出lOx6算例下本文算法求解的甘特圖。圖2為lOx6算例調(diào)度甘特圖。

5.2 實(shí)驗(yàn)結(jié)果分析

為更直觀展示兩算法結(jié)果的差別，在此做出Pareto前沿圖像，圖3所示：

觀察圖3，相同完工時(shí)間目標(biāo)下本文算法所得Pareto解的設(shè)備空閑時(shí)間更小，相同設(shè)備空閑時(shí)間目標(biāo)下本文算法所得Pareto解的完工時(shí)間更小。本文算法所得解在兩個(gè)目標(biāo)維度上均優(yōu)于且絕大多數(shù)都支配原NSGA-II所得解。改進(jìn)后算法有效地逼近了Pareto前沿，搜索能力更好，求解效率更高。

6 總結(jié)

本文針對(duì)流水車間聯(lián)合生產(chǎn)與維護(hù)雙目標(biāo)優(yōu)化問題，建立了考慮設(shè)備退化影響下的預(yù)防性維護(hù)與生產(chǎn)調(diào)度模型，并改進(jìn)了傳統(tǒng)NSGA-II算法，設(shè)計(jì)了混合多樣性解的保留算子，通過實(shí)驗(yàn)對(duì)比分析，本文所獲得的Pareto解在空間散布范圍、間距及解的個(gè)數(shù)上均有改善，同時(shí)本文提出的算法可以很好地逼近Pareto前沿，保持解的多樣性，是一種有效求解多目標(biāo)優(yōu)化問題的方法。

參考文獻(xiàn);

[1] Kubzin M A，Strusevich V A.Planning machine maintenancein two-machine shop scheduling[J]. Operations Research.2006， 54（4）：789-800.

[2] Wang X，Cheng T C E.A heuristic for scheduling jobs on twoidentical parallel machines with a machine availability con-straint[J]. Intemational Journal of Production Economics.2015， 161（3）：74-82.

[3] Hugo H M， Marcelo S N，et al.Integrating preventive mainte-nance activities to the no-wait flow shop scheduling problemwith dependent-sequence setup times and makespanminimization[J]. Computers&Industrial Engineering， 2019， 135（9）：79-104.

[4] Ma Y，Chu C，Zuo C.A survey of scheduling with determinis-tic machine availability constraints[J]. Computers&IndustrialEngineering， 2010， 58（2）：199-211.

[5] Deb K，PratapA，Agarwal S，et al.A fast and elitist multi-ob-jective genetic algorithm： NSGA-II[J]. IEEE Transactions onEvolutionary Computation. 2002， 6（2）：0-197.

[6]周炳海，蔣舒宇，王世進(jìn)，等.集成生產(chǎn)與預(yù)防性維護(hù)的流水線車間調(diào)度算法[J]大連海事大學(xué)學(xué)報(bào)，2007，33（3）：32-35.

[7]金玉蘭，蔣祖華.預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化[J].哈爾濱工程大學(xué)學(xué)報(bào)，2011，32（09）：1205-1209.