基于維修時(shí)間窗的柔性作業(yè)車間調(diào)度優(yōu)化研究

朱傳軍　宋文家　張超勇　曹　靜　朱孟周

1.湖北工業(yè)大學(xué)，武漢，4300682.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，4300743. 江蘇省電力公司電力科學(xué)研究院,南京，211103

?

基于維修時(shí)間窗的柔性作業(yè)車間調(diào)度優(yōu)化研究

朱傳軍1宋文家2張超勇2曹靜1朱孟周3

1.湖北工業(yè)大學(xué)，武漢，4300682.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，4300743. 江蘇省電力公司電力科學(xué)研究院,南京，211103

摘要：針對(duì)柔性作業(yè)車間調(diào)度和預(yù)防性維護(hù)的單目標(biāo)集成優(yōu)化問題，以最大完工時(shí)間為優(yōu)化指標(biāo)，建立了基于維修時(shí)間窗的集成優(yōu)化模型，設(shè)計(jì)了混合“教與學(xué)”優(yōu)化(HTLBO)算法求解該模型。提出一種“基于工序加工時(shí)間最短”的機(jī)器序列初始化策略，對(duì)部分初始種群進(jìn)行初始優(yōu)化，以提高部分初始解的質(zhì)量，使得算法能夠以較短的時(shí)間收斂。對(duì)文獻(xiàn)中柔性作業(yè)車間調(diào)度的基準(zhǔn)問題進(jìn)行求解并比較其計(jì)算結(jié)果，初步證明該混合算法的可行性；針對(duì)集成維修時(shí)間窗的柔性作業(yè)車間調(diào)度優(yōu)化模型，借鑒文獻(xiàn)中的數(shù)據(jù)生成實(shí)例進(jìn)行求解，并與其他算法進(jìn)行比較，證明該混合算法的有效性。

關(guān)鍵詞：維修時(shí)間窗;柔性作業(yè)車間調(diào)度問題;“教與學(xué)”優(yōu)化;模擬退火

0引言

為消除實(shí)際生產(chǎn)中的設(shè)備失效和生產(chǎn)計(jì)劃外中斷等現(xiàn)象，需要定期或不定期地對(duì)設(shè)備進(jìn)行預(yù)防性維護(hù)(preventive maintenance，PM)。按照設(shè)備維護(hù)時(shí)間可將預(yù)防性維護(hù)分為周期性維護(hù)和非周期性維護(hù)兩類。一般來說，設(shè)備維護(hù)不可能在正常作業(yè)時(shí)進(jìn)行，必須是作業(yè)結(jié)束后或開始前進(jìn)行，所以周期性維護(hù)相對(duì)來說很難滿足實(shí)際生產(chǎn)需要。目前關(guān)于周期性維護(hù)的研究文獻(xiàn)相對(duì)較少。Naderi等[1]分析了柔性流水線車間的周期性預(yù)防性維護(hù)問題，采用基于遺傳算法和人工免疫系統(tǒng)的兩種啟發(fā)式方法優(yōu)化最大完工時(shí)間(makespan)。設(shè)備的非周期性預(yù)防性維護(hù)計(jì)劃受到國內(nèi)外學(xué)者的廣泛關(guān)注。李林等[2]建立了一種面向租賃設(shè)備的順序預(yù)防維護(hù)策略，通過最小化期望總成本率獲得了租賃設(shè)備的優(yōu)化租賃期限及維護(hù)計(jì)劃。夏唐斌等[3]建立了一種設(shè)備層的單設(shè)備動(dòng)態(tài)預(yù)防性維護(hù)的多目標(biāo)決策模型。Ni等[4]研究了生產(chǎn)過程中不影響產(chǎn)量的預(yù)防性維護(hù)機(jī)會(huì)，開發(fā)了一個(gè)識(shí)別維護(hù)機(jī)會(huì)的預(yù)測(cè)模型。非周期性預(yù)防性維護(hù)會(huì)影響實(shí)際生產(chǎn)計(jì)劃，增加作業(yè)車間調(diào)度的難度，因此考慮設(shè)備非周期預(yù)防性維護(hù)的車間調(diào)度問題的研究也逐漸引起了人們的關(guān)注。Fitouhi等[5]研究了針對(duì)單機(jī)非周期性預(yù)防維護(hù)的生產(chǎn)計(jì)劃；Allaoui等[6]研究了雙機(jī)柔性車間中帶預(yù)防性維護(hù)的最小完工時(shí)間優(yōu)化問題，假設(shè)條件為其中一臺(tái)設(shè)備在調(diào)度開始的T個(gè)周期內(nèi)必須完成一次預(yù)防性維護(hù)。針對(duì)柔性作業(yè)車間調(diào)度和預(yù)防性維護(hù)的集成優(yōu)化問題，本文以最大完工時(shí)間為優(yōu)化指標(biāo)，在周期性維護(hù)的基礎(chǔ)上建立了基于維護(hù)時(shí)間窗的集成優(yōu)化模型，并設(shè)計(jì)了一種混合“教與學(xué)”優(yōu)化(hybrid teaching-learning-based optimization，HTLBO)算法，對(duì)該問題進(jìn)行求解。

