彭建剛　劉明周　張　璽　張銘鑫　葛茂根

合肥工業(yè)大學(xué),合肥,230009

基于Pareto優(yōu)化的離散自由搜索算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題

彭建剛劉明周張璽張銘鑫葛茂根

合肥工業(yè)大學(xué),合肥,230009

針對多目標(biāo)柔性作業(yè)車間調(diào)度問題搜索空間的離散性和求解算法的收斂性，提出一種基于Pareto優(yōu)化的離散自由搜索算法來求解多目標(biāo)柔性作業(yè)車間調(diào)度問題。在建立基于Markov鏈數(shù)學(xué)模型的基礎(chǔ)上，證明了算法以概率1收斂；引入首達最優(yōu)解期望時間來分析算法收斂速度，并分析了算法時間復(fù)雜度。采用基于工序排序和機器分配的個體表達方式，在多目標(biāo)柔性作業(yè)車間離散域，利用自由搜索算法在鄰域小步幅精確搜索和在全局空間大步幅勘測進行尋優(yōu)；通過自由搜索算法自適應(yīng)賦予個體各異辨別能力和Pareto優(yōu)化概念來比較個體優(yōu)劣性，不僅保留優(yōu)化個體，而且使個體尋優(yōu)方向沿多目標(biāo)柔性作業(yè)車間調(diào)度問題Pareto前沿逼近。通過對搜索過程中產(chǎn)生的偽調(diào)度方案進行可行性判定，以確保調(diào)度方案可行。采用10×10FJSP和8×8FJSP問題的實例進行尋優(yōu)測試，驗證了所提算法的可行性和有效性。

多目標(biāo)柔性作業(yè)車間調(diào)度問題；自由搜索；Markov鏈；Pareto優(yōu)化

0　引言

柔性作業(yè)車間問題(flexible job-shop scheduling problem, FJSP)突破了經(jīng)典作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)的資源唯一性約束，是復(fù)雜的NP-hard問題[1]，F(xiàn)JSP比JSP更適應(yīng)現(xiàn)實制造車間的調(diào)度需求。實際生產(chǎn)調(diào)度往往需要滿足多個相互沖突的目標(biāo)，因此，大量生產(chǎn)調(diào)度屬于多目標(biāo)優(yōu)化問題，尋求多方利益的合理折中成為生產(chǎn)調(diào)度決策的重要問題[2]。多目標(biāo)柔性作業(yè)車間調(diào)度(multi-objective FJSP, MOFJSP)是面向多個目標(biāo)進行優(yōu)化與決策的FJSP，是實現(xiàn)先進制造技術(shù)的基礎(chǔ)和關(guān)鍵，對MOFJSP問題的深入研究具有重要的理論意義和應(yīng)用價值。

目前，求解MOFJSP的方法主要有進化算法和群智能優(yōu)化算法。鞠全勇等[2]研究批量生產(chǎn)中以生產(chǎn)周期、最大提前/最大拖后時間、生產(chǎn)成本以及設(shè)備利用率指標(biāo)為調(diào)度目標(biāo)的FJSP優(yōu)化調(diào)度問題，結(jié)合多種群粒子群搜索與遺傳算法優(yōu)點提出了具有傾向性粒子群搜索的多種群混合算法，提高了搜索效率和搜索質(zhì)量。張超勇等[3]采用多目標(biāo)進化算法解決具有工件釋放時間、工件目標(biāo)差異的FJSP調(diào)度問題，設(shè)計改進的NSGA-Ⅱ算法求解MOFJSP的Pareto解集，并運用層次分析法選出最優(yōu)妥協(xié)解。王云等[4]應(yīng)用改進的強度Pareto進化算法求解以制造工期、加工成本及交貨期為目標(biāo)函數(shù)的MOFJSP問題，并利用模糊集合理論的方法得到Pareto解的優(yōu)先選擇序列和一個最優(yōu)解。Kacem等[5]采用基于模糊進化的Pareto優(yōu)化法求解MOFJSP，將優(yōu)化解質(zhì)量的多目標(biāo)評價轉(zhuǎn)化成一個單一的適應(yīng)度函數(shù)，通過模糊控制規(guī)則動態(tài)地計算適應(yīng)度函數(shù)權(quán)重，使進化算法搜索方向朝Pareto前沿逼近，得到Pareto非支配解集，并通過適應(yīng)度函數(shù)各個目標(biāo)值的下邊界值來評價最優(yōu)解質(zhì)量。張靜等[6]采用基于工序排序和機器分配的粒子表達方式直接在離散域進行位置更新，并通過Pareto支配的概念來比較粒子的優(yōu)劣性, 提出了一種基于Pareto支配的混合粒子群優(yōu)化算法求解MOFJSP問題。Li等[7]結(jié)合多種局部搜索方法，引入Pareto概念對種群進行快速非支配排序，提出了基于Pareto的離散蜂群算法求解MOFJSP問題。

