基于多目標混合殖民競爭算法的設備維護與車間調度集成優化

宋文家　張超勇　尹　勇　邵新宇

1.華中科技大學數字制造裝備與技術國家重點實驗室，武漢，4300742.武漢理工大學湖北省數字制造重點實驗室，武漢，430070

基于多目標混合殖民競爭算法的設備維護與車間調度集成優化

宋文家1張超勇1尹勇2邵新宇1

1.華中科技大學數字制造裝備與技術國家重點實驗室，武漢，4300742.武漢理工大學湖北省數字制造重點實驗室，武漢，430070

在制定調度計劃時考慮設備預防性維護可以提高設備利用率和資產效率。首先，依據實際制造車間生產環境，在每臺機器的可靠度降低到閾值的時候安排預防性維護，建立柔性作業車間設備預防性維護與調度集成優化的數學模型，以最小化最大完工時間、總生產成本和平均總維修成本為目標。然后，提出一種多目標混合殖民競爭算法求解該模型，設計相應的編碼、解碼、殖民國家同化過程以及多目標混合殖民競爭算法的流程，并采用改進加權TOPSIS方法在獲得的Pareto解集中選擇滿意解，以達到提高設備的可靠性、按期交貨和節省成本的目的。最后通過具體實例驗證提出策略的可行性和有效性。

柔性作業車間調度問題；預防性維護；多目標混合殖民競爭算法；多目標優化

0　引言

柔性作業車間調度問題(flexible job-shop scheduling problem, FJSP) 廣泛存在于機械加工系統中，它是傳統作業車間調度問題(job-shop scheduling problem, JSP)的擴展，更貼近于制造企業實際車間的生產環境。在FJSP中，一臺機器可以加工同一工件的不同工序，同一個工序也可以在不同的幾臺機器上加工[1]。由于工件和工序沒有資源的唯一性要求，FJSP是比JSP更復雜的NP-hard問題。

在傳統作業車間調度問題中，車間設備的役齡被看作是無窮大，設備不存在故障，被看作一直可用。但是在實際情況中，隨著時間的累積，設備役齡的增加，設備不可避免地要出現故障，并且設備運行時間越長，故障的頻率會越高，甚至會發生設備整體的損壞以至于無法運行的情況。設備的重大故障會導致整個車間生產停滯，會對企業產品的交貨期產生重大影響，并給企業造成不必要的損失。所以在進行調度的時候，必須將設備維護的環節考慮進去。

設備的預防性維修(preventive maintenance，PM)是根據設備故障的統計規律制定出長遠的維修計劃，以期從總體上控制維修成本，提高設備可靠性。若維修不當，設備可能出現可靠性下降的情況, 進而導致成本損失[2]。相對于故障后維護，預防性維護更加合理有效，可以很大程度上減輕將來可能的故障對整個系統的影響。合理的預防性維修是提高設備利用率，實現資產效率最大化的有效途徑。因此，在制定調度計劃的同時，根據車間內機器設備的正常損耗和役齡的情況，把設備的合理維護考慮在車間調度之中具有重要理論意義和實際應用價值。

為了合理解決生產調度和設備維護之間的矛盾沖突，許多學者對設備維護和生產調度的集成優化問題進行了研究。Moradi等[3]以最小化最大完工時間和降低系統不可用率為優化目標，將預防性維護安排在柔性作業車間調度中固定的時間段；Li等[4]以最小化最大完工時間、機器總負荷和瓶頸機器總負荷為目標，運用化學反應算法解決整合柔性作業車間調度和預防維護的問題；Fitouhi等[5]采用了基于運行的預防性維護，這種維護方法去除了周期性的約束，降低了更多的生產和維護成本；Lu等[6]將批量生產問題和基于運行的預防性維護結合起來，并考慮了設備的可靠度約束。

有效的預防性維修和生產調度計劃集成必須同時考慮到提高生產效率和降低維修成本。在前人研究的基礎之上，本文在研究集成優化問題時不僅考慮了柔性作業車間生產時機器可靠度的動態約束，而且兼顧了設備維護的成本。

殖民競爭算法(imperialist competitive algorithm, ICA)是Atashpaz等[7]在2007年通過模擬人類社會殖民競爭過程提出的一種新穎的基于群體的元啟發式算法，實驗結果顯示該算法比遺傳算法和粒子群優化算法具有更高的優化效率和魯棒性，近年來得到了越來越廣泛的應用[8-9]。本文依據實際生產環境，建立了預防性維修和生產調度集成模型，以最小化最大完工時間、總生產成本和平均總維修成本為優化目標，在每一臺機器的維修時間段內合理安排設備維護，設計一種新穎的多目標混合殖民競爭算法求解該問題。