1考慮維修時(shí)間窗的柔性作業(yè)車間調(diào)度優(yōu)化模型

1.1問題描述

柔性作業(yè)車間調(diào)度問題(FJSP)可描述如下：n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件分為K道工序，每道工序可以在若干臺(tái)機(jī)器上加工，并且必須按一些可行的工藝次序進(jìn)行加工；每臺(tái)機(jī)器可以加工工件的若干工序，并且在不同的機(jī)器上加工的工序集可以不同。調(diào)度的目標(biāo)是將工件合理地安排到各機(jī)器，使系統(tǒng)的某些性能指標(biāo)達(dá)到最優(yōu)。

為了便于求解，本文假設(shè)以下條件：①每臺(tái)機(jī)床一次只能加工一個(gè)工件；②機(jī)器的準(zhǔn)備時(shí)間和工序間的轉(zhuǎn)移時(shí)間可忽略不計(jì)；③所有工件均不包含可被打斷的工序；④不同工件前后次序沒有硬性要求；⑤分屬不同工件的工序，其前后次序沒有硬性要求；⑥對(duì)于隸屬同一工件的所有工序，必須依照既定的順序加工。

圖1　向前偏移的預(yù)防性維護(hù)方法描述圖

(1)先按照傳統(tǒng)柔性作業(yè)車間調(diào)度進(jìn)行決策，不包含預(yù)防性維護(hù)，只包含工序的最初調(diào)度。

(2)將所有設(shè)備的維護(hù)安排在各個(gè)機(jī)器維護(hù)時(shí)間窗的末尾。

(3)如果某一臺(tái)機(jī)器預(yù)防性維護(hù)的時(shí)間段和其他工序的加工時(shí)間不沖突，則將該機(jī)器的維護(hù)和加工環(huán)節(jié)合并調(diào)度，否則執(zhí)行步驟(4)。

(4)如果某臺(tái)機(jī)器的預(yù)防性維護(hù)時(shí)間段和某個(gè)工序加工的時(shí)間段發(fā)生沖突，則將維護(hù)環(huán)節(jié)盡量提前到前一道工序末尾或者機(jī)器開始加工的時(shí)刻，然后安排沖突的加工環(huán)節(jié)和之后的加工環(huán)節(jié)。

當(dāng)然，預(yù)防性維護(hù)以后工件加工順序如果改變，有可能會(huì)減小最大完工時(shí)間，但這些改變會(huì)在算法中的“教學(xué)”、“自學(xué)”及模擬退火環(huán)節(jié)中實(shí)現(xiàn)，因?yàn)檫@幾個(gè)環(huán)節(jié)都對(duì)工序的排序情況進(jìn)行變更。

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

對(duì)設(shè)備的預(yù)防性維護(hù)和生產(chǎn)調(diào)度進(jìn)行有機(jī)集成，把設(shè)備的維護(hù)考慮在作業(yè)計(jì)劃之中，以最小化最大完工時(shí)間為目標(biāo)，機(jī)器的預(yù)防性維護(hù)盡量安排在既定的時(shí)間窗內(nèi)，制定設(shè)備維護(hù)和各個(gè)工序的生產(chǎn)計(jì)劃。建立的數(shù)學(xué)模型如下：

(1)

s.t.

(2)