從現(xiàn)有文獻可以看出，MOFJSP問題的求解，既要選擇性能優(yōu)良的優(yōu)化算法，也要適合在離散空間與高效的局部搜索方法相結(jié)合，以提高算法效率、防止算法過早收斂；還要針對多目標(biāo)優(yōu)化特點，采用基于Pareto概念對種群進行非支配排序，尋求MOFJSP問題的Pareto非支配解集。本文選擇集成遺傳算法優(yōu)勝劣汰機制、蟻群算法信息素和個體觀察范圍理論、粒子群算法群體記憶功能等優(yōu)點的自由搜索(free search, FS)算法搜索MOFJSP問題優(yōu)化解。FS算法的研究相比遺傳算法、蟻群算法和粒子群算法等起步較晚，尚未形成系統(tǒng)的分析方法和較好的數(shù)學(xué)基礎(chǔ)，特別是利用有效的數(shù)學(xué)工具對算法的收斂性分析和收斂速度估計是亟待解決的課題。本文在分析FS算法及其結(jié)構(gòu)基礎(chǔ)上，將FS算法引入離散領(lǐng)域，結(jié)合Pareto優(yōu)化技術(shù)，提出基于Pareto優(yōu)化的離散自由搜索算法(discrete free search based on Pareto-optimality, P-DFS)求解MOFJSP問題；利用P-DFS算法對應(yīng)隨機過程的Markov鏈性質(zhì)證明了所提算法的收斂性、估計了算法的收斂速度、分析了算法的時間復(fù)雜度；通過算例仿真和結(jié)果對比，驗證了所提出算法的可行性和有效性。

1　MOFJSP數(shù)學(xué)模型

企業(yè)內(nèi)部不同部門，諸如采購部門、銷售部門、制造部門、生產(chǎn)部門等從自身利益考慮，對生產(chǎn)調(diào)度提出不同期望，因此，通過優(yōu)化部門之間相互作用且相互沖突的期望目標(biāo)，尋求各方利益的合理折中成為解決MOFJSP問題的關(guān)鍵。求解MOFJSP，即為對存在多個相互沖突目標(biāo)的柔性作業(yè)車間調(diào)度方案進行優(yōu)化與決策。為便于分析與研究, 調(diào)度過程作以下假設(shè)和約束：每個工件的各道工序只能按照事先給定的順序加工；每個工件在t=0時刻都可以開始加工，所有機器在時間t=0時刻都可以使用；在給定的時間內(nèi)，一臺機器只能加工一道工序；一道工序只能在其前道工序加工完成后，才能從其候選機器集合中選擇一臺空閑機器加工。

本文針對n個工件在m臺機器上加工的MOFJSP的最大完工時間、機器總負(fù)荷和單臺機器最大負(fù)荷等3種性能指標(biāo)進行優(yōu)化。建立MOFJSP的數(shù)學(xué)模型如下：

(1)

式中，ci為工件Ji的完工時間；Cmax為最大完工時間；WT為機器總負(fù)荷；max(Wh)為單臺機器最大負(fù)荷。

2　FS算法及其離散化

2.1FS算法基本原理

FS算法是Penev和Littlefair于2005年提出的一種源于高等群居動物的群聚進化算法[8]。FS算法通過個體在鄰域附近多維連續(xù)空間的小步幅精確搜索和在全局空間的大步幅勘測兩個搜索過程尋找目標(biāo)函數(shù)的最優(yōu)解。