1　設備維護綜述

之前的文獻顯示，設備的故障一般服從指數分布，實際應用中，傾向于采用二參數威布爾分布來描述一般設備的故障規律[2]。服從威布爾分布的設備故障率函數公式為

(1)

其中，m>0,η>0。m、η均為與機器設備自身有關的參數，可以通過對不同設備故障情況的歷史數據分析得到，與時間無關。m是形狀參數，不改變分布函數的形狀，只表示函數曲線在時間坐標軸上的平行移動。形狀參數m是三個參數中最重要的一個參數，不同的m值可以決定不同的曲線形狀。η是尺度參數，只影響曲線橫軸和縱軸尺度的放大和縮小，并不影響曲線的基本形狀。

根據文獻[6]，設備在運行時刻t的可靠度Rt的計算公式為

(2)

式中，Zt為設備的役齡。

假設某臺設備的最低可靠度閾值為R′，則根據式(2)，該設備的可靠度達到閾值時的役齡Z′為

(3)

在調度的過程中，任何時刻該設備的役齡Zt均要小于Z′。

在研究設備維護的過程中，假設經過預防性維護，設備能恢復到最初的狀態或設備的可靠度不會有所增加都是不切實際的，所以根據文獻[10]的研究，可以運用一種比例的方法來恰當地表示，即役齡回退因子p(i)，假設經過預防性維護前，某設備的實際役齡是Zi，則第i次預防性維護以后，設備的實際役齡變為(1-p(i))Zi。經過預防性維護，設備的累積役齡隨時間變化的曲線如圖1所示，PM為預防性維修。

圖1　設備役齡隨時間變化的曲線

制定生產計劃時所有設備都需要在可靠度降低到閾值之前進行預防性維護，兩次維護之間的間隔時間以及每臺設備的維護總次數則要根據各個設備之前的故障狀態數據(包括維修前役齡、役齡回退因子、維修后工作時間等)來決定。

2　設備維護與調度集成模型

2.1問題描述

柔性作業車間調度問題可描述如下：若干個工件在m臺機器上加工，每個工件分為k道工序，每道工序可以在若干臺機器上加工，并且必須按一些可行的工藝次序進行加工；每臺機器可以加工工件的若干工序，并且在不同的機器上加工的工序集可以不同。此外，在加工過程中還需滿足以下約束條件：①每臺機床一次只能加工一個工件；②工序一旦進行不能中斷；③假定工件之間具備相同的優先級；④不同工件的工序之間沒有先后約束；⑤同一工件的工序之間有嚴格的順序約束。

對于本文研究的集成優化問題，在生產過程中，如果要進行設備的維護，必然要停止生產活動，這就造成了生產調度和設備維護的沖突。本文在柔性作業車間調度中安排設備維護方法借鑒Li等[4]的研究，提出一種動態安排設備維護過程，如圖2所示，Oij表示工件i的第j道工序。具體步驟如下：

(1) 先按照單純柔性作業車間問題進行決策，決定每道工序的加工順序以及加工的機器；

(4)在每臺機器上重復步驟(2)到步驟(3)，直到所有工序和PM都被安排，然后按照不同的工序、工序和PM的時間約束調整調度安排。

圖2　動態安排設備維護的過程

當然，PM以后工件加工順序如果做某些改變，有可能會減小最大完工時間。這些會在算法中的帝國內同化環節和模擬退火環節中實現。

2.2數學模型

本文對設備的預防性維修和生產調度進行有機集成，將生產成本和多臺設備的平均維護成本也作為模型的優化目標。把設備的維護考慮在作業計劃之中，以最小化最大完工時間、總生產成本和平均總維修成本為目標，根據設備的可靠度要求，在調度過程中動態地決定每臺設備預防性維護的開始時刻，制定設備維護和各個工序的生產計劃。建立的數學模型如下：

(1)最大完工時間為

f1=max(ten,jk|j=1,2,…,n;k=1,2,…,kj)

(4)

(2)總生產成本為

(5)

(3)平均總維修成本為

(6)

該模型的約束條件如下：

tbe,jk+Xijktijk=ten,jk

(7)

ten,jk≤tbe,j(k+1)

(8)

(9)

tbe,jk+tijk≤ten,hl+L(1-yijkhl)

(10)

(11)

[(tmc,i-tp,i-ten,jk)Xijk≥0]∪