enjk≤bej(k+1)?j,k

(3)

(4)

bejk+tijk≤behl+L(1-yijkhl)?i,j,k,h,l,j≠h

(5)

[(MCi-tpi-enjk)Xijk≥0]∨[(enjk-

MCi-tijk)Xijk≥0]?i,j,k

(6)

wbi+tpi≤MCi≤wei?i

(7)

yijkhl≤Xijk,yijkhl≤Xihl?i,j,k,h,l

(8)

式中，Mjk為工件j的第k工序可用的機(jī)器集合，Mjk?{1, 2,…,m};tijk為工件j的第k工序在機(jī)器i上的加工時(shí)間，i?Mjk；bejk為工件j 的第k工序開始的時(shí)間；enjk為工件j的k工序完工時(shí)間；tpi為 機(jī)器i預(yù)防性維護(hù)所需時(shí)間；MCi為機(jī)器i的維護(hù)結(jié)束時(shí)刻；L 為一個(gè)足夠大的正數(shù)；wbi和wei分別為機(jī)器i的預(yù)防性維護(hù)時(shí)段的開始和結(jié)束時(shí)刻。

式(1)為模型的目標(biāo)函數(shù)，即最大完工時(shí)間最小；式(2)和式(3)表示每個(gè)工件的加工工序的順序約束；式(4)表示機(jī)器約束，即同一時(shí)刻，一臺(tái)機(jī)器能且只能加工一種工件的一個(gè)工序；式(5)表示在特定的時(shí)刻，一臺(tái)機(jī)器只能加工一種工件的一種工序；式(6)表示同一臺(tái)機(jī)器上設(shè)備預(yù)防性維護(hù)和工序的加工不能存在沖突；式(7)導(dǎo)入維修時(shí)間窗約束；式(8)說明只有分到同一機(jī)器上的各工序才需要進(jìn)行排序。

2HTLBO算法求解集成優(yōu)化問題

2.1初始化

對(duì)于該優(yōu)化問題，初始化時(shí)解的整體質(zhì)量直接影響算法的收斂速度以及最終最優(yōu)解的質(zhì)量，所以必須選擇比較好的編碼方式，力求使初始化時(shí)產(chǎn)生的解的整體質(zhì)量比較高。

柔性作業(yè)車間調(diào)度需要將每臺(tái)機(jī)器上的不同工件的工序分配到合理的機(jī)器上，因此柔性作業(yè)車間調(diào)度中HTLBO算法采用兩條編碼，一條是基于工序的編碼，用于說明不同工件的不同工序的加工先后順序；另一條是基于機(jī)器的編碼，用來確定具體每個(gè)工件的每個(gè)工序在哪一臺(tái)機(jī)器上加工。

(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è)工序。HTLBO算法對(duì)基于工序的編碼采用隨機(jī)交換的方法，將所有工件的工序按照順序依次排列，如[1 1 1 2 2 2 3 3]，然后隨機(jī)交換工序位置，產(chǎn)生該解內(nèi)基于工序編碼的序列，如[1 3 1 2 2 1 3 2]。

(2)機(jī)器序列的編碼。基于機(jī)器的工序中，將各個(gè)工件的工序按照順序排列下來，然后每個(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ī)器來安排，同時(shí)需要兼顧考慮每臺(tái)機(jī)器已經(jīng)分配的負(fù)載情況，不能使某臺(tái)機(jī)器的負(fù)載過大。為了提高初始解的質(zhì)量，借鑒Kacem等[8]提出的利用時(shí)間表的分配方法AL(approachbyLocalization)和Pezzella等[9]改進(jìn)的分配規(guī)則來進(jìn)行編碼，使得編碼的魯棒性比較強(qiáng)，進(jìn)而得到質(zhì)量比較高的初始解。Pezzella等[9]改進(jìn)的遺傳算法編碼是在Kacem等[8]分配方法的基礎(chǔ)上增加隨機(jī)交換工件位置或者機(jī)器位置，以及在時(shí)間表中優(yōu)先安排擁有全局最小加工時(shí)間的工序及機(jī)器，但是他們都沒有考慮不同工件以及同一工件的不同工序的加工順序。

