求解FJSP的改進元胞粒子群算法

吳正佳 付先旺 望 蕓 劉秀鳳

(三峽大學 機械與動力學院， 湖北 宜昌 443002)

求解FJSP的改進元胞粒子群算法

吳正佳 付先旺 望 蕓 劉秀鳳

(三峽大學 機械與動力學院， 湖北 宜昌 443002)

以企業(yè)的實際需求為依據(jù)，建立了柔性作業(yè)車間調度問題的數(shù)學模型；針對其特點，提出一種混合元胞粒子群優(yōu)化算法，通過雙層編碼，將工件的加工順序與加工機器位置信息數(shù)值化表示；引入遺傳算法中的交叉、變異操作，改進了粒子位置更新方法；融入變鄰域算法,改善算法局部搜索能力．通過仿真實驗，結果表明：算法在求解能力方面有所提升，能夠有效地求解柔性作業(yè)車間調度問題．

柔性作業(yè)車間調度問題； 雙層編碼； 混合元胞粒子群算法

0 引 言

車間調度在制造企業(yè)的組織生產(chǎn)中有著舉足輕重的地位，對提高企業(yè)的生產(chǎn)效率、降低成本有著十分重要的意義[1]．隨著市場競爭壓力加劇，企業(yè)生產(chǎn)模式逐步向單件小批量轉變，柔性制造在企業(yè)得到廣泛應用，研究柔性作業(yè)車間調度問題(Flexible Job Shop Scheduling Problem, FJSP)就顯得尤為重要．學者們在探索求解FJSP問題的方法中取得了一定的成果：李俊等[2]在模擬退火算法中引入新求解問題的編碼方法，趙詩奎[3]提出一種融合兩級鄰域搜索和遺傳算法的混合算法，劉曉冰等[4]提出了改進的雙鏈量子遺傳算法，吳秀麗等[5]提出了一種改進的細菌覓食優(yōu)化算法，趙敏等[6]提出了一種改進人工魚群算法．可以看出，利用多種算法進行優(yōu)勢互補構成混合算法是研究的主流．事實上，絕大多數(shù)智能算法(元啟發(fā)式算法)都采用單一的領域結構，很難有效地平衡搜索深度和搜索廣度，僅適合求解單一適應度地形問題，很難有效解決復雜柔性作業(yè)車間調度問題．

粒子群算法(PSO)[7]是近年發(fā)展起來的一種群智能優(yōu)化算法，該算法能在合理的時間內求得問題的滿意解，得到了學者的廣泛關注和研究；元胞粒子群優(yōu)化算法(CPSO)[8]是在PSO基礎上，引元胞自動機的原理而形成的新型算法，使解的多樣性得以維持，避免了算法早熟現(xiàn)象，但是該算法存在著收斂速度慢、易陷入局部最優(yōu)解的缺點；變鄰域搜索(VNS)[9]通過系統(tǒng)地改變搜索區(qū)域，能夠很好地跳出局部最優(yōu)．因此，本文針對柔性作業(yè)調度問題的特點，通過將上述算法有機地結合，充分發(fā)揮各算法的優(yōu)勢，以提高混合算法的性能，拓寬算法的應用領域．

1 FJSP問題描述與模型建立

1.1 FJSP問題描述

柔性作業(yè)車間調度問題一般描述為：將n個工件J={J1，J2，…，Jn}安排至m臺機器M={M1，M2，…，Mm}上進行加工．每個工件由一道或多道工序組成，工件的各工序是已知的，每道工序可以在多個備選機器上加工，但加工時間隨機器選擇的不同而不同．FJSP的調度目標是通過確定各工序的機器選擇以及各個機器上各工序的加工順序和開始加工時間，在滿足如下約束的條件下，使某些調度性能指標達到最優(yōu)[10]．因此，F(xiàn)JSP問題可分解為兩個調度子問題：一是確定各工件工序的機器選擇，二是確定各個機器上工序的排序問題．

除了考慮工件的數(shù)量以及機器的加工時間外，一般滿足如下的約束或假設：1)同工件的優(yōu)先級相同，t=0時刻所有工件都可以被加工；2)所有機器在t=0時刻都可用；3)各工件必須滿足既定加工順序；4)同一時刻，一臺機器上只能加工一個工件；5)同一時刻，一個工件只能被一個機器加工；6)忽略擾動因素，即工件一旦開始加工就不能中斷．