[(ten,jk-tmc,i-tijk)Xijk≥0]?(i,j,k,l)

(12)

式中，j、k、kj分別表示n個工件中第j工件，某個工件的第k工序，工件j包含的工序數量；Mjk為工件j的第k個工序可用的機器集合，Mjk?{1, 2,…,m};Xijk為工件j的第k個工序是否在機器i上加工；npr,i為機器i上預防性維護的次數；pi為設備i故障導致的生產損失；tijk為工件j的第k工序在機器i上的加工時間，i? Mjk；Ci為機器i上單位時間的加工成本；Cs,i為機器i維修固定費用；Cm,i為機器i的故障后維修成本；Cp,i為機器i預防性維護所需成本；Rit為機器i在時刻t的可靠度；Ri′為機器i的可靠度閾值；tbe,jk為工件j 的第k工序開始的時間；ten,jk為工件j 的k工序完工時間；tp,i為機器i預防性維護所需時間；tmc,i為機器i的維護結束時刻；Ni(Δt)為Δt時間段內設備i發生故障的次數；L 為一個足夠大的正數。

式(7)和式(8)表示每個工件的加工工序的順序約束；式(9)表示機器約束；式(10)表示在特定的時刻，一臺機器只能加工一種工件的一種工序；式(11)表示在任意時刻t，設備i的可靠度不能低于可靠度閾值；式(12)表示同一臺機器上設備預防性維護和工序的加工不能存在沖突。

3　多目標混合殖民競爭算法求解設備維護與柔性作業車間調度集成問題

殖民競爭算法的流程為初始化每個個體為一個“國家”，根據國家能量的不同將這些國家分為“殖民國家”和“殖民地”，將殖民地分給不同的殖民國家來形成一個個的“帝國”；然后，在帝國內進行殖民地同化操作和帝國之間殖民競爭，帝國同化操作是殖民地受到殖民國家的同化作用，使得自身解的結構和殖民國家更接近；殖民競爭是找出當前能量最弱帝國內部的最弱殖民地，將此殖民地設置為自由狀態根據各個帝國的總能量和隨機數來確定哪個帝國獲得該殖民地。殖民地改革是選出所有國家中能量最弱的國家，將該國家用一個隨機產生的新國家替換掉[11]。

殖民競爭算法的操作特點使得算法中的較劣解能夠和較優解相互作用，相比于遺傳算法，殖民競爭算法中的較劣解可以向更優解更快速地移動，亦或能產生比較優解更優的解。但是殖民競爭算法的特點也可能使算法陷入局部最優解不容易跳出，模擬退火算法的思想是通過對已有的解運用某種鄰域結構進行擾動來進行局部搜索，試圖得到新的解，可以使得算法跳出局部最優。所以本文對已有的殖民競爭算法加入模擬退火環節，可以將兩種算法的特點結合起來，使得該算法更加適合于求解本文研究的集成優化問題。這樣雖然算法的時間復雜度會有所增加，但會使得新算法的全局和局部搜索的能力都比較強。

殖民國家內競爭、殖民競爭和殖民地改革等過程參考文獻[7]，本文只對帝國初始化和帝國內同化等過程進行設計。

3.1初始化

對于多目標問題，初始化時各個解的質量直接影響算法的收斂速度以及最終求解出的Pareto解集中的解的整體質量，所以必須選擇比較好的編碼方式，力求使初始化時產生的解的質量比較高。

柔性作業車間的殖民競爭算法采用兩條編碼，一條是基于工序的編碼，用于說明不同工件的不同工序的加工先后順序；另一條是基于機器的編碼，用來確定具體每個工件的每個工序在哪一臺機器上加工。

3.1.1工序序列的編碼

在基于工序的編碼中，每個數字代表一個工件，數字出現的次數等于該數字對應工序的個數。且第k次出現的一個數字代表該數字對應的工件的第k個工序，例如編碼[1 2 2 1 3 1 2 3]，表明工件1有三個工序，工件2有三個工序，工件3有兩個工序。本文算法在國家初始化時，對于基于工序的編碼采用隨機交換的方法，將所有工件的工序按照順序依次排列，如[1 1 1 2 2 2 3 3]，然后隨機交換工序位置，就產生了該國家內基于工序編碼的序列，如[1 3 1 2 2 1 3 2]。

3.1.2機器序列的編碼

基于機器的工序中，將各個工件的工序按照順序排列下來，然后每個位置上對應的機器就是對應工序所在的機器。如編碼[1 3 1 2 2 1 3 2]表明工件1的三個工序分別在機器1、3、1上加工；工件2的三個工序在機器2、2、1加工；工件3的兩個工序在機器3、2上加工。

