宋文家　張超勇　尹　勇　邵新宇

1.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，4300742.武漢理工大學(xué)湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，武漢，430070

基于多目標(biāo)混合殖民競(jìng)爭(zhēng)算法的設(shè)備維護(hù)與車間調(diào)度集成優(yōu)化

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

1.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，4300742.武漢理工大學(xué)湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，武漢，430070

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

柔性作業(yè)車間調(diào)度問(wèn)題；預(yù)防性維護(hù)；多目標(biāo)混合殖民競(jìng)爭(zhēng)算法；多目標(biāo)優(yōu)化

0　引言

柔性作業(yè)車間調(diào)度問(wèn)題(flexible job-shop scheduling problem, FJSP) 廣泛存在于機(jī)械加工系統(tǒng)中，它是傳統(tǒng)作業(yè)車間調(diào)度問(wèn)題(job-shop scheduling problem, JSP)的擴(kuò)展，更貼近于制造企業(yè)實(shí)際車間的生產(chǎn)環(huán)境。在FJSP中，一臺(tái)機(jī)器可以加工同一工件的不同工序，同一個(gè)工序也可以在不同的幾臺(tái)機(jī)器上加工[1]。由于工件和工序沒(méi)有資源的唯一性要求，F(xiàn)JSP是比JSP更復(fù)雜的NP-hard問(wèn)題。

在傳統(tǒng)作業(yè)車間調(diào)度問(wèn)題中，車間設(shè)備的役齡被看作是無(wú)窮大，設(shè)備不存在故障，被看作一直可用。但是在實(shí)際情況中，隨著時(shí)間的累積，設(shè)備役齡的增加，設(shè)備不可避免地要出現(xiàn)故障，并且設(shè)備運(yùn)行時(shí)間越長(zhǎng)，故障的頻率會(huì)越高，甚至?xí)l(fā)生設(shè)備整體的損壞以至于無(wú)法運(yùn)行的情況。設(shè)備的重大故障會(huì)導(dǎo)致整個(gè)車間生產(chǎn)停滯，會(huì)對(duì)企業(yè)產(chǎn)品的交貨期產(chǎn)生重大影響，并給企業(yè)造成不必要的損失。所以在進(jìn)行調(diào)度的時(shí)候，必須將設(shè)備維護(hù)的環(huán)節(jié)考慮進(jìn)去。

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

為了合理解決生產(chǎn)調(diào)度和設(shè)備維護(hù)之間的矛盾沖突，許多學(xué)者對(duì)設(shè)備維護(hù)和生產(chǎn)調(diào)度的集成優(yōu)化問(wèn)題進(jìn)行了研究。Moradi等[3]以最小化最大完工時(shí)間和降低系統(tǒng)不可用率為優(yōu)化目標(biāo)，將預(yù)防性維護(hù)安排在柔性作業(yè)車間調(diào)度中固定的時(shí)間段；Li等[4]以最小化最大完工時(shí)間、機(jī)器總負(fù)荷和瓶頸機(jī)器總負(fù)荷為目標(biāo)，運(yùn)用化學(xué)反應(yīng)算法解決整合柔性作業(yè)車間調(diào)度和預(yù)防維護(hù)的問(wèn)題；Fitouhi等[5]采用了基于運(yùn)行的預(yù)防性維護(hù)，這種維護(hù)方法去除了周期性的約束，降低了更多的生產(chǎn)和維護(hù)成本；Lu等[6]將批量生產(chǎn)問(wèn)題和基于運(yùn)行的預(yù)防性維護(hù)結(jié)合起來(lái)，并考慮了設(shè)備的可靠度約束。

有效的預(yù)防性維修和生產(chǎn)調(diào)度計(jì)劃集成必須同時(shí)考慮到提高生產(chǎn)效率和降低維修成本。在前人研究的基礎(chǔ)之上，本文在研究集成優(yōu)化問(wèn)題時(shí)不僅考慮了柔性作業(yè)車間生產(chǎn)時(shí)機(jī)器可靠度的動(dòng)態(tài)約束，而且兼顧了設(shè)備維護(hù)的成本。

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

