預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化

金玉蘭，蔣祖華

(1.上海工程技術(shù)大學(xué) 管理學(xué)院，上海200260;2.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海200240)

預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度是生產(chǎn)企業(yè)所面臨的最常見(jiàn)和最重要的問(wèn)題之一.預(yù)防性維修占據(jù)了本來(lái)用來(lái)進(jìn)行生產(chǎn)活動(dòng)的時(shí)間，同時(shí)，如果不進(jìn)行預(yù)防性維修，又有可能在生產(chǎn)過(guò)程中發(fā)生突發(fā)故障，更大程度地影響生產(chǎn)進(jìn)程.

為合理解決生產(chǎn)調(diào)度和預(yù)防性維修間的矛盾沖突，許多學(xué)者對(duì)預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的聯(lián)合優(yōu)化問(wèn)題進(jìn)行了研究［1-4］，主要集中在最小化加權(quán)總完工時(shí)間［1，3］、最小化加權(quán)總延遲時(shí)間［2］、最小化生產(chǎn)任務(wù)的最大完成時(shí)間［4］等時(shí)間目標(biāo)的優(yōu)化上，而對(duì)于維修的成本問(wèn)題沒(méi)有涉及.有效的預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃必須同時(shí)考慮到降低維修成本，提高生產(chǎn)效率.

本文對(duì)單設(shè)備預(yù)防性維修和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化問(wèn)題進(jìn)行了研究，并分別與單目標(biāo)聯(lián)合優(yōu)化的方法［1-3］和獨(dú)立優(yōu)化的方法進(jìn)行了對(duì)比.

1 預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)聯(lián)合優(yōu)化模型

1.1 生產(chǎn)調(diào)度

假設(shè)一個(gè)生產(chǎn)系統(tǒng)中的一臺(tái)設(shè)備需要順序完成n個(gè)作業(yè)，pj為作業(yè)j的加工時(shí)間，dj為作業(yè)j的預(yù)定完成時(shí)間，wj為作業(yè) j的重要性，j=1，2，…，n.生產(chǎn)調(diào)度計(jì)劃的目的是對(duì)n個(gè)作業(yè)進(jìn)行合理的作業(yè)排序.令［1-2］

設(shè) p［i］為作業(yè)序列中第 i個(gè)作業(yè)所用時(shí)間，d［i］為作業(yè)序列中第i個(gè)作業(yè)的預(yù)定完成，w［i］為作業(yè)序列中第i個(gè)作業(yè)的重要性，C［i］為作業(yè)序列中第i個(gè)作業(yè)的實(shí)際完成時(shí)間，T［i］為作業(yè)序列中第i個(gè)作業(yè)的延遲時(shí)間，i=1，2，…，n.若忽略設(shè)備的失效狀況，則［1-3］

對(duì)生產(chǎn)調(diào)度計(jì)劃的制定，經(jīng)常考慮到以下一些面向時(shí)間的目標(biāo)，如:全部生產(chǎn)任務(wù)的最大完成時(shí)間(makespan)，加權(quán)總完工時(shí)間(total weighted completion times，TWC)，加權(quán)總延遲時(shí)間(total weighted tardiness，TWT)等.其中［3］:

1.2 維修計(jì)劃

設(shè)備可靠性狀況、預(yù)防性維修策略、預(yù)防性維修處理時(shí)間、突發(fā)故障處理時(shí)間、突發(fā)故障次數(shù)等因素都會(huì)影響到生產(chǎn)任務(wù)中各個(gè)作業(yè)的最終完成時(shí)間［1］.因此，在生產(chǎn)調(diào)度時(shí)要同時(shí)考慮維修策略.同文獻(xiàn)［1-3］，將預(yù)防性維修計(jì)劃安排在作業(yè)序列中每個(gè)作業(yè)開(kāi)始之前.假設(shè)預(yù)防性維修使設(shè)備的狀態(tài)修復(fù)到全新.生產(chǎn)過(guò)程中的突發(fā)故障用小修處理.設(shè)R0為加工整個(gè)作業(yè)序列前的設(shè)備初始可靠度，tp為預(yù)防性維修平均所需時(shí)間，tr為突發(fā)故障平均處理時(shí)間，cp為進(jìn)行一次預(yù)防性維修的平均成本，cr為處理一次突發(fā)故障的平均成本.

設(shè)y［i］為作業(yè)序列中第 個(gè)作業(yè)加工前的預(yù)防性維修決策，則［1］