為每個工序分配機器的時候要考慮該工序在不同可加工機器上的加工時間，最好選擇最小值對應的機器來安排，同時又要兼顧考慮每臺機器已經分配的負載情況，不能使某臺機器的負載過大。因此，本文為了提高初始解的質量，借鑒了Kacem等[12]提出的利用時間表的分配方法(approach by locallization,AL)和Pezzella等[13]的改進分配規則來進行編碼，使得編碼的魯棒性比較強，進而得到質量比較高的初始解。但是這兩篇文獻中都沒有考慮不同工件以及同一工件的不同工序的加工順序。

本文在文獻[12]的基礎上對機器序列的初始化進一步改進，即將加工時間的表格按照已經確定的工序排序從上到下對每行重新排序，首先分配排在第一位的工序，選擇加工該工序時間最短的某臺機器分配給該工序，然后將表中該機器對應的加工時間列在該行之后的所有值均增加該工序的加工時間，表示該機器負載已經增加。接著對剩下的每個工序都按照一樣的操作，最終確定對應該工序編碼的機器分配方案，過程如表1所示，對于基于工序的序列[1 3 1 2 2 1 3 2]，Mi為第i臺機器，首先將工序O11安排到最小加工時間的M3，將M3剩余可加工的工序時間增加4，再安排O31，最終的安排如表1最右邊三列所示，得到的基于機器編碼的序列為[3 1 2 3 1 3 2 1]。

表1　為已排序的工序安排加工機器的過程

由于要保證初始解的多樣性，本文算法中一半初始解的機器編碼采用表1的方法，另一半初始解的機器編碼采用在該工序可用機器集合中隨機分配機器的編碼方法。

由兩列編碼就可以結合之前描述的動態安排設備預防性維護的方法，在某臺機器上安排某工序后，若再安排下一道工序的加工就將使得設備可靠度低于閾值水平的時候，就在該工序之后進行預防性維護。解碼后畫出相對應的甘特圖，如圖3所示，進行PM的時間均是根據機器可靠度的變化情況來決定的。

圖3　甘特圖示例

3.2帝國內同化

帝國內同化就是在一個帝國內，所有的殖民地都要受到殖民國家的同化作用，使得所有殖民國家都朝比較好的解來轉化。本文算法的同化過程采用交叉和變異操作，各個殖民國家均要和所在帝國的殖民地進行交叉操作來進行同化，同化之后得到的新解或許會支配原來的解，這時就將原來的解用新解替換掉；新解也或許會和已有的Pareto解集中的解處于同一Pareto等級，這時就將新解保留到Pareto解集中。由于要保證交叉變異以后得到的子代都是問題的可行解，故一個國家內的兩條編碼所需要的交叉變異方式是不相同的。

3.2.1交叉操作

針對柔性作業車間調度的復雜性，殖民競爭算法中一個國家內兩條編碼的交叉分別進行，其中第一部分基于工序的編碼采用元素分集合的交叉方法，第二部分基于機器的編碼采用一種新型多點交叉的方法。

(1)基于工序編碼的交叉。該條編碼交叉的過程是：將所有的工件隨機分為兩個集合J1、J2，新國家內的編碼先是繼承殖民國家中集合J1內的工件對應的元素，而后將殖民地中集合J2內的工件對應的元素分別填充到新國家內的編碼空缺的元素中，如圖4所示，其中J1={2, 3}。

圖4　基于工序編碼的交叉

(2)基于機器編碼的交叉。基于機器的編碼采用多點交叉的方法，具體操作是：先隨機產生一條和編碼等長的0-1序列，將殖民國家中與0-1序列中的0位置相同的所有元素復制到新國家中，殖民地中與0-1序列中的1位置相同的所有元素復制到新國家中，如圖5所示。

圖5　基于機器編碼的交叉

3.2.2變異操作

(1)基于工序編碼的變異。基于工序編碼的序列串采用交換與插入變異，即從編碼串中隨機選取一個元素，然后隨機插入到編碼的其他位置，如圖6所示。

圖6　基于工序編碼的變異

(2)基于機器編碼的變異。不同工件的不同工序可選擇的機器各不相同，所以這部分編碼的變異采用隨機選取某個工件的某個工序，將該工序的加工機器隨機替換成該工序可選擇機器集合中的其他機器，如圖7所示。

圖7　基于機器編碼的變異

3.3Pareto求解及排序