本文在Kacem等[8]分配方法的基礎(chǔ)上對(duì)機(jī)器序列的初始化進(jìn)一步改進(jìn)，提出“基于工序加工時(shí)間最短”的機(jī)器序列初始化策略，即將加工時(shí)間的表格按照已經(jīng)確定的工序排序從上到下對(duì)每行重新排序。具體過程如下：首先分配排在第一位的工序，選擇加工該工序時(shí)間最短的某臺(tái)機(jī)器分配給該工序；然后將表中該機(jī)器對(duì)應(yīng)的加工時(shí)間位于該行之后的所有值均增加該工序的加工時(shí)間，表示該機(jī)器負(fù)載已經(jīng)增加；最后對(duì)剩下的每個(gè)工序都進(jìn)行同樣的操作，最終確定對(duì)應(yīng)該工序編碼的機(jī)器分配方案。如表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ī)器的過程

由兩列編碼就可以結(jié)合上述動(dòng)態(tài)安排設(shè)備預(yù)防性維護(hù)的方法來進(jìn)行預(yù)防性維護(hù)安排，在某臺(tái)機(jī)器上安排某工序后，若再安排其下一道工序?qū)⑹沟妙A(yù)防性維護(hù)與該工序沖突，則在該工序之后進(jìn)行預(yù)防性維護(hù)。解碼后畫出對(duì)應(yīng)的甘特圖，見圖2。

圖2　甘特圖實(shí)例

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

2.2“教與學(xué)”的過程

2.2.1“教學(xué)”階段

“教學(xué)”的過程和“學(xué)生”互相學(xué)習(xí)的過程借鑒遺傳算法(GA)中交叉算子的思想，使得新解能從“教師”或者其他“學(xué)生”解的序列中“學(xué)習(xí)”到新知識(shí)。

由于要保證交叉變異以后得到的子代都是問題的可行解，因此一個(gè)解內(nèi)的兩條編碼所需要的交叉變異方式是不相同的，表示工序次序的序列采用元素分集合的交叉方法，表示加工機(jī)器的序列采用多點(diǎn)交叉方法。交叉操作力求可以將較優(yōu)秀序列的元素盡可能地保留在新得到的序列中。

(1)工序序列串的交叉。工序序列的交叉過程是：首先把需要調(diào)度的工件集合Q任意分為非空子集Q1和Q2，新解內(nèi)的編碼先繼承“教師”集合Q1內(nèi)的工件對(duì)應(yīng)的元素，然后將“學(xué)生”集合Q2內(nèi)的工件對(duì)應(yīng)的元素分別填充到新解內(nèi)的編碼空缺的元素中，如圖3所示，其中Q1={2, 3}。

圖3　基于工序編碼的交叉

(2)基于機(jī)器編碼的交叉采用多點(diǎn)交叉的方式，具體操作是：先隨機(jī)產(chǎn)生一條和編碼等長(zhǎng)的0-1序列，將“教師”中與0-1序列中的0位置相同的所有元素復(fù)制到新解中，將“學(xué)生”中與0-1序列中的1位置相同的所有元素復(fù)制到新解中，如圖4所示。

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

2.2.2“自學(xué)”階段

算法中除了“教與學(xué)”的過程外，還增加了學(xué)生“自學(xué)”的過程，即通過對(duì)“學(xué)生”解中的兩條序列進(jìn)行一定的操作，看是否能得到質(zhì)量更優(yōu)的解。自學(xué)的過程借鑒遺傳算法變異操作的思想，對(duì)已有的序列進(jìn)行一定的擾動(dòng)來計(jì)算確定得到的解是否為更優(yōu)解。

(1)工序順序序列的變異。表示工序順序的序列串采用Insert變異，即從編碼串中任意選取某元素，然后隨機(jī)調(diào)換到序列的其他位置，如圖5所示。

圖5　工序序列的變異

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

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

在教與學(xué)和自學(xué)階段，算法均會(huì)產(chǎn)生新解。如果新解S′比原來的解S目標(biāo)函數(shù)值更優(yōu)，則一定用S′將S替換掉；如果S′不比S的結(jié)果更優(yōu)，則引入一個(gè)選擇因子c= rand(0,1)，如果c≥0.5則將S′保留在算法解集中，否則丟棄S′。這樣可以使得到的更優(yōu)解保留下來，選擇性保留非更優(yōu)解既可以保證算法中解的多樣性，還可以避免算法中解的數(shù)量過于龐大，影響算法的空間復(fù)雜度。