1　設(shè)備維護(hù)綜述

之前的文獻(xiàn)顯示，設(shè)備的故障一般服從指數(shù)分布，實(shí)際應(yīng)用中，傾向于采用二參數(shù)威布爾分布來(lái)描述一般設(shè)備的故障規(guī)律[2]。服從威布爾分布的設(shè)備故障率函數(shù)公式為

(1)

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

根據(jù)文獻(xiàn)[6]，設(shè)備在運(yùn)行時(shí)刻t的可靠度Rt的計(jì)算公式為

(2)

式中，Zt為設(shè)備的役齡。

假設(shè)某臺(tái)設(shè)備的最低可靠度閾值為R′，則根據(jù)式(2)，該設(shè)備的可靠度達(dá)到閾值時(shí)的役齡Z′為

(3)

在調(diào)度的過(guò)程中，任何時(shí)刻該設(shè)備的役齡Zt均要小于Z′。

在研究設(shè)備維護(hù)的過(guò)程中，假設(shè)經(jīng)過(guò)預(yù)防性維護(hù)，設(shè)備能恢復(fù)到最初的狀態(tài)或設(shè)備的可靠度不會(huì)有所增加都是不切實(shí)際的，所以根據(jù)文獻(xiàn)[10]的研究，可以運(yùn)用一種比例的方法來(lái)恰當(dāng)?shù)乇硎?，即役齡回退因子p(i)，假設(shè)經(jīng)過(guò)預(yù)防性維護(hù)前，某設(shè)備的實(shí)際役齡是Zi，則第i次預(yù)防性維護(hù)以后，設(shè)備的實(shí)際役齡變?yōu)?1-p(i))Zi。經(jīng)過(guò)預(yù)防性維護(hù)，設(shè)備的累積役齡隨時(shí)間變化的曲線如圖1所示，PM為預(yù)防性維修。

圖1　設(shè)備役齡隨時(shí)間變化的曲線

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

2　設(shè)備維護(hù)與調(diào)度集成模型

2.1問(wèn)題描述

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

對(duì)于本文研究的集成優(yōu)化問(wèn)題，在生產(chǎn)過(guò)程中，如果要進(jìn)行設(shè)備的維護(hù)，必然要停止生產(chǎn)活動(dòng)，這就造成了生產(chǎn)調(diào)度和設(shè)備維護(hù)的沖突。本文在柔性作業(yè)車間調(diào)度中安排設(shè)備維護(hù)方法借鑒Li等[4]的研究，提出一種動(dòng)態(tài)安排設(shè)備維護(hù)過(guò)程，如圖2所示，Oij表示工件i的第j道工序。具體步驟如下：

(1) 先按照單純?nèi)嵝宰鳂I(yè)車間問(wèn)題進(jìn)行決策，決定每道工序的加工順序以及加工的機(jī)器；

(4)在每臺(tái)機(jī)器上重復(fù)步驟(2)到步驟(3)，直到所有工序和PM都被安排，然后按照不同的工序、工序和PM的時(shí)間約束調(diào)整調(diào)度安排。

圖2　動(dòng)態(tài)安排設(shè)備維護(hù)的過(guò)程

當(dāng)然，PM以后工件加工順序如果做某些改變，有可能會(huì)減小最大完工時(shí)間。這些會(huì)在算法中的帝國(guó)內(nèi)同化環(huán)節(jié)和模擬退火環(huán)節(jié)中實(shí)現(xiàn)。

2.2數(shù)學(xué)模型