本文采取一種效率較高的Pareto解集求解和排序方法。設群體的規模大小為NP，將群體按照支配關系分類排序為m個子集P1，P2，…，Pm，這些子集中兩兩之間無交集，且滿足P1?P2?…?Pm，即Pk+1中的個體直接受Pk中的個體支配(k=1, 2,…,m-1)。經過排序之后，候選解就會不斷集散到最優解集的邊界上。傳統的排序方法構造非支配集時，到了后期可能出現所有的或絕大多數個體均為非支配解，這樣一來排序速度就會變得很慢。為了克服排序速度慢的問題，本文采用一種新型的快速排序方法。將傳統的一個比較個體改為兩個比較個體，其中第二個個體與第一個個體不相關或第二個個體支配第一個個體，這樣，算法具有更高的工作效率，降低了時間復雜度。算法程序具體如下：

Function improved_quick_sort(pop){

while(|pop|>1){

randomly select a∈pop;

set *b=pop[0];

while(a?*b)

b++;

for(int i=0;i

if(a?pop[i]||b?pop[i])

delete pop[i] from pop;

}

}

}

3.4適應度函數

本文采用Enayatifar等[9]提出的目標組合法來量化每一個國家，即

(13)

其中，Pareto最優解集的名次被設定為1，cn是個體n的適應度，fk(n)是個體 n 的第 k 個目標值，Nrank是指相同層次Pareto解集里面的個體數。rank(n)是0～1之間的隨機數。該公式可以區分不同Pareto層次的個體適應度大小。然后可以根據下式計算各個國家標準化之后的能量：

Cn=max(cn)-cn

(14)

式中，Cn為第n個殖民國家標準化之后的成本值，即適應度。

標準化之后的成本Cn代表了殖民國家的能量，即對于最小化問題來說，成本越小，能量越大。然后可以計算第n個殖民國家的殖民地數量：

(15)

其中，Ncol是殖民地數量，Nimp是殖民國家的數量。殖民國家成本越高，其殖民地越多。

3.5多目標混合殖民競爭算法

(16)

本文對已知解中基于工序編碼的擾動方式采用趙良輝等[15]提出的2變換鄰域搜索。2變換鄰域就是將已知解i的編碼首尾相接，從中任取兩點，將兩點間的路徑反向后形成的新解的集合稱為i的2變換鄰域，搜索時從舊解的2變換鄰域中隨機挑選一個作為新解。由于基于機器編碼的可行性要求比較高，對于已知解中基于機器編碼的擾動采用本文提出的機器編碼的變異方式來進行。

在本文中，模擬退火環節的步驟如下：

(1)帝國同化后，將所有的國家合并，計算每個國家的能量值；

(2)對當前所有國家依次進行擾動產生新的國家，如果新國家支配舊國家，則用新國家替換舊國家，否則按照概率決定是否接受新國家到合并的國家中；

(3)在溫度為T的時候，對每個國家進行一定次數的擾動；

(4)使溫度以衰減率α緩慢降低，即Tk+1=Tkα，α∈(0, 1)；

(5)重復步驟(2)到步驟(4)，直至滿足停止條件。

多目標混合殖民競爭算法的步驟如下：

(1)選擇算法各個參數并運用本文的初始化方法生成國家群體；

(2)用快速排序法得到所有國家的Pareto排序，計算各個國家的適應度；

(3)判斷是否滿足算法終止的條件，即達到預設的代數或帝國數量是1；

(4)根據適應度選出殖民國家，并計算隸屬各個殖民國家的殖民地數量，按照數量將所有殖民地隨機分配給殖民國家；

(5)帝國內同化；

(6)模擬退火算法對各個國家進行擾動，尋找更優解；

(7)將所有國家重新進行Pareto排序，計算適應度，進而重新選定殖民國家及隸屬各個殖民國家的殖民地；

(8)殖民競爭；

(9)殖民地改革；

(10)刪除帝國；

(11)重復步驟(3)到步驟(9)；

(12)輸出并保存最終的Pareto解集。

多目標混合殖民競爭算法的流程如圖8所示。

圖8　多目標殖民競爭算法流程圖

3.6算法的時間復雜度分析