當(dāng)生產(chǎn)設(shè)備的故障服從威布爾分布，形狀參數(shù)為β(β＞1)，尺寸參數(shù)為 η，則設(shè)備的可靠度R(t)和故障率λ(t)分別為

設(shè)從全新?tīng)顟B(tài)始，設(shè)備運(yùn)行時(shí)間τ內(nèi)發(fā)生的故障次數(shù)為 N(τ)，則

設(shè)as［i］為作業(yè)序列中進(jìn)行第i個(gè)作業(yè)加工前的設(shè)備役齡，ae［i］為作業(yè)序列中完成第i個(gè)作業(yè)完成后的設(shè)備役齡，則［1］

根據(jù)式(10)，當(dāng)加工整個(gè)作業(yè)序列前的設(shè)備初始可靠度為R0時(shí)有

作業(yè)序列中第i個(gè)作業(yè)的完成時(shí)間C［i］為

設(shè)MC為完成整個(gè)作業(yè)序列所需的維修成本(maintenance cost)，則

1.3 多目標(biāo)聯(lián)合優(yōu)化模型

為更好地節(jié)約維修成本和完成生產(chǎn)任務(wù)，設(shè)fk(k=1，2，3，4)為需要考慮的目標(biāo)，則

設(shè) fopt為目標(biāo)向量函數(shù)，fopt=(f1，f2，f3，f4)，則多目標(biāo)優(yōu)化模型為

2 多目標(biāo)遺傳算法

多目標(biāo)優(yōu)化問(wèn)題常會(huì)存在一個(gè)Pareto最優(yōu)集，集中的每個(gè)解都是多目標(biāo)優(yōu)化問(wèn)題的一個(gè)非劣解，可為決策者作最終選擇所用.與大多數(shù)優(yōu)化算法不同，遺傳算法可以提供一個(gè)種群的相似解，同時(shí)尋找到多個(gè) Pareto優(yōu)解［5］.

多目標(biāo)遺傳算法是根據(jù)支配的概念來(lái)運(yùn)作的［5］.如果說(shuō)解x1支配x2，則必須滿足以下2個(gè)條件［5］:1)對(duì)于所有的目標(biāo)x1非劣于x2;2)至少有一個(gè)目標(biāo)x1優(yōu)于x2.如果以上2個(gè)條件不滿足，則x1不支配x2.

2.1 編碼和初始種群

個(gè)體(染色體)采用實(shí)值編碼法.對(duì)于種群中的每個(gè)個(gè)體先隨機(jī)產(chǎn)生一個(gè)預(yù)防性維修序列，再產(chǎn)生一個(gè)隨機(jī)的作業(yè)序列.如個(gè)體{01104321}表示預(yù)防性維修序列為0-1-1-0，作業(yè)序列為4-3-2-1.隨機(jī)產(chǎn)生多目標(biāo)遺傳算法的初始種群，種群的大小為Npop，Npop設(shè)定要適中，太小會(huì)使收斂速度變慢，太大則會(huì)增加搜索的難點(diǎn)，降低搜索效率.

2.2 精英策略

在多目標(biāo)優(yōu)化中，存在一組非被支配個(gè)體的集合 Eg(g=1，2，…，Gen，Gen 為算法的代數(shù)).在進(jìn)行遺傳算法時(shí)，從Eg找出不同于Ei(i=1，2，…，g-1)中的非被支配個(gè)體，組成新集合Eg'.將Eg'中的個(gè)體保存在精英集中.從這個(gè)精英集中隨機(jī)選擇Nelite組個(gè)體作為遺傳算法中的精英［5］.

2.2.1 評(píng)價(jià)

對(duì)種群中的每個(gè)個(gè)體，按照1.1節(jié)和1.2節(jié)分別計(jì)算出各個(gè)目標(biāo)函數(shù).將種群中的個(gè)體按照是否支配其他個(gè)體進(jìn)行分類，并將非被支配的個(gè)體保存在集合 Eg(g=1，2，…，Gen)中.

2.2.2 分類

下列過(guò)程可以找出種群中的非被支配個(gè)體［5］.

1)從i=1開(kāi)始.

2)從 j=1，2，…，Npop，如果 i≠j，則根據(jù)支配的概念來(lái)判斷個(gè)體xi和個(gè)體xj之間的支配關(guān)系.

