吳正佳 付先旺 望 蕓 劉秀鳳

(三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院， 湖北 宜昌 443002)

求解FJSP的改進(jìn)元胞粒子群算法

吳正佳 付先旺 望 蕓 劉秀鳳

(三峽大學(xué) 機(jī)械與動(dòng)力學(xué)院， 湖北 宜昌 443002)

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

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

0 引 言

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

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

1 FJSP問題描述與模型建立

1.1 FJSP問題描述

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

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

1.2 數(shù)學(xué)模型建立

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

(1)

(2)

(3)

(4)

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

2 求解FJSP的元胞粒子群算法設(shè)計(jì)

2.1 編碼與解碼

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

FJSP包含工件排序與機(jī)器選擇兩個(gè)子問題，編碼時(shí)也需分開處理，因此本文采用如圖1所示的雙層編碼的結(jié)構(gòu)．

圖1 雙層編碼示意圖

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

2)解碼

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

2.2 粒子位置信息更新方法

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

(5)

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

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

(6)

2.3 混合元胞粒子群算法設(shè)計(jì)

2.3.1 FJSP鄰域結(jié)構(gòu)設(shè)計(jì)

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

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

圖3 N5鄰域結(jié)構(gòu)

2)塊內(nèi)工序與塊首或塊尾交換的鄰域結(jié)構(gòu)：N5鄰域僅對(duì)塊首前兩個(gè)和塊尾后兩個(gè)進(jìn)行交換操作，較為單一，將關(guān)鍵塊內(nèi)的工序分別與塊首或塊尾工序交換，極大地豐富關(guān)鍵塊的鄰域，如圖4所示．

圖4 與塊首或塊尾交換的鄰域結(jié)構(gòu)

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

圖5 N6鄰域結(jié)構(gòu)

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

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

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

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

圖6 HCPSO流程圖

3 仿真實(shí)驗(yàn)與分析

3.1 仿真設(shè)計(jì)

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

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

表1 標(biāo)準(zhǔn)算例計(jì)算結(jié)果

3.2 結(jié)果分析

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

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

圖7 3種算法迭代過程圖

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

4 結(jié) 語

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

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

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

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

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

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

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

[7] 李艷鵬．基于粒子群和禁忌搜索算法求解作業(yè)車間調(diào)度優(yōu)化問題[D]．大連：大連交通大學(xué)，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] 吳正佳, 何海洋, 黃燦超, 等．帶機(jī)器故障的柔性作業(yè)車間動(dòng)態(tài)調(diào)度[J]．機(jī)械設(shè)計(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è)車間調(diào)度問題研究[D]．宜昌:三峽大學(xué), 2015．

[責(zé)任編輯 張 莉]

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

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

吳正佳(1964-)，男，教授，博士研究生，研究領(lǐng)域?yàn)樯a(chǎn)管理、調(diào)度優(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