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

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

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

?

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

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

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

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

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

0引言

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

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

1.1問題描述

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

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

圖1　向前偏移的預防性維護方法描述圖

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

(2)將所有設備的維護安排在各個機器維護時間窗的末尾。

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

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

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

1.2數(shù)學模型

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

(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工序可用的機器集合，Mjk?{1, 2,…,m};tijk為工件j的第k工序在機器i上的加工時間，i?Mjk；bejk為工件j 的第k工序開始的時間；enjk為工件j的k工序完工時間；tpi為 機器i預防性維護所需時間；MCi為機器i的維護結束時刻；L 為一個足夠大的正數(shù)；wbi和wei分別為機器i的預防性維護時段的開始和結束時刻。

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

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

2.1初始化

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

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

(1)工序序列的編碼。在基于工序的編碼中，每個數(shù)字代表一個工件，數(shù)字出現(xiàn)的次數(shù)等于該數(shù)字對應工序的個數(shù)，且第k次出現(xiàn)的一個數(shù)字代表該數(shù)字對應的工件的第k個工序，例如，編碼[1 2 2 1 3 1 2 3]表示工件1有三個工序，工件2有三個工序，工件3擁有兩個工序。HTLBO算法對基于工序的編碼采用隨機交換的方法，將所有工件的工序按照順序依次排列，如[1 1 1 2 2 2 3 3]，然后隨機交換工序位置，產(chǎn)生該解內(nèi)基于工序編碼的序列，如[1 3 1 2 2 1 3 2]。

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

為每個工序分配機器時要考慮該工序在不同可加工機器上的加工時間，最好選擇最小值對應的機器來安排，同時需要兼顧考慮每臺機器已經(jīng)分配的負載情況，不能使某臺機器的負載過大。為了提高初始解的質量，借鑒Kacem等[8]提出的利用時間表的分配方法AL(approachbyLocalization)和Pezzella等[9]改進的分配規(guī)則來進行編碼，使得編碼的魯棒性比較強，進而得到質量比較高的初始解。Pezzella等[9]改進的遺傳算法編碼是在Kacem等[8]分配方法的基礎上增加隨機交換工件位置或者機器位置，以及在時間表中優(yōu)先安排擁有全局最小加工時間的工序及機器，但是他們都沒有考慮不同工件以及同一工件的不同工序的加工順序。

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

由兩列編碼就可以結合上述動態(tài)安排設備預防性維護的方法來進行預防性維護安排，在某臺機器上安排某工序后，若再安排其下一道工序將使得預防性維護與該工序沖突，則在該工序之后進行預防性維護。解碼后畫出對應的甘特圖，見圖2。

圖2　甘特圖實例

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

2.2“教與學”的過程

2.2.1“教學”階段

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

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

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

圖3　基于工序編碼的交叉

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

圖4　基于機器編碼的交叉

2.2.2“自學”階段

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

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

圖5　工序序列的變異

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

圖6　基于機器編碼的變異

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

2.3模擬退火算法

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

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

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

圖7　基于工序編碼的鄰域結構

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

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

2.4算法執(zhí)行流程

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

圖8　HTLBO算法流程圖

3實例驗證與分析

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

3.1基準實例的測試

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

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

(9)

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

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

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

表2　10個MK實例測試結果對比

3.2考慮維修時間窗的實例測試

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

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

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

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

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

表6　三種具體實例的測試結果對比

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

4結論

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

參考文獻：

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

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

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

[3]夏唐斌, 奚立峰, 周曉軍，等. 串并聯(lián)衰退系統(tǒng)的多目標預防性維護優(yōu)化建模[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

基金項目：國家自然科學基金國際(地區(qū))合作與交流項目(51561125002)；國家自然科學基金資助項目(51275190, 51575211)；中央高?；究蒲袠I(yè)務費專項資金資助項目(2014TS038)

中圖分類號：TP18

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

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