3)如果對(duì)于任意的j(i≠j)，xj都支配，xi則表示xi是被支配的.

4)如果種群中的所有個(gè)體都考慮了，轉(zhuǎn)步驟4);否則，轉(zhuǎn)步驟2).

5)除被支配的個(gè)體外，種群中的其他個(gè)體都是非被支配個(gè)體.

2.3 選擇

本文采用隨機(jī)加權(quán)法［5］將多目標(biāo)轉(zhuǎn)化成單目標(biāo)，從而計(jì)算個(gè)體的適應(yīng)度.對(duì)目標(biāo) fk(k=1，2，3，4)線性正規(guī)化處理，設(shè)fmaxk和fmink分別為種群中目標(biāo)fk的最大值和最小值，線性正規(guī)化后目標(biāo)值vk(fk)為［6］

在選擇一組個(gè)體作為父代產(chǎn)生新個(gè)體時(shí)，用以下方法為各目標(biāo)產(chǎn)生一個(gè)隨機(jī)權(quán)重:

式中:randomk(·)為任意非負(fù)隨機(jī)數(shù)，且randomk(·)∈［0，1］.由式(24)、(25)得隨機(jī)加權(quán)適應(yīng)度函數(shù)為

2.4 交叉

本文采用單點(diǎn)交叉，交叉點(diǎn)范圍為［1，2n-1］，n為作業(yè)序列中作業(yè)的個(gè)數(shù)，在交叉點(diǎn)之后的父?jìng)€(gè)體的變量相互交換.當(dāng)交叉點(diǎn)為［1，n］時(shí)，即交叉點(diǎn)在預(yù)防性維修序列中，則直接進(jìn)行交換.當(dāng)交叉點(diǎn)為［n+1，2n-1］時(shí)，即交叉點(diǎn)在作業(yè)序列中，則從交叉點(diǎn)之后父?jìng)€(gè)體Parent1的作業(yè)序列為父?jìng)€(gè)體Parent2中除去Parent1交叉點(diǎn)前作業(yè)后的作業(yè)序列［3］.

2.5 變異

本文采用單點(diǎn)變異，變異點(diǎn)的范圍為［1，2n］，n為作業(yè)序列中作業(yè)的個(gè)數(shù).當(dāng)變異點(diǎn)為［1，n］時(shí)，即變異點(diǎn)處于預(yù)防性維修序列中，將變異點(diǎn)值進(jìn)行0和1之間的轉(zhuǎn)換.當(dāng)變異點(diǎn)為［n+1，2n］時(shí)，即變異點(diǎn)處于作業(yè)序列中，將變異點(diǎn)處的作業(yè)轉(zhuǎn)移到作業(yè)序列的最后一個(gè)進(jìn)行加工［3］.

2.6 多目標(biāo)遺傳算法流程

1)根據(jù)2.1節(jié)產(chǎn)生初始種群Npop.

2)根據(jù)2.2節(jié)找出種群中的非支配個(gè)體集Eg和Eg'，并將Eg'保存在精英集中.判斷是否滿足優(yōu)化準(zhǔn)則，如果滿足，轉(zhuǎn)步驟7)，否則，轉(zhuǎn)步驟3).

3)從精英集中隨機(jī)選擇Nelite組個(gè)體作為父?jìng)€(gè)體.其余(Npop-Nelite)組父?jìng)€(gè)體從種群中選出.根據(jù)2.3節(jié)計(jì)算種群中各個(gè)體的隨機(jī)加權(quán)適應(yīng)度函數(shù)，然后用輪盤賭的方法選出(Npop-Nelite)組父?jìng)€(gè)體.

4)將Npop組父?jìng)€(gè)體重新隨機(jī)組對(duì).根據(jù)交叉概率pc和2.4節(jié)的交叉方法，生成一組新個(gè)體.

5)根據(jù)變異概率pm和2.5節(jié)的變異方法對(duì)新的個(gè)體進(jìn)行變異操作.

6)對(duì)每組新個(gè)體根據(jù)2.2.1 節(jié)和2.2.2 節(jié)進(jìn)行評(píng)價(jià)分類，并找出一個(gè)較優(yōu)的個(gè)體作為新個(gè)體.如果沒(méi)有較優(yōu)的個(gè)體，則隨機(jī)選擇一個(gè)作為新個(gè)體.Npop個(gè)新個(gè)體組成新的種群.轉(zhuǎn)步驟2).