2.3模擬退火算法

基本TLBO算法求解一定時(shí)間后很可能會(huì)陷入局部最優(yōu)，可以將鄰域結(jié)構(gòu)的局部搜索加入該算法中，以提高算法整體的搜索效率[10-12]。本文將模擬退火(simulatedannealing,SA)算法加入到TLBO算法中，在算法中“教與學(xué)”和“自學(xué)”之后，采用SA算法對(duì)所得的解進(jìn)行局部搜索，搜索對(duì)象是原有解集和產(chǎn)生的所有解，這樣會(huì)導(dǎo)致算法整體時(shí)間復(fù)雜度有所增加，但可以很大程度地提高解的質(zhì)量。

SA算法是一種根據(jù)熱力學(xué)統(tǒng)計(jì)定律得出的鄰域搜索技術(shù)，在過去求解組合問題時(shí)產(chǎn)生了良好的效果[13]。標(biāo)準(zhǔn)的SA算法首先隨機(jī)產(chǎn)生初始解，設(shè)定初始溫度T0、終止溫度Tf、溫度衰減率α，然后運(yùn)用特定的鄰域結(jié)構(gòu)對(duì)已得到的解進(jìn)行鄰域搜索，若得到的新解更優(yōu)，就用新解將舊解替換掉。隨著算法的進(jìn)行，溫度也以一定比例降低，直到達(dá)到設(shè)定的終止溫度Tf。

在SA算法環(huán)節(jié)中，對(duì)于兩條編碼需要用不同的鄰域結(jié)構(gòu)進(jìn)行局部搜索。采用兩種基于工序編碼的鄰域結(jié)構(gòu)，分別是反向(Inverse)和交換(Swap)。反向的鄰域結(jié)構(gòu)就是在編碼中隨機(jī)選擇一段編碼，將所有元素逆轉(zhuǎn)反向排序；交換的鄰域結(jié)構(gòu)就是在編碼中隨機(jī)選擇兩個(gè)元素交換位置。兩種鄰域結(jié)構(gòu)如圖7所示。

圖7　基于工序編碼的鄰域結(jié)構(gòu)

對(duì)于已知解中基于機(jī)器編碼的鄰域結(jié)構(gòu)，采用本文算法提出的機(jī)器編碼的變異方式進(jìn)行變異。混合算法中模擬退火的步驟如下：①設(shè)定初始溫度T0、終止溫度Tf、溫度衰減率α的值； ②選擇已有解S，運(yùn)用SA算法的鄰域結(jié)構(gòu)對(duì)S進(jìn)行局部搜索得到S′，令ΔS=f(S′)-f(S)；③如果ΔS<0則將S用S′替換掉，否則令P=exp(-ΔS/T)決定是否用S′替換S；④使溫度以衰減率α緩慢降低，即Tk+1=Tkα，其中α∈(0, 1)；⑤重復(fù)步驟①～④，直至滿足停止條件。

由于要保證算法空間和時(shí)間復(fù)雜度不至于過高，所以模擬退火階段得到的新解S″只有比之前的解S′更優(yōu)才會(huì)得以保留，若S″比之前的解S′更優(yōu)則將S′替換掉。

2.4算法執(zhí)行流程

HTLBO算法流程如圖8所示，P的值由混合算法中模擬退火的步驟③獲取，該算法具體步驟如下：①按照2.1節(jié)所述進(jìn)行算法的初始化，產(chǎn)生初始解集Pt，此時(shí)t←0，令解集規(guī)模為N；②在初始解集中選擇n個(gè)目標(biāo)值較好的解作為“教師”；③按照2.2節(jié)所述對(duì)解集Pt進(jìn)行“教與學(xué)”的過程和“自學(xué)”過程，得到新的解集Qt；④運(yùn)用SA算法對(duì)Qt中的解進(jìn)行搜索，得到新的解集Qt′；⑤如果t

圖8　HTLBO算法流程圖

3實(shí)例驗(yàn)證與分析