本文對(duì)設(shè)備的預(yù)防性維修和生產(chǎn)調(diào)度進(jìn)行有機(jī)集成，將生產(chǎn)成本和多臺(tái)設(shè)備的平均維護(hù)成本也作為模型的優(yōu)化目標(biāo)。把設(shè)備的維護(hù)考慮在作業(yè)計(jì)劃之中，以最小化最大完工時(shí)間、總生產(chǎn)成本和平均總維修成本為目標(biāo)，根據(jù)設(shè)備的可靠度要求，在調(diào)度過(guò)程中動(dòng)態(tài)地決定每臺(tái)設(shè)備預(yù)防性維護(hù)的開始時(shí)刻，制定設(shè)備維護(hù)和各個(gè)工序的生產(chǎn)計(jì)劃。建立的數(shù)學(xué)模型如下：

(1)最大完工時(shí)間為

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

(4)

(2)總生產(chǎn)成本為

(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個(gè)工件中第j工件，某個(gè)工件的第k工序，工件j包含的工序數(shù)量；Mjk為工件j的第k個(gè)工序可用的機(jī)器集合，Mjk?{1, 2,…,m};Xijk為工件j的第k個(gè)工序是否在機(jī)器i上加工；npr,i為機(jī)器i上預(yù)防性維護(hù)的次數(shù)；pi為設(shè)備i故障導(dǎo)致的生產(chǎn)損失；tijk為工件j的第k工序在機(jī)器i上的加工時(shí)間，i? Mjk；Ci為機(jī)器i上單位時(shí)間的加工成本；Cs,i為機(jī)器i維修固定費(fèi)用；Cm,i為機(jī)器i的故障后維修成本；Cp,i為機(jī)器i預(yù)防性維護(hù)所需成本；Rit為機(jī)器i在時(shí)刻t的可靠度；Ri′為機(jī)器i的可靠度閾值；tbe,jk為工件j 的第k工序開始的時(shí)間；ten,jk為工件j 的k工序完工時(shí)間；tp,i為機(jī)器i預(yù)防性維護(hù)所需時(shí)間；tmc,i為機(jī)器i的維護(hù)結(jié)束時(shí)刻；Ni(Δt)為Δt時(shí)間段內(nèi)設(shè)備i發(fā)生故障的次數(shù)；L 為一個(gè)足夠大的正數(shù)。

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

3　多目標(biāo)混合殖民競(jìng)爭(zhēng)算法求解設(shè)備維護(hù)與柔性作業(yè)車間調(diào)度集成問(wèn)題

殖民競(jìng)爭(zhēng)算法的流程為初始化每個(gè)個(gè)體為一個(gè)“國(guó)家”，根據(jù)國(guó)家能量的不同將這些國(guó)家分為“殖民國(guó)家”和“殖民地”，將殖民地分給不同的殖民國(guó)家來(lái)形成一個(gè)個(gè)的“帝國(guó)”；然后，在帝國(guó)內(nèi)進(jìn)行殖民地同化操作和帝國(guó)之間殖民競(jìng)爭(zhēng)，帝國(guó)同化操作是殖民地受到殖民國(guó)家的同化作用，使得自身解的結(jié)構(gòu)和殖民國(guó)家更接近；殖民競(jìng)爭(zhēng)是找出當(dāng)前能量最弱帝國(guó)內(nèi)部的最弱殖民地，將此殖民地設(shè)置為自由狀態(tài)根據(jù)各個(gè)帝國(guó)的總能量和隨機(jī)數(shù)來(lái)確定哪個(gè)帝國(guó)獲得該殖民地。殖民地改革是選出所有國(guó)家中能量最弱的國(guó)家，將該國(guó)家用一個(gè)隨機(jī)產(chǎn)生的新國(guó)家替換掉[11]。

殖民競(jìng)爭(zhēng)算法的操作特點(diǎn)使得算法中的較劣解能夠和較優(yōu)解相互作用，相比于遺傳算法，殖民競(jìng)爭(zhēng)算法中的較劣解可以向更優(yōu)解更快速地移動(dòng)，亦或能產(chǎn)生比較優(yōu)解更優(yōu)的解。但是殖民競(jìng)爭(zhēng)算法的特點(diǎn)也可能使算法陷入局部最優(yōu)解不容易跳出，模擬退火算法的思想是通過(guò)對(duì)已有的解運(yùn)用某種鄰域結(jié)構(gòu)進(jìn)行擾動(dòng)來(lái)進(jìn)行局部搜索，試圖得到新的解，可以使得算法跳出局部最優(yōu)。所以本文對(duì)已有的殖民競(jìng)爭(zhēng)算法加入模擬退火環(huán)節(jié)，可以將兩種算法的特點(diǎn)結(jié)合起來(lái)，使得該算法更加適合于求解本文研究的集成優(yōu)化問(wèn)題。這樣雖然算法的時(shí)間復(fù)雜度會(huì)有所增加，但會(huì)使得新算法的全局和局部搜索的能力都比較強(qiáng)。

殖民國(guó)家內(nèi)競(jìng)爭(zhēng)、殖民競(jìng)爭(zhēng)和殖民地改革等過(guò)程參考文獻(xiàn)[7]，本文只對(duì)帝國(guó)初始化和帝國(guó)內(nèi)同化等過(guò)程進(jìn)行設(shè)計(jì)。

3.1初始化

對(duì)于多目標(biāo)問(wèn)題，初始化時(shí)各個(gè)解的質(zhì)量直接影響算法的收斂速度以及最終求解出的Pareto解集中的解的整體質(zhì)量，所以必須選擇比較好的編碼方式，力求使初始化時(shí)產(chǎn)生的解的質(zhì)量比較高。

柔性作業(yè)車間的殖民競(jìng)爭(zhēng)算法采用兩條編碼，一條是基于工序的編碼，用于說(shuō)明不同工件的不同工序的加工先后順序；另一條是基于機(jī)器的編碼，用來(lái)確定具體每個(gè)工件的每個(gè)工序在哪一臺(tái)機(jī)器上加工。

3.1.1工序序列的編碼

在基于工序的編碼中，每個(gè)數(shù)字代表一個(gè)工件，數(shù)字出現(xiàn)的次數(shù)等于該數(shù)字對(duì)應(yīng)工序的個(gè)數(shù)。且第k次出現(xiàn)的一個(gè)數(shù)字代表該數(shù)字對(duì)應(yīng)的工件的第k個(gè)工序，例如編碼[1 2 2 1 3 1 2 3]，表明工件1有三個(gè)工序，工件2有三個(gè)工序，工件3有兩個(gè)工序。本文算法在國(guó)家初始化時(shí)，對(duì)于基于工序的編碼采用隨機(jī)交換的方法，將所有工件的工序按照順序依次排列，如[1 1 1 2 2 2 3 3]，然后隨機(jī)交換工序位置，就產(chǎn)生了該國(guó)家內(nèi)基于工序編碼的序列，如[1 3 1 2 2 1 3 2]。

3.1.2機(jī)器序列的編碼

基于機(jī)器的工序中，將各個(gè)工件的工序按照順序排列下來(lái)，然后每個(gè)位置上對(duì)應(yīng)的機(jī)器就是對(duì)應(yīng)工序所在的機(jī)器。如編碼[1 3 1 2 2 1 3 2]表明工件1的三個(gè)工序分別在機(jī)器1、3、1上加工；工件2的三個(gè)工序在機(jī)器2、2、1加工；工件3的兩個(gè)工序在機(jī)器3、2上加工。

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

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

表1　為已排序的工序安排加工機(jī)器的過(guò)程

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

由兩列編碼就可以結(jié)合之前描述的動(dòng)態(tài)安排設(shè)備預(yù)防性維護(hù)的方法，在某臺(tái)機(jī)器上安排某工序后，若再安排下一道工序的加工就將使得設(shè)備可靠度低于閾值水平的時(shí)候，就在該工序之后進(jìn)行預(yù)防性維護(hù)。解碼后畫出相對(duì)應(yīng)的甘特圖，如圖3所示，進(jìn)行PM的時(shí)間均是根據(jù)機(jī)器可靠度的變化情況來(lái)決定的。

圖3　甘特圖示例

3.2帝國(guó)內(nèi)同化

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

3.2.1交叉操作

針對(duì)柔性作業(yè)車間調(diào)度的復(fù)雜性，殖民競(jìng)爭(zhēng)算法中一個(gè)國(guó)家內(nèi)兩條編碼的交叉分別進(jìn)行，其中第一部分基于工序的編碼采用元素分集合的交叉方法，第二部分基于機(jī)器的編碼采用一種新型多點(diǎn)交叉的方法。

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

圖4　基于工序編碼的交叉

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

圖5　基于機(jī)器編碼的交叉

3.2.2變異操作

(1)基于工序編碼的變異?；诠ば蚓幋a的序列串采用交換與插入變異，即從編碼串中隨機(jī)選取一個(gè)元素，然后隨機(jī)插入到編碼的其他位置，如圖6所示。

圖6　基于工序編碼的變異

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

圖7　基于機(jī)器編碼的變異

3.3Pareto求解及排序

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

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適應(yīng)度函數(shù)

本文采用Enayatifar等[9]提出的目標(biāo)組合法來(lái)量化每一個(gè)國(guó)家，即

(13)

其中，Pareto最優(yōu)解集的名次被設(shè)定為1，cn是個(gè)體n的適應(yīng)度，fk(n)是個(gè)體 n 的第 k 個(gè)目標(biāo)值，Nrank是指相同層次Pareto解集里面的個(gè)體數(shù)。rank(n)是0～1之間的隨機(jī)數(shù)。該公式可以區(qū)分不同Pareto層次的個(gè)體適應(yīng)度大小。然后可以根據(jù)下式計(jì)算各個(gè)國(guó)家標(biāo)準(zhǔn)化之后的能量：

Cn=max(cn)-cn

(14)

式中，Cn為第n個(gè)殖民國(guó)家標(biāo)準(zhǔn)化之后的成本值，即適應(yīng)度。

標(biāo)準(zhǔn)化之后的成本Cn代表了殖民國(guó)家的能量，即對(duì)于最小化問(wèn)題來(lái)說(shuō)，成本越小，能量越大。然后可以計(jì)算第n個(gè)殖民國(guó)家的殖民地?cái)?shù)量：