FS算法結(jié)構(gòu)由初始化、搜索過程和終止判定3個步驟組成。Penev等[8]的研究表明，F(xiàn)S在收斂速度上優(yōu)于遺傳算法，在求解約束優(yōu)化問題上優(yōu)于粒子群算法，在求解平板問題上優(yōu)于差分進化算法。

2.2離散FS算法

目前，F(xiàn)S算法的研究主要集中在連續(xù)型問題上，即描述FS算法個體及其運動狀態(tài)規(guī)律的量是連續(xù)的，在離散領(lǐng)域，F(xiàn)S算法的應(yīng)用文獻甚少；而MOFJSP調(diào)度是典型的組合優(yōu)化問題，為了將FS算法用于求解MOFJSP，本文提出離散FS算法(discrete free search, DFS)。FS離散化的關(guān)鍵是根據(jù)MOFJSP問題領(lǐng)域定義個體尋優(yōu)的位置更新規(guī)則。

2.2.1DFS的編碼

DFS算法采用基于工序和機器分配相結(jié)合的編碼方式進行編碼，如圖1所示。工件的每道工序Oij在可用設(shè)備集Mij?{1,2,…,m}中的一臺設(shè)備上加工。第1條染色體編碼表示的工序順序為(O21,O11,O22,O31,O23,O12,O32),第2條染色體編碼表示的機器序列為(M1,M2,M3,M2,M4, M4,M3)。

圖1　基于工序和機器的編碼

2.2.2個體位置更新

在FS算法搜索空間中，個體位置Xi=(x1,x2,…,xr)是一個r維向量，結(jié)合MOFJSP特點和文獻[9]提出的位置更新策略，定義FS算法個體位置更新公式為

(1)個體從小步幅搜索獲得的尋優(yōu)信息如下：

(3)調(diào)度方案可行性判定[10]。由于個體位置移動產(chǎn)生的調(diào)度方案不一定是可行調(diào)度方案，故需進行調(diào)度方案可行性甄別，其操作為

πk=πk-1⊕(j,d)k,k=1,2,…,r

σ+l=φ(πk)

式中，⊕為第j個個體經(jīng)移動d位置后產(chǎn)生調(diào)度方案πk的操作算子；σ為調(diào)度方案；l為調(diào)度方案中個體移動前后的位置差；φ為工件序列修正程序。

即在新調(diào)度方案中，掃描工件排列，若某一位置分配多個工件，則結(jié)合FIFO(first-in-first-out)規(guī)則、工序約束和機器約束將多余工件向后移動到最近的空位上；若某位置為空，則同樣結(jié)合FIFO規(guī)則、工序約束和機器約束從其后面最近的含有多個工件的位置上提取一個工件插入；最終得到可行調(diào)度方案。

3　P-DFS算法設(shè)計

3.1符號說明

3.2P-DFS算法

MOFJSP面向FJSP的多個相互沖突目標(biāo)實施調(diào)度方案優(yōu)化與決策，是復(fù)雜組合優(yōu)化問題。本文將FS算法引入離散領(lǐng)域，在實現(xiàn)FS離散化的基礎(chǔ)上，結(jié)合求解多目標(biāo)優(yōu)化問題的Pareto優(yōu)化技術(shù)，提出P-DFS算法求解MOFJSP問題。在MOFJSP離散域內(nèi)，P-DFS算法個體在鄰域附近多維空間作小步幅精確搜索，在全局空間作大步幅勘測，目的是尋找目標(biāo)函數(shù)優(yōu)化解。個體將自己在鄰域空間發(fā)現(xiàn)的最優(yōu)解以信息素的形式保存起來，并利用信息素和靈敏度選擇下一步搜索的位置。信息素反映多目標(biāo)函數(shù)解的質(zhì)量；靈敏度猶如“過濾器”，不僅保留優(yōu)良個體，而且對不良個體重新初始化。不同的個體有不同的靈敏度，同一個體在不同的搜索步中有不同的靈敏度，個體選擇適合其靈敏度的信息素作為下一步搜索的起始點。每次隨機迭代搜索到的優(yōu)化解進入歸檔集，通過非支配排序得到非支配解，最終構(gòu)成Pareto非支配解集[11]。因此，P-DFS算法不僅有利于提高算法種群質(zhì)量，而且對尋優(yōu)搜索方向朝Pareto前沿逼近有重要的導(dǎo)向作用。基于雙目標(biāo)P-DFS算法搜索方向如圖2所示。