7)根據(jù)2.2節(jié)的方法，從精英集中找出非被支配的個(gè)體作為Pareto最優(yōu)集.

8)決策者根據(jù)偏好從Pareto最優(yōu)集中選出滿意解.

3 算例分析

3.1 算例及結(jié)果

假設(shè)設(shè)備的初始可靠度R0=0.8;故障服從威布爾分布，形狀參數(shù)β=1.8，尺寸參數(shù)η=100;預(yù)防性維修處理時(shí)間tp=5，小修處理時(shí)間tr=15;預(yù)防性維修成本cp=500，小修的成本cr=300.有4個(gè)作業(yè)需要進(jìn)行加工，其參數(shù)見(jiàn)表1.

表1 生產(chǎn)調(diào)度參數(shù)示例Table 1 Factors of production scheduling in the example

將以上參數(shù)代入優(yōu)化模型，在Visual Basic 6.0中編程實(shí)現(xiàn)多目標(biāo)遺傳算法.當(dāng)遺傳代數(shù)Gen=30，種群大小 Npop=30，交叉概率 pc=0.8，變異概率pm=0.7，Nelite=3 時(shí)，所得優(yōu)化結(jié)果見(jiàn)表2.

一般情況下預(yù)防性維修次數(shù)越多，則突發(fā)故障的產(chǎn)生次數(shù)越少.由表2可知，對(duì)于特定的生產(chǎn)要求(如表1所示)由于cp＞cr所以維修成本(MC)還是隨維修次數(shù)的增多而升高.由表2可知，加權(quán)總完工時(shí)間(TWC)和加權(quán)總延遲時(shí)間(TWT)則同時(shí)受作業(yè)序列和預(yù)防性維修序列的影響.當(dāng)預(yù)防性維修次數(shù)相同時(shí)，對(duì)于相同的作業(yè)序列，TWC和TWT隨預(yù)防性維修序列的變化而小幅變化;對(duì)于相同的預(yù)防性維修序列，TWC和TWT隨作業(yè)序列的變化而發(fā)生較大幅度的變化.makespan主要受預(yù)防性維修序列的影響，作業(yè)序列對(duì)makespan的相對(duì)較小.

由表2可知，多目標(biāo)聯(lián)合預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃所得的 makespan的最小值為190.2，TWC 的最小值為105.1，TWT 的最小值為 10.7，MC的最小值為1 020.0.但沒(méi)有一組預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃使得4個(gè)目標(biāo)同時(shí)最優(yōu)，因此決策者可根據(jù)偏好信息決策出的滿意解.

表2 多目標(biāo)遺傳算法的優(yōu)化結(jié)果Table 2 Multi-objective genetic algorithms simulation results

3.2 方法對(duì)比

將本文所提的預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度多目標(biāo)聯(lián)合優(yōu)化方法分別跟單目標(biāo)聯(lián)合優(yōu)化方法和獨(dú)立優(yōu)化方法進(jìn)行比較.

1)單目標(biāo)聯(lián)合優(yōu)化方法.若應(yīng)用文獻(xiàn)［1-2］的方法，將本文所示范例進(jìn)行預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃的單目標(biāo)聯(lián)合優(yōu)化.當(dāng)優(yōu)化目標(biāo)分別為makespan和MC時(shí)，經(jīng)枚舉所得的優(yōu)化計(jì)劃結(jié)果不唯一，makespan和 MC的最小值分別為190.2和1 020.0.當(dāng)優(yōu)化目標(biāo)分別為TWC和TWT，所得最優(yōu)結(jié)果相同且唯一，預(yù)防性維修序列為0-1-1-0而生產(chǎn)作業(yè)序列為1-2-4-3，TWC和TWT分別為最小值105.1和10.7，此時(shí)makespan和MC分別為191.6 和 1 411.4.

對(duì)比表2可知，本文的多目標(biāo)聯(lián)合優(yōu)化的Pareto最優(yōu)集中包含了預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃的單目標(biāo)聯(lián)合優(yōu)化的優(yōu)化結(jié)果.當(dāng)決策者要考慮多個(gè)優(yōu)化目標(biāo)時(shí)，單目標(biāo)聯(lián)合優(yōu)化的效率顯然較差.