為驗(yàn)證HTLBO算法的有效性，首先對(duì)文獻(xiàn)[14]中的10個(gè)MK算例進(jìn)行測(cè)試，均以最小化最大完工時(shí)間為目標(biāo)，并與其他文獻(xiàn)中的算法的測(cè)試結(jié)果進(jìn)行對(duì)比。同時(shí)參考其他文獻(xiàn)的數(shù)據(jù)生成三個(gè)實(shí)際模型的算例進(jìn)行求解，與基本TLBO算法和遺傳算法求解的結(jié)果進(jìn)行對(duì)比。

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

HTLBO算法采用C++語言編程，計(jì)算機(jī)運(yùn)行環(huán)境為2.5GHzIntelCorei5多核CPU和2GBRAM，算法的有關(guān)參數(shù)設(shè)置如下：種群規(guī)模Popsize=200， 遺傳代數(shù)Generation=100；模擬退火環(huán)節(jié)中，本文取初始溫度T=1000，溫度衰減率α=0.8，終止溫度Tf=1，在溫度T時(shí)，每個(gè)已有解進(jìn)行5次的擾動(dòng)。

MK實(shí)例的HTLBO算法測(cè)試結(jié)果與其他文獻(xiàn)算法結(jié)果對(duì)比如表2所示，其中，m和n分別表示每個(gè)問題中機(jī)器和工件的數(shù)量，GA-Chen表示Chen等[15]的測(cè)試結(jié)果，GA-Jia表示Jia等[16]的測(cè)試結(jié)果，GA-Pezzella表示Pezzella等[9]的測(cè)試結(jié)果，TSPCB表示Li等[17]的測(cè)試結(jié)果，C表示測(cè)試目標(biāo)makespan的值；Div為最優(yōu)解相對(duì)偏差的值，其計(jì)算公式為

(9)

式中，Ci為對(duì)比算法求得的makespan的值；C為HTLBO算法求得的makespan的值。

由表2可以看出，HTLBO算法求解出了質(zhì)量比較高的解(達(dá)到或者超過其他算法求解出的makespan最優(yōu)值)，在表中已用黑體突出顯示。

從表2中數(shù)據(jù)可以看出，對(duì)于前6個(gè)基準(zhǔn)問題以及MK08問題，HTLBO算法均求解出了已有文獻(xiàn)中得出的最優(yōu)解；對(duì)于MK10問題，HTLBO算法得到的解比其他4種算法的解更優(yōu)；只有MK07問題和MK09問題沒有得到其他算法的最優(yōu)解，但相差不大。

表2　10個(gè)MK實(shí)例測(cè)試結(jié)果對(duì)比

3.2考慮維修時(shí)間窗的實(shí)例測(cè)試

對(duì)于具體實(shí)例的測(cè)試，傳統(tǒng)的FJSP測(cè)試數(shù)據(jù)來自文獻(xiàn)[14]中的MK04、MK07和MK09的三組數(shù)據(jù)，三個(gè)實(shí)例分別是15×8、20×5以及20×10的FJSP問題。對(duì)于三個(gè)問題中各臺(tái)機(jī)器的預(yù)防性維護(hù)時(shí)間窗和預(yù)防性維護(hù)需要的時(shí)間tpi，假定分別如表3～表5所示，PMmn表示第m臺(tái)機(jī)器的n次維護(hù)。先用HTLBO算法獲得三個(gè)結(jié)果，再分別用GA算法的解進(jìn)行對(duì)比。

三種算法對(duì)三個(gè)算例分別進(jìn)行求解得到的結(jié)果對(duì)比如表6所示。由表6可以看出，針對(duì)本文建立的單目標(biāo)集成優(yōu)化模型，HTLBO算法對(duì)三個(gè)算例求得的結(jié)果均優(yōu)于對(duì)比算法GA算法的結(jié)果，因此，本文提出的HTLBO算法求解基于固定維護(hù)時(shí)間窗的柔性作業(yè)車間調(diào)度和預(yù)防性維護(hù)的集成優(yōu)化問題是有效的。其中，對(duì)于第一個(gè)15×8的算例，HTLBO算法求解出的最優(yōu)解的甘特圖見圖9，圖中某些工序之后緊跟的“PM”小條即是預(yù)防性維護(hù)的環(huán)節(jié)。Jm表示第m個(gè)工件，工序的先后順序由甘特圖中的時(shí)間先后來決定。