圖2　基于雙目標(biāo)P-DFS算法搜索方向

3.3P-DFS算法步驟

(1)設(shè)定搜索初始值。設(shè)定種群規(guī)模N，搜索代數(shù)G，搜索小步幅數(shù)T，鄰域半徑Rji。

(2)種群初始化。隨機產(chǎn)生初始種群{η(0)}，并計算個體適應(yīng)值。

(3)根據(jù)Pareto支配關(guān)系，生成初始種群歸檔集A(0)=M({η(0)},?)。

(4)釋放初始信息素pk→xjkp。

(5)計算靈敏度sj。

(7)計算搜索步個體適應(yīng)值。

(8)生成迭代種群{η(t)}t≥0。

(9)種群個體非支配排序，生成新的歸檔集:

A(t+1)=Mf(A(t)∪{η(t)}t≥0,?)

(10)釋放信息素pk→xjkp。

(11)終止判定。

4　P-DFS算法收斂性與收斂速度分析

4.1P-DFS算法的Markov鏈

P-DFS算法對應(yīng)的尋優(yōu)過程中，個體根據(jù)信息素和靈敏度進行隨機搜索，信息素和靈敏度在不同搜索步中不斷更新，第t次搜索信息素和靈敏度由第t-1次搜索的當(dāng)前最優(yōu)解和搜索得到的解集所決定。

P(η(t)∈Y′|η(0),η(1),…,η(t-1))=

P(η(t)∈Y′|η(t-1))Y′?Y

證畢。

4.2P-DFS算法的收斂性分析

定義2[11]P-DFS算法搜索到的Pareto非支配解構(gòu)成的集合為Pareto非支配解集，記為M(F,?)，即

M(F,?)={x*|┐?x∈F:xx*}

Pareto非支配解集對應(yīng)的狀態(tài)空間稱為最優(yōu)狀態(tài)空間，記為Y*。

定義3[13]設(shè)A、B是有限基礎(chǔ)集X的子集，則d(A,B)=|A∪B|-|A∩B|是X的冪集距離。

定義4[12]若Markov鏈轉(zhuǎn)移概率與初始時刻無關(guān)，則稱Markov鏈為齊次的。

從有互聯(lián)網(wǎng)以來的歷史我們發(fā)現(xiàn)，不能僅僅只依賴互聯(lián)網(wǎng)本身達成商業(yè)價值的創(chuàng)造。我們不能忽視其他行業(yè)與互聯(lián)網(wǎng)行業(yè)的相互補足。如此才能更多地發(fā)現(xiàn)企業(yè)的更優(yōu)發(fā)展模式。

定義5[14]隨機過程從一個狀態(tài)經(jīng)過有限步轉(zhuǎn)移到達另一狀態(tài)的條件概率大于0，則稱隨機過程的轉(zhuǎn)移矩陣是不可約的。

引理1[14]齊次有限狀態(tài)的離散時間參數(shù)Markov鏈的概率特性主要由一步轉(zhuǎn)移矩陣決定。

引理2[13]無論初始分布如何，一個具有有限狀態(tài)空間和不可約轉(zhuǎn)移矩陣的齊次Markov鏈經(jīng)常以概率1無窮多次地訪問每個狀態(tài)。

證明方法參見文獻[13]。

定理3P-DFS算法對應(yīng)的Markov鏈以概率1收斂到Pareto非支配解集。