初始化的過程主要與初始國家數量P，所有工序的數量N和機器數量M有關，每道工序安排以后，就要相應地更新工序-機器時間表，因此初始化過程的時間復雜度是O(PN2M)，在一次迭代操作中，帝國內同化，殖民競爭和殖民地改革的時間復雜度均為O(NeNc)，其中，Ne和Nc分別代表殖民國家的數量和每個帝國中殖民地的數量，而模擬退火環節的時間復雜度為O(NMlogCr(Tf/T0))，其中，T0代表初始溫度，Tf代表終止溫度，Cr代表降溫系數；根據快速排序法的計算方法，該環節的時間復雜度為O((NeNc)log2(NeNc))。本文提出的多目標混合殖民競爭算法總的時間復雜度為O(PN2M)+ GO(NM)+GO(PN2M2logCr(Tf/T0))，G是算法的迭代次數。可以看出本文提出算法的時間復雜度與種群大小、算法迭代次數、問題規模以及參數的大小有關。

4　算法測試與比較結果分析

為了驗證提出的多目標混合殖民競爭算法的有效性，本文的測試分為兩部分，第一部分是將文獻[4]中三個實例作為基準實例進行測試，三個實例均是整合柔性作業車間調度和預防性維護的問題，以最小化最大完工時間、機器總負荷和瓶頸機器總負荷為目標，由于這三個實例模型的目標和本文模型的目標不同，故將本文算法的目標改為三個實例中的目標；第二部分是本文模型的具體實例測試，針對考慮維修成本的設備維護與車間調度集成的問題，把本文提出MOHICA算法與傳統多目標殖民競爭算法[7](multi-objective imperialist competitive algorithm，MOICA)(不考慮模擬退火算法)，以及文獻[1]改進非支配排序遺傳算法(NSGA-Ⅱ)進行比較。

4.1基準實例測試

本文提出的多目標混合殖民競爭算法采用C++語言編程，計算機運行環境為2.5 GHz Intel Core i5多核CPU和2GB RAM 的個人計算機，算法的有關參數設置如下：群規模NP=100，帝國數量為10，殘民地數量為190，G= 100；對于模擬退火環節的參數，本文取初始溫度T=1000，溫度衰減率α=0.8，終止溫度Tf=1，在溫度T時，每個國家進行n=5次的擾動。三個基準實例分別是8×8、10×10和15×10的整合柔性作業車間調度和預防性維護的問題。文獻[4]中的幾種不同算法(混合遺傳算法(hGA)、基于過濾束搜索的算法(FBS-based)和(離散化學反應算法DCRO)算法)和本文MOHICA算法分別得到的Pareto解如表2所示，f1、f2和f3分別表示最大完工時間、機器總負荷和瓶頸機器總負荷。由表2可以看出，本文的MOHICA算法求解基準實例得到的Pareto解集中解的質量不比前三種算法的質量差，對于前兩個基準實例，部分解的f2目標的值比其他算法得到的所有值更優，而且可以得到數量更多的Pareto解。

表2　幾種不同的算法求解基準實例的Pareto對比

4.2具體實例的測試

4.2.1測試數據

在具體測試實例中，柔性作業車間調度的數據來自文獻[1]，是一個10×8的問題，每臺設備的歷史維護數據來自現實制造車間數據[10]，并針對測試實例進行調整，如表3所示。在表3中，ηi和mi分別是設備的形狀參數和尺度參數，此外，假設每臺設備的可靠度閾值為0.85。

表3　8臺機器的設備維護數據

假設設備i經過第j次預防性維修之前的役齡為Zij，并且維修后又運行了Δt的時間，則根據文獻[10]，經過維護以后設備i在時刻t的故障強度λij也會以比例p(i)降低，計算公式為

λij(t)=λi0(t)-p(i)λi0(Zij)

(17)

所以第j次預防性維修之后到第j+1次維修之間，設備故障發生次數平均值Nij(Δt)計算的公式為

(18)

進而可以得到設備在一次預防性維護到下一次維護這段時間內的平均故障后維修費用：

(pi+Cs,i+Cm,i)

(19)

4.2.2具體實例測試結果

本文算法的參數設置與基準實例測試時的設置相同，對比的MOICA算法除了沒有模擬退火環節，其余的參數設置與MOHICA相同，對于比較算法NSGA-Ⅱ，將初始化編碼、交叉和變異的方式改為適合本文算例的方式，參數設置如下：種群規模NP=100，改進優先工序交叉概率50%，多點交叉50%，兩種序列變異操作的變異概率各為2%，選擇概率值r=0.9，最大進化代數100。采用三種算法求解上述實例得出各自的Pareto解集，如表4所示，MT、PC和MC分別代表最大完工時間、總生產費用和平均維護費用。

表4　三種算法得到的Pareto解集