(15)

其中，Ncol是殖民地?cái)?shù)量，Nimp是殖民國(guó)家的數(shù)量。殖民國(guó)家成本越高，其殖民地越多。

3.5多目標(biāo)混合殖民競(jìng)爭(zhēng)算法

(16)

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

在本文中，模擬退火環(huán)節(jié)的步驟如下：

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

(2)對(duì)當(dāng)前所有國(guó)家依次進(jìn)行擾動(dòng)產(chǎn)生新的國(guó)家，如果新國(guó)家支配舊國(guó)家，則用新國(guó)家替換舊國(guó)家，否則按照概率決定是否接受新國(guó)家到合并的國(guó)家中；

(3)在溫度為T的時(shí)候，對(duì)每個(gè)國(guó)家進(jìn)行一定次數(shù)的擾動(dòng)；

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

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

多目標(biāo)混合殖民競(jìng)爭(zhēng)算法的步驟如下：

(1)選擇算法各個(gè)參數(shù)并運(yùn)用本文的初始化方法生成國(guó)家群體；

(2)用快速排序法得到所有國(guó)家的Pareto排序，計(jì)算各個(gè)國(guó)家的適應(yīng)度；

(3)判斷是否滿足算法終止的條件，即達(dá)到預(yù)設(shè)的代數(shù)或帝國(guó)數(shù)量是1；