證明P-DFS算法狀態(tài)空間YX的狀態(tài)有限性決定了P-DFS算法對應(yīng)的隨機過程是有限Markov鏈；P-DFS算法步驟(2)、步驟(6)解釋了轉(zhuǎn)移概率與初始狀態(tài)無關(guān)，決定了P-DFS算法對應(yīng)的Markov鏈?zhǔn)驱R次的；P-DFS算法步驟(5)～步驟(9)決定了其轉(zhuǎn)移矩陣是不可約的，由定義5和引理1可得：P-DFS算法對應(yīng)的Markov鏈?zhǔn)遣豢杉s的。根據(jù)定理2，當(dāng)t→∞時,d(f(η(t),F*)以概率1趨于0成立，由定義3可得：P-DFS算法對應(yīng)的Markov鏈以概率1收斂到最優(yōu)解集F*。由引理2可得：P-DFS算法對應(yīng)的Markov鏈的每一個最優(yōu)解將以概率1搜索到，并經(jīng)過P-DFS算法步驟(9)非支配排序獲得Pareto非支配解集，因此，P-DFS算法對應(yīng)的Markov鏈以概率1收斂到Pareto非支配解集。

證畢。

4.3P-DFS算法的收斂速度分析

A(t+1)=Mf(A(t)∪{η(t)},?)

可得

所以

成立，即

證畢。

P-DFS算法對應(yīng)的隨機過程滿足吸收態(tài)Markov性，引入首達最優(yōu)解期望時間(expected first hitting time, EFHT)[16]表征P-DFS算法的收斂速度。

可得

P(τ≤t)-P(τ≤t-1)

可得

?)-

證畢。

4.4P-DFS算法復(fù)雜度分析

假設(shè)優(yōu)化目標(biāo)函數(shù)個數(shù)為r，種群規(guī)模為N。從3.3節(jié)算法步驟可以看出，P-DFS算法尋優(yōu)主要由5部分組成：第1部分計算個體適應(yīng)值，其時間復(fù)雜度約為O(rN)；第2部分與歸檔集中非支配個體比較，其時間復(fù)雜度為O(rN2)；第3部分計算靈敏度，其時間復(fù)雜度約為O(rN)；第4部分選擇新的搜索起點，其時間復(fù)雜度約為O(rN)，第5部分為個體小步幅搜索和大步幅勘測，其時間復(fù)雜度為O(rN)。因此，P-DFS算法的總時間復(fù)雜度為

O(r,N)=[O(rN)+O(rN2)+O(rN)+

O(rN)+O(rN)]≈O(rN2)

P-DFS算法的時間復(fù)雜度與個體規(guī)模、優(yōu)化目標(biāo)函數(shù)個數(shù)有關(guān)，與基于Pareto非支配排序[17]的時間復(fù)雜度相同。

5　P-DFS算法實驗結(jié)果與比較

為驗證算法尋優(yōu)性能，采用文獻[18]提供的10×10和8×8FJSP問題實例進行尋優(yōu)測試。算法采用MATLABR2009a編程語言實現(xiàn)，微機運行環(huán)境為：CPUE6500，主頻2.93GHz，內(nèi)存2G；搜索初始值設(shè)定為：種群規(guī)模N=50,搜索代數(shù)G=100,搜索小步幅數(shù)T=50,鄰域半徑Rji=2。P-DFS算法的流程如圖3所示。

圖3　P-DFS算法流程圖

表1　10×10 FJSP問題的結(jié)果比較

表2　8×8 FJSP問題的結(jié)果比較

從表1和表2結(jié)果可以看出，對于10×10 FJSP和8×8 FJSP問題實例，分別運行P-DFS算法獲得的3個非支配解總體上不劣于文獻算法給出的最優(yōu)解(文獻結(jié)果統(tǒng)稱為最優(yōu)解)。單目標(biāo)函數(shù)值下界是衡量算法局部搜索能力的重要體現(xiàn)，針對本文實例，P-DFS算法搜索到了兩個實例所有單目標(biāo)函數(shù)值下界，并求解到相應(yīng)的Pareto非支配解集。因此，采用P-DFS算法求解10×10 FJSP問題和8×8 FJSP問題不僅可行而且效果良好。

6　結(jié)論