為了比較這三個多目標算法的結果，將Pareto最優解的平均比率作為一個量化比較對象。讓P1和P2分別代表兩個算法計算得到的Pareto最優解，P是P1和P2的并集(P=P1∪P2)，即P中僅含有非支配解。所以Pi中的Pareto最優解不被P中的解支配的比率RPOS(Pi)為

(20)

比率越大，證明算法效果越好。本文算法與兩個對比算法的比率計算結果如表5所示。

表5　多目標算法比較結果

圖9和圖10分別給出了MOHICA與NSGA-Ⅱ算法和MOICA的對比Pareto前沿圖。

圖9　MOHICA和NSGA-Ⅱ的Pareto前沿的比較

圖10　MOHICA和普通MOICA的Pareto前沿比較

從表5可以看出，MOHICA算法的所有比率值都是1，表明通過本文算法得到的結果均沒有受普通MOICA算法和NSGA-Ⅱ算法得到的解支配，顯示MOHICA算法具有較強的搜索能力。從圖9、圖10可以看出，MOHICA算法得到的Pareto解的曲面在NSGA-Ⅱ算法和MOICA算法得到的Pareto解的曲面下邊，更靠近“原點”，說明由MOHICA算法得到的解可以支配參考算法得到的解集。由表5和圖9、圖10可以看出，MOHICA算法能得到質量更優的Pareto解。

4.3Pareto解集的決策

MOHICA算法獲得一組Pareto解集后，車間調度員還面臨如何從這組Pareto解集選出滿意方案的問題，這需要根據決策者主觀經驗(如依據決策指標重要性的排序)或多指標決策技術進行排序或評估。

本文采用張洪等[16]提出的改進加權優劣解距離(TOPSIS)法，對基本的TOPSIS法增加了權重的因素，使決策過程更加科學。該方法的步驟為：首先將目標值矩陣的各元素取倒數轉換為高優指標Xij；然后將每個目標值進行歸一化處理，處理后值為aij，aij計算公式為

(21)

通過式(21)得到變換后矩陣；再將矩陣每一列目標值中的最優值組合成理想最優解，最差值組合成最劣解。計算公式為

(22)

圖11　得到滿意解的甘特圖

5　結語

本文以最小化最大完工時間、總生產成本和平均總維修成本為目標，建立基于可靠度約束的設備預防性維護與柔性作業車間調度集成的模型，提出了一種多目標混合殖民競爭算法求解該問題，設計了相應的編碼、解碼、帝國同化等操作，得到較好的初始化解。算法中加入模擬退火環節，避免陷入局部最優，并且力求得到質量更好的解。通過基準實例和具體實例跟其他算法比較驗證了提出算法的有效性，最后采用改進加權TOPSIS法幫助決策者在獲得的Pareto集中選出滿意解。

[1]張超勇，董星，王曉娟，等. 基于改進非支配排序遺傳算法的多目標柔性作業車間調度[J]. 機械工程學報, 2010, 46(11)：156-164.

Zhang Chaoyong，Dong Xing，Wang Xiaojuan，et al. Improved NSGA-Ⅱ for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2010，46(11)：156-164.

[2]王靈芝, 徐宇工, 張家棟. 以可靠性為中心的多部件系統預防性維修優化研究[J]. 計算機集成制造系統, 2008, 14(10): 2043-2046.

Wang Lingzhi，Xu Yugong，Zhang Jiadong. Optimization of Reliability-centered Preventive Maintenance for Multi-component Systems[J]. Computer Integrated Manufacturing Systems,2008, 14(10): 2043-2046.

[3]Moradi E, Fatemi Ghomi S M T, Zandieh M, et al. Bi-objective Optimization Research on Integrated Fixed Time Interval Preventive Maintenance and Production for Scheduling Flexible Job-shop Problem[J]. Expert Systems with Applications，2011，38(6): 7169-7178.

[4]Li J Q, Pan Q K. Chemical-reaction Optimization for Flexible Job-shop Scheduling Problems with Maintenance Activity[J]. Applied Soft Computing 2012，2(9): 2896-2912.

[5]Fitouhi M C, Nourelfath M. Integrating Noncyclical Preventive Maintenance Scheduling and Production Planning for a Single Machine[J]. International Journal of Production Economics,2012，136(2):344-351.

[6]Lu Z Q, Zhang Y J, Han X L. Integrating Run-based Preventive Maintenance into the Capacitated Lot Sizing Problem with Reliability Constraint[J]. International Journal of Production Economics,2013，51(5):1379-1391.