(4)根據(jù)適應(yīng)度選出殖民國(guó)家，并計(jì)算隸屬各個(gè)殖民國(guó)家的殖民地?cái)?shù)量，按照數(shù)量將所有殖民地隨機(jī)分配給殖民國(guó)家；

(5)帝國(guó)內(nèi)同化；

(6)模擬退火算法對(duì)各個(gè)國(guó)家進(jìn)行擾動(dòng)，尋找更優(yōu)解；

(7)將所有國(guó)家重新進(jìn)行Pareto排序，計(jì)算適應(yīng)度，進(jìn)而重新選定殖民國(guó)家及隸屬各個(gè)殖民國(guó)家的殖民地；

(8)殖民競(jìng)爭(zhēng)；

(9)殖民地改革；

(10)刪除帝國(guó)；

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

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

多目標(biāo)混合殖民競(jìng)爭(zhēng)算法的流程如圖8所示。

圖8　多目標(biāo)殖民競(jìng)爭(zhēng)算法流程圖

3.6算法的時(shí)間復(fù)雜度分析

初始化的過(guò)程主要與初始國(guó)家數(shù)量P，所有工序的數(shù)量N和機(jī)器數(shù)量M有關(guān)，每道工序安排以后，就要相應(yīng)地更新工序-機(jī)器時(shí)間表，因此初始化過(guò)程的時(shí)間復(fù)雜度是O(PN2M)，在一次迭代操作中，帝國(guó)內(nèi)同化，殖民競(jìng)爭(zhēng)和殖民地改革的時(shí)間復(fù)雜度均為O(NeNc)，其中，Ne和Nc分別代表殖民國(guó)家的數(shù)量和每個(gè)帝國(guó)中殖民地的數(shù)量，而模擬退火環(huán)節(jié)的時(shí)間復(fù)雜度為O(NMlogCr(Tf/T0))，其中，T0代表初始溫度，Tf代表終止溫度，Cr代表降溫系數(shù)；根據(jù)快速排序法的計(jì)算方法，該環(huán)節(jié)的時(shí)間復(fù)雜度為O((NeNc)log2(NeNc))。本文提出的多目標(biāo)混合殖民競(jìng)爭(zhēng)算法總的時(shí)間復(fù)雜度為O(PN2M)+ GO(NM)+GO(PN2M2logCr(Tf/T0))，G是算法的迭代次數(shù)?？梢钥闯霰疚奶岢鏊惴ǖ臅r(shí)間復(fù)雜度與種群大小、算法迭代次數(shù)、問(wèn)題規(guī)模以及參數(shù)的大小有關(guān)。