1.2 數(shù)學模型建立

實際中，企業(yè)常以生產(chǎn)周期衡量生產(chǎn)效率的高低，因此，本文建立了以工件的最大完工時間最小為目標的柔性作業(yè)車間調度問題的數(shù)學模型，具體可描述如下：

(1)

(2)

(3)

(4)

其中，min(Cmax)為優(yōu)化目標；n為工件總數(shù)；m為機器總數(shù)；M為所有機器的集合；i表示第i個工件；j表示工件i的第j個工序；h為工序j選擇的機器編號；ni為第i個工件的工序總數(shù)；sijk為工件i在機器k上的開始加工時間；tklh為工件k的工序l在機器h上的加工時間；mij為工序j可選機器集合．

2 求解FJSP的元胞粒子群算法設計

2.1 編碼與解碼

1)基于粒子位置的雙層編碼

FJSP包含工件排序與機器選擇兩個子問題，編碼時也需分開處理，因此本文采用如圖1所示的雙層編碼的結構．

圖1 雙層編碼示意圖

采用雙層編碼，使得機器編碼與工序的排序相互獨立，便于粒子位置信息交叉的有效性和合法性，而且以矩陣的形式表示，減小計算的內存消耗．

2)解碼

由于機器碼的產(chǎn)生依賴于工序碼，故只需對工序碼進行解碼，一般解碼方式只能得到半主動調度，得不到主動調度．采用插入式貪婪解碼方法，以確保得到的調度為主動調度．其操作步驟為：按粒子的位置編碼信息，從左到右依次讀取各工序，將其依次插入到對應機器上最早可以加工的時間上，直到所有的工序都被安排．

2.2 粒子位置信息更新方法

針對FJSP問題特點，改變中粒子的信息共享與繼承機制，本文提出離散的元胞粒子群位置更新方式．當前粒子依據(jù)上一代、歷史最優(yōu)以及全局最優(yōu)的位置信息，融入遺傳算法的交叉思想實現(xiàn)粒子位置信息的更新，重新定義一種新的位置更新方法，如公式(5)所示：

(5)

圖2 基于工序編碼的IPOX交叉操作

Fibt=min(fitness(Pibt)，fitness(Pi1bt)，

(6)

2.3 混合元胞粒子群算法設計

2.3.1 FJSP鄰域結構設計

柔性作業(yè)車間調度問題中最基本的鄰域是通過在工序排序部分隨機選擇兩個位置，采取逆序、插入、交換等操作構造，這些鄰域結構在一定程度上豐富了解的鄰域，但它們包含了大量的無效移動，導致算法后期搜索緩慢，運算效率低．因此本文在這些鄰域的基礎上加入更高效的基于關鍵塊的鄰域結構，有下幾種：

1)N5鄰域結構：N5鄰域結構由Nowicki和Smutnicki[11]提出，其操作對象為關鍵路徑中的關鍵塊．對于首關鍵塊，交換塊尾兩個工序；尾關鍵塊，交換塊首兩個工序；中間關鍵塊，塊首兩個工序與塊尾兩個工序都需要交換，如圖3所示．

圖3 N5鄰域結構

2)塊內工序與塊首或塊尾交換的鄰域結構：N5鄰域僅對塊首前兩個和塊尾后兩個進行交換操作，較為單一，將關鍵塊內的工序分別與塊首或塊尾工序交換，極大地豐富關鍵塊的鄰域，如圖4所示．

圖4 與塊首或塊尾交換的鄰域結構

3)N6鄰域結構：N5鄰域很小，搜索范圍受到一定限制，為發(fā)掘更多有效移動，Balas和Vazacopoulos[12]提出了N6鄰域結構．在不產(chǎn)生回路的前提下，將塊內工序插入到塊首前面或插入到塊尾后面，如圖5所示．

圖5 N6鄰域結構

2.3.2 元胞粒子群和變鄰域混合策略

在元胞粒子群算法中，粒子通過追隨自身歷史最優(yōu)位置學習鄰居最優(yōu)位置，不斷地更新自身位置，使種群優(yōu)質信息均勻傳播，維持了種群的多樣性，算法的全局搜索能力得以保障，這樣的操作直接導致了收斂精度低，算法很難收斂．變鄰域搜索(VNS)算法的局部搜索能力較強，但是VNS在變換鄰域結構時具有一定的盲目性，很容易錯過較優(yōu)解所在的區(qū)域，求解質量很大程度上依賴于初始解和鄰域結構．

