衰退流水車間生產與預防性維護調度研究

陳陽 譚園園

摘要：針對實際生產中調度與維修計劃相互影響的問題。以衰退流水車間為研究對象，考慮設備的退化和預防性維護限制，決策工件調度計劃和設備的預防性維護計劃。建立了不確定環境下以最小化最大工件完工時間和最小化平均設備空閑時間為目標的數學模型。基于非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ），為避免算法陷入局部最優前沿，提出了混合多樣性解的多目標優化算法。不同規模的算例應用改進算法與原NSGA-Ⅱ算法進行求解，對比結果表明所設計算法在收斂性、多樣性方面上表現更好。

關鍵詞：流水車間;設備衰退;預防性維護;多目標優化;NSGA-Ⅱ算法

中圖分類號：TP302 文獻標識碼：A

文章編號：1009-3044（2020）03-0237-03

1 概述

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

2 問題描述

2.1 流水車間調度問題

調度期內有n個工件，m臺設備，每一道生產工序僅有一臺設備，每個工件依次在m臺設備上加工，工件在每臺設備上的加工順序相同，每個工件在每臺設備上只能被加工一次。

2.2 設備故障

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

4 算法設計

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

4.1 編碼與解碼

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

4.2 交叉、變異算子

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

5 仿真實驗

5.1 實驗設置

本文采用C++編程實現算法，參照文獻[6]，[7]設置參數如下：最大迭代次數為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。問題規模分別是lOx6、15x8、20xl0、30x15。

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

5.2 實驗結果分析

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

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

6 總結

本文針對流水車間聯合生產與維護雙目標優化問題，建立了考慮設備退化影響下的預防性維護與生產調度模型，并改進了傳統NSGA-II算法，設計了混合多樣性解的保留算子，通過實驗對比分析，本文所獲得的Pareto解在空間散布范圍、間距及解的個數上均有改善，同時本文提出的算法可以很好地逼近Pareto前沿，保持解的多樣性，是一種有效求解多目標優化問題的方法。

參考文獻;

[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]大連海事大學學報，2007，33（3）：32-35.

[7]金玉蘭，蔣祖華.預防性維修計劃和生產調度的多目標優化[J].哈爾濱工程大學學報，2011，32（09）：1205-1209.