4　算法測(cè)試與比較結(jié)果分析

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

4.1基準(zhǔn)實(shí)例測(cè)試

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

表2　幾種不同的算法求解基準(zhǔn)實(shí)例的Pareto對(duì)比

4.2具體實(shí)例的測(cè)試

4.2.1測(cè)試數(shù)據(jù)

在具體測(cè)試實(shí)例中，柔性作業(yè)車間調(diào)度的數(shù)據(jù)來(lái)自文獻(xiàn)[1]，是一個(gè)10×8的問(wèn)題，每臺(tái)設(shè)備的歷史維護(hù)數(shù)據(jù)來(lái)自現(xiàn)實(shí)制造車間數(shù)據(jù)[10]，并針對(duì)測(cè)試實(shí)例進(jìn)行調(diào)整，如表3所示。在表3中，ηi和mi分別是設(shè)備的形狀參數(shù)和尺度參數(shù)，此外，假設(shè)每臺(tái)設(shè)備的可靠度閾值為0.85。

表3　8臺(tái)機(jī)器的設(shè)備維護(hù)數(shù)據(jù)

假設(shè)設(shè)備i經(jīng)過(guò)第j次預(yù)防性維修之前的役齡為Zij，并且維修后又運(yùn)行了Δt的時(shí)間，則根據(jù)文獻(xiàn)[10]，經(jīng)過(guò)維護(hù)以后設(shè)備i在時(shí)刻t的故障強(qiáng)度λij也會(huì)以比例p(i)降低，計(jì)算公式為

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

(17)

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

(18)