基于以上分析，綜合分析CPSO和VNS算法的特點，提出一種CPSO與VNS混合算法，稱之混合的元胞粒子群算法(Hybrid CPSO, HCPSO)．

在CPSO系統(tǒng)中，多個粒子通過與共同鄰居最優(yōu)值Lbt同時進行信息交流，這種信息流動方式單一．在多個Lbt的作用下，粒子朝著最優(yōu)解的方向進化，顯然，Lbt對CPSO算法的性能有很大的影響．為提高CPSO算法的搜索性能，粒子群每次更新后對Lbt執(zhí)行變鄰域搜索，以增強算法對全局最優(yōu)解的探索能力，因而混合元胞粒子群優(yōu)化算法求解FJSP步驟如圖6所示．

圖6 HCPSO流程圖

3 仿真實驗與分析

3.1 仿真設計

本文選用文獻[13]中的Brandimarte算例，驗證設計算法的有效性．文中元胞粒子群算法的主要參數(shù)設置如下：種群大小N=50，粒子鄰居結構為Moore型，粒子適應度值連續(xù)不變的最大步數(shù)MaxStep=20，最大迭代次數(shù)MaxCount=50，交叉概率c1=c2=0.45，變異概率Pm=0.01．變鄰域搜索算法的主要參數(shù)設置如下：外循環(huán)步長outstep=20,內循環(huán)步長instep=100．

在Matlab 2012b版本軟件中編程，針對不同算例，將HCPSO,CPSO和PSO 3種算法獨立運行50次，得到的仿真結果見表1．

表1 標準算例計算結果

3.2 結果分析

如表1所示，m×n表示問題的工件總數(shù)和機器總數(shù)，LB,UB分別表示到目前為止已知的最優(yōu)值下界和最優(yōu)值上界，Cmax表示優(yōu)化目標的最優(yōu)值，Avg表示算法運行20次中所得平均最優(yōu)值．分析求解的結果可知：對于FJSP問題，無論是最優(yōu)解還是平均解，HCPSO的求解能力優(yōu)于其他兩種算法，這是因為在元胞粒子群優(yōu)化算法中混入了VNS算法，由于VNS算法通過系統(tǒng)地改變鄰域結構，提高了算法的局部搜索能力，避免算法過早陷入局部最優(yōu)值．而CPSO因種群粒子鄰域結構太單一，局部搜素能力較差，算法易陷入局部最優(yōu)值，但整體上要比未采用任何改良機制的傳統(tǒng)PSO要優(yōu)．

進一步探討HCPSO,CPSO和PSO 3種算法的收斂性，3種算法在求解Mk03問題最優(yōu)值的迭代過程如圖7所示．

圖7 3種算法迭代過程圖

可以看出，在前20代，3種算法收斂速度都較快，而傳統(tǒng)的PSO比CPSO,HCPSO的收斂速度更快．當運行至20代至36代之間時，PSO開始趨于最終的收斂，CPSO和HPSO算法收斂速度變慢，但仍具有較好的局部搜索能力．由于融合了變鄰域搜索，改變了解的結構，使得HCPSO比CPSO具有更強局部開挖能力，到37代以后，PSO因沒有挖掘到更好的解而局部最優(yōu)，HPSO算法和CPSO算法的收斂速度變慢，仍然保留一定的局部探索能力，最終由于HCPSO中融入變鄰域搜索算法使得問題收斂到了全局最優(yōu)值．

4 結 語

本文以生產(chǎn)實際為背景，建立柔性作業(yè)車間調度問題的優(yōu)化模型，針對柔性作業(yè)車間調度問題包含了工件排序與機器選擇兩個子問題的特點，設計了高效的雙層編碼方式，提出適合求解該問題的元胞粒子群算法．通過改進粒子位置信息更新方法、粒子鄰域結構選擇策略以及各粒子更新策略，設計了元胞粒子群算法求解FJSP流程；探索了適合該問題的高效鄰域結構，提出了求解FJSP問題的混合元胞粒子群算法．最后，采用標準的算例對改進的混合元胞粒子群算法做性能測試，比較了3種算法在多種類型問題上的求解性能．結果表明：所改進的混合元胞粒子群算法得到的解的質量較高，算法收斂性較好，可以廣泛應用于其他優(yōu)化問題的求解中．