(1)針對MOFJSP問題特點，將FS算法引入離散領(lǐng)域，在定義算法個體位置更新和判定調(diào)度方案可行基礎(chǔ)上，結(jié)合Pareto優(yōu)化提出了P-DFS算法。在MOFJSP離散域內(nèi)，通過DFS算法小步幅精確搜索和全局空間的大步幅勘測，以及最優(yōu)解的非支配排序，使算法種群的尋優(yōu)方向朝Pareto前沿逼近，最終求解MOFJSP問題的最優(yōu)可行解。

(2)利用P-DFS算法的Markov鏈性質(zhì)，證明P-DFS算法以概率1收斂到Pareto非支配解集；引入首達最優(yōu)解期望時間和吸收態(tài)Markov鏈性質(zhì)分析P-DFS算法收斂速度；從P-DFS算法的主要尋優(yōu)過程分析其時間復(fù)雜度。

(3)基于P-DFS算法收斂性證明和收斂速度分析結(jié)論，將其應(yīng)用于MOFJSP問題求解；采用相同的實例進行實驗測試，并將P-DFS算法的尋優(yōu)結(jié)果與文獻結(jié)果進行比較，驗證了P-DFS算法的可行性和有效性。

[1]Blazewicz J,Finke G,Haopt G.New Trends in Machine Scheduling[J].European Journal of Operational Research,1988, 37: 303-317.

[2]鞠全勇,朱劍英.多目標(biāo)批量生產(chǎn)柔性作業(yè)車間優(yōu)化調(diào)度[J].機械工程學(xué)報,2007,43(8):148-154.

Ju Quanyong,Zhu Jianying.Multi-objective Flexible Job Shop Scheduling of Batch Production[J].Chinese Journal of Mechanical,2007,43(8):148-154.

[3]張超勇,董星,王曉娟,等.基于改進非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度[J].機械工程學(xué)報, 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.

[4]王云,譚建榮,馮毅雄,等.基于SPEA的多目標(biāo)柔性作業(yè)車間調(diào)度方法[J].中國機械工程,2010, 21(10):1167-1172.

Wang Yun,Tan Jianrong,Feng Yixiong, et al. Multi-objective Flexible Job-shop Scheduling Based on Strength Pareto Evolutionary Algorithm[J]. China Mechanical Engineering, 2010, 21(10):1167-1172.

[5]Kacem I, Hammadi S, Borne P.Pareto-optimality Approach for Flexible Job-shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic[J]. Mathematics and Computers in Simulation, 2002,60: 245- 276.

[6]張靜,王萬良,徐新黎,等.混合粒子群算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題[J].控制理論與應(yīng)用,2012,29 (6): 715-722.

Zhang Jing,Wang Wanliang,Xu Xinli,et al.Hybrid Particle-swarm Optimization for Multi-objective Flexible Job-shop Scheduling Problem[J].Control Theory & Applications,2012, 29(6):715-722.

[7]Li Junqing, Pan Quanke, Gao Kaizhou. Pareto-based Discrete Artificial Bee Colony Algorithm for Multi-objective Flexible Job Shop Scheduling Problems[J]. International Journal of Advanced Manufacturing Technology, 2011, 55: 1159-1169.

[8]Penev K, Littlefair G. Free Search-a Comparative Analysis[J]. Information Sciences,2005,172(1/2):173-193.

[9]潘全科,王文宏,朱劍英,等.基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J].計算機集成制造系統(tǒng), 2007,13(2): 323- 328.

Pan Quanke, Wang Wenhong, Zhu Jianying, et al.Hybrid Heuristics Based on Particle Swarm Optimization and Variable Neighborhood Search for Job Shop Scheduling[J].Computer Integrated Manufacturing Systems, 2007,13(2):323-328.

[10]Anghinolfi D,Paolucci M.A New Discrete Particle Swarm Optimization Approach for the Single-machine Total Weighted Tardiness Scheduling Problem with Sequence- dependent Setup Times[J]. European Journal of Operational Research, 2009, 193:73-85.

[11]公茂果,焦李成,楊咚咚,等.進化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報, 2009,20(2):271-289.

Gong Maoguo,Jiao Licheng,Yang Dongdong,et al.Research on Evolutionary Multi-objective Optimization Algorithms[J]. Journal of Software, 2009, 20(2): 271-289.