2)獨(dú)立優(yōu)化方法.將預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃分別進(jìn)行獨(dú)立優(yōu)化.預(yù)防性維修計(jì)劃采用使設(shè)備可用度達(dá)到最優(yōu)的基于壽命的維修策略［1］，而生產(chǎn)調(diào)度計(jì)劃采用多目標(biāo)(makespan，TWC，TWT)優(yōu)化.由文獻(xiàn)［1］可知，當(dāng) β =1.8，η =100，tp=5，tr=15時(shí)，設(shè)備從全新?tīng)顟B(tài)開(kāi)始，經(jīng)過(guò)61.5單位時(shí)間后進(jìn)行預(yù)防性維修，R(61.5)=0.66，即當(dāng)設(shè)備可靠度降到0.66時(shí)，進(jìn)行預(yù)防性維修.對(duì)生產(chǎn)調(diào)度計(jì)劃單獨(dú)進(jìn)行多目標(biāo)優(yōu)化的結(jié)果為:1-2-3-4、1-2-4-3、1-3-2-4.將2種優(yōu)化計(jì)劃組合起來(lái)，計(jì)算makespan、TWC、TWT和 MC 見(jiàn)表3.由表 3 可見(jiàn)，最優(yōu)結(jié)果為預(yù)防性維修開(kāi)始時(shí)間序列為18-79.5-141且作業(yè)序列為1-2-4-3.

表3 預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃的獨(dú)立優(yōu)化結(jié)果Table 3 Calculated results of separately optimizing PM planning and production scheduling in the example

對(duì)比表2可知，本文的多目標(biāo)聯(lián)合優(yōu)化的Pareto最優(yōu)集包含了預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度計(jì)劃獨(dú)立優(yōu)化的結(jié)果.對(duì)于表3中的任意計(jì)劃，都能從本文的多目標(biāo)聯(lián)合優(yōu)化的Pareto最優(yōu)集中找出比其更優(yōu)的計(jì)劃.因此，本文的聯(lián)合方法要優(yōu)于獨(dú)立優(yōu)化方法.

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

本文提出了單設(shè)備預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化模型.通過(guò)實(shí)例可知，一般情況下預(yù)防性維修次數(shù)越多，則突發(fā)故障的產(chǎn)生次數(shù)越少.在預(yù)防性維修成本高于小修成本的情況下，MC主要隨預(yù)防性維修次數(shù)的增多而升高.TWC和TWT則同時(shí)受作業(yè)序列和預(yù)防性維修序列的影響.Makespan主要受預(yù)防性維修序列的影響.

本文未對(duì)決策者如何從多目標(biāo)聯(lián)合優(yōu)化的Pareto最優(yōu)集中選出滿意解作闡述，當(dāng)最優(yōu)集規(guī)模較大時(shí)，這一問(wèn)題值得探討.對(duì)于多臺(tái)設(shè)備、多種預(yù)防性維修方式或flowshop生產(chǎn)計(jì)劃問(wèn)題等，還需要對(duì)預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化方法進(jìn)行更深入的研究.

［1］CASSADY C R，KUTANOGLU E.Integrating preventive maintenance planning and production scheduling for a single machine［J］.IEEE Transactions on Reliability，2005，54(2):304-309.

［2］應(yīng)保勝，但斌斌，張華.生產(chǎn)計(jì)劃和預(yù)防性維修計(jì)劃的統(tǒng)籌優(yōu)化模型［J］.機(jī)械工程學(xué)報(bào)，2005，41(3):226-228.YING Baosheng，DAN Binbin，ZHANG Hua.Optimization model by integrating preventive maintenance planning and production scheduling［J］.Chinese Journal of Mechanical Engineering，2005，41(3):226-228.

［3］SORTRAKUL N，NACHTMANN H L，CASSADY C R.Genetic algorithms for integrated preventive maintenance planning and production scheduling for a single machine［J］.Computers in Industry，2005，56(2):161-168.

［4］RUIZ R，CARLOS G J，MAROTO C.Considering scheduling and preventive maintenance in the flowshop sequencing problem［J］.Computers＆ Operations Research，2007，34(11):3314-3330.

［5］OSMAN M S，ABO-SINNA M A，MOUSA A A.An effective genetic algorithm approach to multiobjective routing problems(MORPs) ［J］.Applied Mathematics and Computation，2005，163(2):769-781.

［6］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002:115-122.WANG Xiaoping，CAO Liming.GA—theory，application and software［M］.Xi＇an:Xi＇An Jiao Tong University Press，2002:115-122.