進(jìn)而可以得到設(shè)備在一次預(yù)防性維護(hù)到下一次維護(hù)這段時(shí)間內(nèi)的平均故障后維修費(fèi)用：

(pi+Cs,i+Cm,i)

(19)

4.2.2具體實(shí)例測(cè)試結(jié)果

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

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

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

(20)

比率越大，證明算法效果越好。本文算法與兩個(gè)對(duì)比算法的比率計(jì)算結(jié)果如表5所示。

表5　多目標(biāo)算法比較結(jié)果

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

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

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

從表5可以看出，MOHICA算法的所有比率值都是1，表明通過(guò)本文算法得到的結(jié)果均沒(méi)有受普通MOICA算法和NSGA-Ⅱ算法得到的解支配，顯示MOHICA算法具有較強(qiáng)的搜索能力。從圖9、圖10可以看出，MOHICA算法得到的Pareto解的曲面在NSGA-Ⅱ算法和MOICA算法得到的Pareto解的曲面下邊，更靠近“原點(diǎn)”，說(shuō)明由MOHICA算法得到的解可以支配參考算法得到的解集。由表5和圖9、圖10可以看出，MOHICA算法能得到質(zhì)量更優(yōu)的Pareto解。

4.3Pareto解集的決策

MOHICA算法獲得一組Pareto解集后，車間調(diào)度員還面臨如何從這組Pareto解集選出滿意方案的問(wèn)題，這需要根據(jù)決策者主觀經(jīng)驗(yàn)(如依據(jù)決策指標(biāo)重要性的排序)或多指標(biāo)決策技術(shù)進(jìn)行排序或評(píng)估。

本文采用張洪等[16]提出的改進(jìn)加權(quán)優(yōu)劣解距離(TOPSIS)法，對(duì)基本的TOPSIS法增加了權(quán)重的因素，使決策過(guò)程更加科學(xué)。該方法的步驟為：首先將目標(biāo)值矩陣的各元素取倒數(shù)轉(zhuǎn)換為高優(yōu)指標(biāo)Xij；然后將每個(gè)目標(biāo)值進(jìn)行歸一化處理，處理后值為aij，aij計(jì)算公式為

(21)

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

(22)

圖11　得到滿意解的甘特圖

5　結(jié)語(yǔ)

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

[1]張超勇，董星，王曉娟，等. 基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J]. 機(jī)械工程學(xué)報(bào), 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]王靈芝, 徐宇工, 張家棟. 以可靠性為中心的多部件系統(tǒng)預(yù)防性維修優(yōu)化研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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]劉繁茂. 面向故障過(guò)程的多設(shè)備可靠性分析與維修決策[D]. 武漢：華中科技大學(xué)，2010.

[11]連坤雷. 殖民競(jìng)爭(zhēng)算法在離散制造系統(tǒng)優(yōu)化問(wèn)題中的應(yīng)用研究[D].武漢：華中科技大學(xué)，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]程博，楊育，劉愛(ài)軍, 等，基于遺傳模擬退火算法的大件公路運(yùn)輸路徑選擇優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，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]趙良輝,鄧飛其. 用于作業(yè)車間調(diào)度的模擬退火算法[J]. 制造業(yè)自動(dòng)化, 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]張洪，張燕. 基于加權(quán)TOPSIS法的旅游資源區(qū)際競(jìng)爭(zhēng)力比較研究[J]. 長(zhǎng)江流域資源與環(huán)境，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

國(guó)家自然科學(xué)基金資助重點(diǎn)項(xiàng)目(51035001 )；國(guó)家自然科學(xué)基金資助項(xiàng)目(51275190 )；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(2014TS038)

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

宋文家，男，1991年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室碩士研究生。主要研究方向?yàn)楝F(xiàn)代優(yōu)化算法、設(shè)備預(yù)防性維護(hù)與調(diào)度。張超勇，男，1972年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室副教授。尹勇，男，1976年生。武漢理工大學(xué)湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室教授。邵新宇，男，1968年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室教授。