表3　15×8問題的預(yù)防性維護(hù)時(shí)間數(shù)據(jù)

表4　20×5問題的預(yù)防性維護(hù)時(shí)間數(shù)據(jù)

表5　20×10問題的預(yù)防性維護(hù)時(shí)間數(shù)據(jù)

表6　三種具體實(shí)例的測(cè)試結(jié)果對(duì)比

圖9　15×8算例最優(yōu)解的甘特圖

4結(jié)論

針對(duì)柔性作業(yè)車間和預(yù)防性維護(hù)的集成優(yōu)化問題，建立了基于機(jī)器維護(hù)時(shí)間窗的集成優(yōu)化模型，在基本“教與學(xué)”優(yōu)化(TLBO)算法中加入模擬退火的過程，提出了新穎的混合“教與學(xué)”優(yōu)化(HTLBO)算法。該算法結(jié)合了TLBO算法全局搜索的優(yōu)勢(shì)和模擬退火算法的局部搜索能力。將該算法用于求解10個(gè)MK基準(zhǔn)測(cè)試實(shí)例，并與其他文獻(xiàn)得到的結(jié)果進(jìn)行對(duì)比，初步證明了該算法的有效性。選擇其中三個(gè)實(shí)例，針對(duì)其特點(diǎn)分別生成三個(gè)符合本文模型的集成預(yù)防性維護(hù)的具體實(shí)例，運(yùn)用HTLBO算法得到最優(yōu)解，并與遺傳算法得到的最優(yōu)調(diào)度進(jìn)行比較，驗(yàn)證了HTLBO算法在解決基于機(jī)器維護(hù)時(shí)間窗的柔性作業(yè)車間和預(yù)防性維護(hù)的集成優(yōu)化問題的有效性。

參考文獻(xiàn)：

[1]NaderiB,ZandiehM,AminnayeriM.IncorporatingPeriodicPreventiveMaintenanceintoFlexibleFlowshopSchedulingProblems[J].AppliedSoftComputing, 2011,11: 2094-2101