[7]Atashpaz G E, Lucas C. Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition[C]//Evolutionary Computation, CEC 2007. Singapore,2007: 4661-4667.[8]Gargari E A, Hashemzadeh F, Rajabioun R, et al. Colonial Competitive Algorithm: A Novel Approach for PID Controller Design in MIMO Distillation Column Process[J]. International Journalof Intelligent Computing and Cybernetics, 2008, 1(3):337-355.[9]Enayatifar R, Yousefi M, Abdullah H, et al. MOICA: A Novel Multi-objective Approach Based on Imperialist Competitive Algorithm[J]. Applied Mathematics and Computation, 2013, 219(17): 8829-8841.

[10]劉繁茂. 面向故障過程的多設備可靠性分析與維修決策[D]. 武漢：華中科技大學，2010.

[11]連坤雷. 殖民競爭算法在離散制造系統優化問題中的應用研究[D].武漢：華中科技大學，2012.

[12]Kacem I, Hammadi S, Borne P. Approach by Localization and Multiobjective Evolutionary Optimization for Flexible Job-shop Scheduling Problems[J]. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 2002, 32(1): 1-13.

[13]Pezzella F, Morganti G, Ciaschetti G. A Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Computers & Operations Research, 2008, 35(10): 3202-12.

[14]程博，楊育，劉愛軍, 等，基于遺傳模擬退火算法的大件公路運輸路徑選擇優化[J].計算機集成制造系統，2013，19(4)：881-882.

Cheng Bo，Yang Yu，Liu Aijun,et al. Highway Transportation Route Selection Optimization Based on Improved Genetic Annealing Algorithm[J]. Computer Integrated Manufacturing Systems，2013，19(4)：881-882.

[15]趙良輝,鄧飛其. 用于作業車間調度的模擬退火算法[J]. 制造業自動化, 2006, 28(3): 10-13.

Zhao Lianghui, Deng Feiqi. A Simulated Annealing Algorithm on Solving Job Shop Scheduling Problem[J]. Manufacturing Automation, 2006, 28(3): 10-13.

[16]張洪，張燕. 基于加權TOPSIS法的旅游資源區際競爭力比較研究[J]. 長江流域資源與環境，2010，19(5)：501-503.

Zhang Hong, Zhang Yan. Comparative Analysis on Regional Competitiveness of Tourism Resources Based on Weighted TOPSIS Method[J]. Resources and Environment in the Yangtze Basin，2010，19(5)：501-503.

(編輯袁興玲)

Integrated Optimization of Equipment Maintenance and Shop Scheduling Problem Based on Multi-objective Hybrid Imperialist Competitive Algorithm

Song Wenjia1Zhang Chaoyong1Ying Yong2Shao Xinyu1

1.State Key Laboratory of Digital Manufacturing Equipment and Technology,Huazhong University of Science and Technology,Wuhan,430074 2.Hubei Key Laboratory of Broadband Wireless Communication and Sensor Networks,Wuhan University of Technology,Wuhan,430070

In order to improve equipment utilization rate and maximize the efficiency of assets, preventive maintenance should be considered in production plan.A mathematical model to optimize the integrated flexible job shop equipment preventive maintenance and scheduling problem was established based on the real environment of the manufacturing shop with three objectives, including minimizing makespan, production cost, and average maintenance cost. An improved algorithm, which was referred to MOHICA, was proposed to solve the problem. This paper designed the process of encoding, decoding and empire assimilation as well as the procedure of MOHICA.An improved weighted TOPSIS (technique for order preference by similarity to an ideal solution) method was employed to choose the most satisfactory solution in the Pareto-optimal solutions to achieve the purposes of improving the reliability of the equipment, in-time delivery and saving cost. To validate the proposed strategy,an experimental test on a real-world instance was conducted. The computational results indicate that the proposed model is feasible and the algorithm is effective.

flexible job shop scheduling problem; preventive maintenance; multi-objective hybrid imperialist competitive algorithm(MOHICA); multi-objective optimization

2014-07-11

國家自然科學基金資助重點項目(51035001 )；國家自然科學基金資助項目(51275190 )；中央高校基本科研業務費資助項目(2014TS038)

TP18DOI：10.3969/j.issn.1004-132X.2015.11.010

宋文家，男，1991年生。華中科技大學數字制造裝備與技術國家重點實驗室碩士研究生。主要研究方向為現代優化算法、設備預防性維護與調度。張超勇，男，1972年生。華中科技大學數字制造裝備與技術國家重點實驗室副教授。尹勇，男，1976年生。武漢理工大學湖北省數字制造重點實驗室教授。邵新宇，男，1968年生。華中科技大學數字制造裝備與技術國家重點實驗室教授。