[12]張文修,梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安:西安交通大學(xué)出版社,2000.

[13]Rudolph G, Agapie A.Convergence Properties of Some Multi-objective Evolutionary Algorithms[C]//Proceedings of on IEEE Conference Evolutionary Computation.Piscataway, New Jersey, 2000:1010-1016.

[14]胡迪鶴.隨機環(huán)境中的馬爾可夫過程[M].北京:高等教育出版社,2011.

[15]黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計算機學(xué)報,2007,30(8): 1344-1353.

Huang Han,Hao Zhifeng,Wu Chunguo,et al. The Convergence Speed of Ant Colony Optimization[J]. Chinese Journal of Computers, 2007,30(8):1344-1353.

[16]Yu Yang,Zhou Zhihua.A New Approach to Estimating the Expected First Hitting Time of Evolutionary Algorithms[J]. Artificial Intelligence,2008,172:1809-1832.

[17]Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multi- objective Genetic Algorithms:NSGA-Ⅱ[J].IEEE Trans.on Evolutionary Computation,2002,6(2):182-197.

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

[19]張國輝,高亮,李培根,等.改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機械工程學(xué)報,2009,45(7):145-151.

Zhang Guohui,Gao Liang,Li Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering, 2009, 45(7): 145-151.

[20]李俊青,潘全科,王玉亭.多目標(biāo)柔性車間調(diào)度的Pareto混合禁忌搜索算法[J].計算機集成制造系統(tǒng), 2010,16(7): 1419- 1426.

Li Junqing,Pan Quanke,Wang Yuting. Hybrid Pareto-based Tabu Search Algorithm for Solving the Multi-objective Flexible Job Shop Scheduling Problem[J].Computer Integrated Manufacturing Systems, 2010,16(7):1419-1426.

[21]Xia Weijun, Wu Zhiming.An Effective Hybrid Optimization Approach for Multi-objective Flexible Job-shop Scheduling Problems[J].Computers & Industrial Engineering,2005,48: 409-425.

(編輯王艷麗)

Discrete Free Search Based on Pareto-optimality for Multi-objective Flexible Job-shop Scheduling Problem

Peng JiangangLiu MingzhouZhang XiZhang MingxinGe Maogen

Hefei University of Technology,Hefei,230009

A discrete free search algorithm based on Pareto-optimality was proposed for solving multi-objective flexible job-shop scheduling problem. The convergence with probability one of the proposed algorithm was demonstrated based on Markov chain and the convergence rate was analyzed based on expected first hitting time. The computational complexity of algorithm was also analyzed. Individuals of algorithm were represented based on job operation and machine assignment, and updated either with small precise steps for local search or with large steps for global exploration in discrete domain. The individuals were compared through adaptive sensibility and Pareto-optimality concept. The proposed algorithm was to retain the optimization individuals, and to guide individuals taking exploration walks towards Pareto-optimality front of multi-objective flexible job-shop scheduling problem. The feasibility and effectiveness of the proposed algorithm were verified by both 10×10FJSP and 8×8FJSP instance.

multi-objective flexible job-shop scheduling problem；free search；Markov chain；Pareto-optimality

2013-12-24

國家自然科學(xué)基金資助項目(71071046)

TH186DOI：10.3969/j.issn.1004-132X.2015.05.009

彭建剛，男，1970年生。合肥工業(yè)大學(xué)機械與汽車工程學(xué)院博士研究生、汽車工程技術(shù)研究院副研究員。主要研究方向為生產(chǎn)計劃與調(diào)度，先進制造技術(shù)和多目標(biāo)優(yōu)化算法。劉明周，男，1968年生。合肥工業(yè)大學(xué)機械與汽車工程學(xué)院教授、博士研究生導(dǎo)師。張璽，男，1985年生。合肥工業(yè)大學(xué)機械與汽車工程學(xué)院博士研究生。張銘鑫，男，1980年生。合肥工業(yè)大學(xué)機械與汽車工程學(xué)院講師。葛茂根，男，1979年生。合肥工業(yè)大學(xué)機械與汽車工程學(xué)院副教授。