基于Pareto優化的離散自由搜索算法求解多目標柔性作業車間調度問題

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

合肥工業大學,合肥,230009

基于Pareto優化的離散自由搜索算法求解多目標柔性作業車間調度問題

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

合肥工業大學,合肥,230009

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

多目標柔性作業車間調度問題；自由搜索；Markov鏈；Pareto優化

0　引言

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

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

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

1　MOFJSP數學模型

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

本文針對n個工件在m臺機器上加工的MOFJSP的最大完工時間、機器總負荷和單臺機器最大負荷等3種性能指標進行優化。建立MOFJSP的數學模型如下：

(1)

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

2　FS算法及其離散化

2.1FS算法基本原理

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

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

2.2離散FS算法

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

2.2.1DFS的編碼

DFS算法采用基于工序和機器分配相結合的編碼方式進行編碼，如圖1所示。工件的每道工序Oij在可用設備集Mij?{1,2,…,m}中的一臺設備上加工。第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維向量，結合MOFJSP特點和文獻[9]提出的位置更新策略，定義FS算法個體位置更新公式為

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

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

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

σ+l=φ(πk)

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

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

3　P-DFS算法設計

3.1符號說明

3.2P-DFS算法

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

圖2　基于雙目標P-DFS算法搜索方向

3.3P-DFS算法步驟

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

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

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

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

(5)計算靈敏度sj。

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

(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算法對應的尋優過程中，個體根據信息素和靈敏度進行隨機搜索，信息素和靈敏度在不同搜索步中不斷更新，第t次搜索信息素和靈敏度由第t-1次搜索的當前最優解和搜索得到的解集所決定。

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

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

證畢。

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

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

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

Pareto非支配解集對應的狀態空間稱為最優狀態空間，記為Y*。

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

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

從有互聯網以來的歷史我們發現，不能僅僅只依賴互聯網本身達成商業價值的創造。我們不能忽視其他行業與互聯網行業的相互補足。如此才能更多地發現企業的更優發展模式。

定義5[14]隨機過程從一個狀態經過有限步轉移到達另一狀態的條件概率大于0，則稱隨機過程的轉移矩陣是不可約的。

引理1[14]齊次有限狀態的離散時間參數Markov鏈的概率特性主要由一步轉移矩陣決定。

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

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

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

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

證畢。

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

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

可得

所以

成立，即

證畢。

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

可得

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

可得

?)-

證畢。

4.4P-DFS算法復雜度分析

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

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

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

P-DFS算法的時間復雜度與個體規模、優化目標函數個數有關，與基于Pareto非支配排序[17]的時間復雜度相同。

5　P-DFS算法實驗結果與比較

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

圖3　P-DFS算法流程圖

表1　10×10 FJSP問題的結果比較

表2　8×8 FJSP問題的結果比較

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

6　結論

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

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

(3)基于P-DFS算法收斂性證明和收斂速度分析結論，將其應用于MOFJSP問題求解；采用相同的實例進行實驗測試，并將P-DFS算法的尋優結果與文獻結果進行比較，驗證了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]鞠全勇,朱劍英.多目標批量生產柔性作業車間優化調度[J].機械工程學報,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].機械工程學報, 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的多目標柔性作業車間調度方法[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]張靜,王萬良,徐新黎,等.混合粒子群算法求解多目標柔性作業車間調度問題[J].控制理論與應用,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]潘全科,王文宏,朱劍英,等.基于粒子群優化和變鄰域搜索的混合調度算法[J].計算機集成制造系統, 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].軟件學報, 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]張文修,梁怡.遺傳算法的數學基礎[M].西安:西安交通大學出版社,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]胡迪鶴.隨機環境中的馬爾可夫過程[M].北京:高等教育出版社,2011.

[15]黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計算機學報,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].機械工程學報,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]李俊青,潘全科,王玉亭.多目標柔性車間調度的Pareto混合禁忌搜索算法[J].計算機集成制造系統, 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

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

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

彭建剛，男，1970年生。合肥工業大學機械與汽車工程學院博士研究生、汽車工程技術研究院副研究員。主要研究方向為生產計劃與調度，先進制造技術和多目標優化算法。劉明周，男，1968年生。合肥工業大學機械與汽車工程學院教授、博士研究生導師。張璽，男，1985年生。合肥工業大學機械與汽車工程學院博士研究生。張銘鑫，男，1980年生。合肥工業大學機械與汽車工程學院講師。葛茂根，男，1979年生。合肥工業大學機械與汽車工程學院副教授。