[2]李林，金琳，周曉軍. 基于沖擊建模的租賃設(shè)備預(yù)防維護(hù)策略[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2013,19(1):114-118.

LiLin,JinLin,ZhouXiaojun.PreventiveMaintenanceStrategyBasedonShockModelingforLeasingEquipment[J].ComputerIntegratedManufacturingSystems, 2013,19(1):114-118.

[3]夏唐斌, 奚立峰, 周曉軍，等. 串并聯(lián)衰退系統(tǒng)的多目標(biāo)預(yù)防性維護(hù)優(yōu)化建模[J]. 計(jì)算機(jī)集成制造系統(tǒng),2010, 16(4):783-788.

XiaTangbin,XiLifeng,ZhouXiaojun,etal.OptimizationofMulti-objectivePreventiveMaintenanceforSeries-parallelDeterioratingSystems[J].ComputerIntegratedManufacturingSystems, 2010, 16(4):783-788.

[4]NiJun,GuXi,JinXiaoning.PreventiveMaintenanceOpportunitiesforLargeProductionSystems[J].CIRPAnnals-ManufacturingTechnology, 2015,64: 447-450.

[5]FitouhiM-C,NourelfathM.IntegratingNoncyclicalPreventiveMaintenanceSchedulingandProductionPlanningforaSingleMachine[J].Int.J.ProductionEconomics， 2012，136：344-351.

[6]AllaouiH,LamouriS,ArtibaA,etal.SimultaneouslySchedulingnJobsandthePreventiveMaintenanceontheTwo-machineFlowShoptoMinimizetheMakespan[J].Int.J.ProductionEconomics， 2008，112 ： 161-167.

[7]LiJQ，PanQK.Chemical-reactionOptimizationforFlexibleJob-shopSchedulingProblemswithMaintenanceActivity[J].AppliedSoftComputing, 2012，12(9): 2896-2912.

[8]KacemI,HammadiS,BorneP.ApproachByLocalizationandMultiobjectiveEvolutionaryOptimizationforFlexibleJob-shopSchedulingProblems[J].ApplicationsandReviews,IEEETransactionsonSystems,Man,andCybernetics,PartC, 2002,32(1): 1-13.

[9]PezzellaF,MorgantiG,CiaschettiG.AGeneticAlgorithmfortheFlexibleJob-shopSchedulingProblem[J].Computers&OperationsResearch, 2008，35(10): 3202-3212.

[10]Mladenovic′N,HansenP.VariableNeighborhoodSearch[J].Computers&OperationsResearch, 1997， 24(11):1097-1100.

[11]BattitiR,TecchiolliG.TheReactiveTabuSearch[J].ORSAJournalonComputing, 1994， 6(2):126-140.

[12]EgleseR.SimulatedAnnealing:aToolforOperationalResearch[J].EuropeanJournalofOperationalResearch, 1990, 46(3): 271-281.

[13]LowC.SimulatedAnnealingHeuristicforFlowShopSchedulingProblemswithUnrelatedParallelMachines[J].Computers&OperationsResearch, 2005, 32(8): 2013-2025.

[14]BrandimarteP.RoutingandSchedulinginaFlexibleJobShopbyTabuSearch[J].AnnalsofOperationsResearch, 1993， 41(3): 157-183.

[15]ChenH,IhlowJ,LehmannC.AgeneticAlgorithmforFlexibleJob-shopscheduling[C]//1999IEEEInternationalConferenceonRoboticsandAutomation.Detroit：IEEE，1999:1120-1125.

[16]JiaH,NeeA,FuhJ,etal.AModifiedGeneticAlgorithmforDistributedSchedulingProblems[J].JournalofIntelligentManufacturing, 2003，14(3/4): 351-62.

[17]LiJQ,PanQK,SuganthanP,etal.AHybridTabuSearchAlgorithmwithanEfficientNeighborhoodStructurefortheFlexibleJobShopSchedulingProblem[J].TheInternationalJournalofAdvancedManufacturingTechnology， 2011，52(5/8): 683-697.

(編輯蘇衛(wèi)國)

Research on Optimization of FJSP Based on Maintenance Time Window

Zhu Chuanjun1Song Wenjia2Zhang Chaoyong2Cao Jing1Zhu Mengzhou3

1.Hubei University of Technology, Wuhan, 430068 2.State Key Laboratory of Digital Manufacturing Equipment & TechnologyHuazhong University of Science and Technology, Wuhan, 430074 3.Electric Power Research Institute, Jiangsu Electric Power Company, Nanjing, 211103

Abstract:An optimization model was proposed to minimize the makespan in FJSP based on maintenance time window， which integrated the preventive maintenance. A hybrid algorithm was presented to deal with the model based on TLBO. A new machine sequence initializing strategy was investigated to optimize partial initial population based on “shortest processing time for operation”, which might improve the quality of the initial solutions, so the computing process might convergence in a relatively short time. By calculating and comparing the results of FJSP benchmark problems with other literatures, the feasibility of the hybrid algorithm was proved on the whole. In view of flexible job-shop schedule optimization model which integrated maintenance time window, the data from the literatures was modified for the model and calculated by the hybrid algorithm. By comparing the results with other algorithms, the effectiveness of the hybrid TLBO algorithm was validated.

Key words:maintenance time window; flexible job shop scheduling problem(FJSP); teaching-learning-based optimization(TLBO); simulated annealing

收稿日期：2015-07-13

基金項(xiàng)目：國家自然科學(xué)基金國際(地區(qū))合作與交流項(xiàng)目(51561125002)；國家自然科學(xué)基金資助項(xiàng)目(51275190, 51575211)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2014TS038)

中圖分類號(hào)：TP18

DOI：10.3969/j.issn.1004-132X.2016.10.010

作者簡(jiǎn)介：朱傳軍，男，1971年生。湖北工業(yè)大學(xué)機(jī)械工程學(xué)院副教授、博士。主要研究方向?yàn)橹悄軆?yōu)化算法、決策分析。宋文家，男，1991年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室碩士研究生。張超勇，男，1972年生。華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院副教授、博士。曹靜，女，1970年生。湖北工業(yè)大學(xué)機(jī)械工程學(xué)院講師。朱孟周，男，1982年生。江蘇省電力公司電力科學(xué)研究院工程師、博士。