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

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

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

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

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

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

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

多目標(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)實(shí)制造車間的調(diào)度需求。實(shí)際生產(chǎn)調(diào)度往往需要滿足多個(gè)相互沖突的目標(biāo)，因此，大量生產(chǎn)調(diào)度屬于多目標(biāo)優(yōu)化問題，尋求多方利益的合理折中成為生產(chǎn)調(diào)度決策的重要問題[2]。多目標(biāo)柔性作業(yè)車間調(diào)度(multi-objective FJSP, MOFJSP)是面向多個(gè)目標(biāo)進(jìn)行優(yōu)化與決策的FJSP，是實(shí)現(xiàn)先進(jìn)制造技術(shù)的基礎(chǔ)和關(guān)鍵，對(duì)MOFJSP問題的深入研究具有重要的理論意義和應(yīng)用價(jià)值。

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

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

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

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

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

(1)

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

2　FS算法及其離散化

2.1FS算法基本原理

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

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

2.2離散FS算法

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

2.2.1DFS的編碼

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

圖1　基于工序和機(jī)器的編碼

2.2.2個(gè)體位置更新

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

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

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

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

σ+l=φ(πk)

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

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

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

3.1符號(hào)說明

3.2P-DFS算法

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

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

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

(5)計(jì)算靈敏度sj。

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

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

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

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

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

(11)終止判定。

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

4.1P-DFS算法的Markov鏈

P-DFS算法對(duì)應(yīng)的尋優(yōu)過程中，個(gè)體根據(jù)信息素和靈敏度進(jìn)行隨機(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非支配解集對(duì)應(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)移概率與初始時(shí)刻無關(guān)，則稱Markov鏈為齊次的。

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

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

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

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

證明方法參見文獻(xiàn)[13]。

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

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

證畢。

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

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

可得

所以

成立，即

證畢。

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

可得

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

可得

?)-

證畢。

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

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

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

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

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

5　P-DFS算法實(shí)驗(yàn)結(jié)果與比較

為驗(yàn)證算法尋優(yōu)性能，采用文獻(xiàn)[18]提供的10×10和8×8FJSP問題實(shí)例進(jìn)行尋優(yōu)測(cè)試。算法采用MATLABR2009a編程語言實(shí)現(xiàn)，微機(jī)運(yù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é)果可以看出，對(duì)于10×10 FJSP和8×8 FJSP問題實(shí)例，分別運(yùn)行P-DFS算法獲得的3個(gè)非支配解總體上不劣于文獻(xiàn)算法給出的最優(yōu)解(文獻(xiàn)結(jié)果統(tǒng)稱為最優(yōu)解)。單目標(biāo)函數(shù)值下界是衡量算法局部搜索能力的重要體現(xiàn)，針對(duì)本文實(shí)例，P-DFS算法搜索到了兩個(gè)實(shí)例所有單目標(biāo)函數(shù)值下界，并求解到相應(yīng)的Pareto非支配解集。因此，采用P-DFS算法求解10×10 FJSP問題和8×8 FJSP問題不僅可行而且效果良好。

6　結(jié)論

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

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

(3)基于P-DFS算法收斂性證明和收斂速度分析結(jié)論，將其應(yīng)用于MOFJSP問題求解；采用相同的實(shí)例進(jìn)行實(shí)驗(yàn)測(cè)試，并將P-DFS算法的尋優(yōu)結(jié)果與文獻(xiàn)結(jié)果進(jìn)行比較，驗(yàn)證了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].機(jī)械工程學(xué)報(bào),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]張超勇,董星,王曉娟,等.基于改進(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.

[4]王云,譚建榮,馮毅雄,等.基于SPEA的多目標(biāo)柔性作業(yè)車間調(diào)度方法[J].中國機(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].計(jì)算機(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]公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào), 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]胡迪鶴.隨機(jī)環(huán)境中的馬爾可夫過程[M].北京:高等教育出版社,2011.

[15]黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計(jì)算機(jī)學(xué)報(bào),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]張國輝,高亮,李培根,等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報(bào),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].計(jì)算機(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é)基金資助項(xiàng)目(71071046)

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

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