[1] 趙學燕．鋼結構企業(yè)生產(chǎn)調度優(yōu)化研究[D]．天津:天津師范大學，2015．

[2] 李 俊，劉志雄，張 煜，等．柔性作業(yè)車間調度優(yōu)化的改進模擬退火算法[J]．武漢科技大學學報，2015，38(2):111-116．

[3] 趙詩奎．求解柔性作業(yè)車間調度問題的兩級鄰域搜索混合算法[J]．機械工程學報，2015，51(14):175-184．

[4] 劉曉冰，焦璇，寧 濤，等．基于雙鏈量子遺傳算法的柔性作業(yè)車間調度[J]．計算機集成制造系統(tǒng)，2015，21(2):495-502．

[5] 吳秀麗，張志強，杜彥華，等．改進細菌覓食算法求解柔性作業(yè)車間調度問題[J]．計算機集成制造系統(tǒng)，2015，21(5):1262-1270．

[6] 趙 敏，殷 歡，孫棣華，等．基于改進人工魚群算法的柔性作業(yè)車間調度[J]．中國機械工程，2016(8):1059-1065．

[7] 李艷鵬．基于粒子群和禁忌搜索算法求解作業(yè)車間調度優(yōu)化問題[D]．大連：大連交通大學，2013．

[8] Shi Y， Liu H, Gao L, et al． Cellular Particle Swarm Optimization[J]．Information Sciences, 2011,181(20):4460-4493．

[9] MladenovicN, Hansen P． Variable Neighborhood Search[J]．Computers & Operations Research, 1997,24(11):1097-1100．

[10] 吳正佳, 何海洋, 黃燦超, 等．帶機器故障的柔性作業(yè)車間動態(tài)調度[J]．機械設計與研究, 2015，31(3):94-98．

[11] Nowicki E, Smutnicki C． A Fast Taboo Search Algorithm for the Job Shop Problem[J]．Management Science, 1996,42(6):797-813．

[12] Balas E, Vazacopoulos A． Guided Local Search with Shifting Bottleneck for Job Shop Scheduling[J]．Management Science, 1998,44(2):262-275．

[13] Brandimarte P． Routing and Scheduling in a Flexible Job Shop by Tabusearch[J]．Annals of Operations Research, 1993，41(3)：157-183．

[14] Pezzella F, Morganti G, Ciaschetti G． A Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]．Computers & Operations Research, 2008,35(10):3202-3212．

[15] Gao J, Sun L, Gen M． A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems[J]． Computers & Operations Research, 2008,35(9):2892-2907．

[16] 蔡保?。谠Ｗ尤核惴ǖ娜嵝宰鳂I(yè)車間調度問題研究[D]．宜昌:三峽大學, 2015．

[責任編輯 張 莉]

Improved Cellular Particle Swarm Optimization for Flexible Job Shop Scheduling Problem

Wu Zhengjia Fu Xianwang Wang Yun Liu Xiufeng

(College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China)

A mathematical model of flexible job-shop scheduling problem has developed based on the actual demand of the manufacturing enterprises. Aiming at its characteristics, a hybrid cellular particle swarm optimization (HCPSO) algorithm is proposed. A double-layer coding strategy is adopted to express the position information numerically for the order of the workpiece and machine.The crossover and mutation operation of genetic algorithm are introduced to improve the method of update with the particle position in the base of cellular particle swarm optimization. At last, the variable neighborhood algorithm is infused to enhance the ability of local exploration, The experiment results indicate that the solving ability of HCPSO has improved, so as to solve the flexible job shop scheduling problem effectively.

flexible job shop scheduling problem； double-layer coding； cellular particle swarm optimization algorithm

2016-09-18

湖北省自然科學基金(ZRY2014001091)

吳正佳(1964-)，男，教授，博士研究生，研究領域為生產(chǎn)管理、調度優(yōu)化．E-mail：zjwu@ctgu.edu.cn

10.13393/j.cnki.issn.1672-948X.2017.03.019

TP18

A

1672-948X(2017)03-0084-05