批量流水線調(diào)度問(wèn)題的混合離散蛙跳算法_圖文

1、 1270 計(jì)算機(jī)集成制造系統(tǒng) 第 16 卷 對(duì)幾種算法的 M S D 進(jìn)行比較 , 結(jié)果如表 4 所示 。 表4 SFLA 及其改進(jìn)算法的 MSD 比較 n ×m 化過(guò)程在各狀態(tài)具有可控的概率突跳特性 , 是避免 算法早熟收斂的有力手段 。 SFL A 4 6031 32 5 9281 32 6 3081 21 4 9171 55 37 2601 16 32 7041 27 47 5871 42 70 6491 28 76 8511 67 80 6321 59 117 5001 96 151 9551 45 169 9841 65 62 0671 98 SFL A1 4121 95

2、 4181 95 1 0711 10 7151 12 4 4411 30 2 9651 36 2 9841 56 6 3451 78 6 1301 42 8 2351 55 13 4141 17 11 9041 90 9 2531 53 5 2531 36 SFL A2 2301 95 5211 67 9261 16 6041 86 3 0161 77 3 0031 82 2 0291 86 5 4761 99 3 8641 58 5 0631 91 6 7321 37 7 1671 38 7 4411 13 3 5441 65 SFL A3 7261 96 1 5761 84 2 8251

3、62 1 7791 28 9 0201 51 5 6291 97 8 7221 31 14 0051 01 16 1081 14 14 7581 63 25 5791 49 30 1871 08 32 1231 05 12 5411 76 5 結(jié)束語(yǔ) 本文根據(jù) L FSP 的特點(diǎn) , 在傳統(tǒng)蛙跳算法模型 的基礎(chǔ)上 ,提出了離散蛙跳算法 。結(jié)合插入鄰域搜 索算法 ,以及擾動(dòng)策略和模擬退火思想對(duì) SFL A 算 法進(jìn)行改進(jìn) 。仿真實(shí)驗(yàn)表明了所得算法的優(yōu)越性 。 將蛙跳算法用于解決組合優(yōu)化問(wèn)題 , 是進(jìn)一步研究 的內(nèi)容 。 7× 3 7× 5 10 × 3 10 

4、15; 5 20 × 3 20 × 5 20 × 10 30 × 3 30 × 5 30 × 10 40 × 3 40 × 5 40 × 10 均值 由表 3 和表 4 可知 : ( 1 比較 SFL A 和三種混合算法可知 : 對(duì)于所 有測(cè)試問(wèn)題 ,混合算法的 M RPI 大部分優(yōu)于或等于 SFL A 。SFL A1 , SFL A2 和 SFL A3 的平均 M RPI 分別為 01 006 7 ,01 006 5 和 01 012 1 , 遠(yuǎn)遠(yuǎn)小于 SF2 L A 的 01 015 1 。這表明嵌入

5、局部搜索能有效改善 SFL A 算法的性能 ,提高了求解質(zhì)量 。 ( 2 對(duì)于所有測(cè)試問(wèn)題 , 混合算法的 MSD 均優(yōu) 參考文獻(xiàn) : 1 ZHOU Yaqin , L I Beizhi , YAN G Jianguo . Genetic algorit hm for lot2st reaming flowshop scheduling problemJ . Machinery , 2004 ,42 (10 :57259 (in Chinese . 周亞勤 ,李蓓智 , 楊建國(guó) . 基 于 SFL A 。其中 SFL A1 , SFL A2 和 SFL A3 的平均 MSD 分別為 5 253

6、1 36 ,3 5441 65 和 12 5411 76 ,遠(yuǎn)遠(yuǎn) 小于 SFL A 的 62 0671 98 ,說(shuō)明改進(jìn)的算法與 SFL A 相比具有較強(qiáng)的穩(wěn)定性 。 ( 3 對(duì)于 13 種不同規(guī)模的問(wèn)題 , 三種混合算法 中 ,SFL A1 和 SFL A2 的求解質(zhì)量和穩(wěn)定性均優(yōu)于 SFL A3 ,其中 SFL A2 表現(xiàn)得更為突出 。 41 21 2 SFL A 和改進(jìn)算法的 E/ T 指標(biāo)進(jìn)化曲線 于遺傳算法的批量 Flow2shop 調(diào)度問(wèn)題研究 J . 機(jī)械制造 , 2004 ,42 (10 :57259. 2 SUN Ling , L I Tieke , L IU Ruiwei.

7、 Heuristic met hod for flow2 shop scheduling p roblemJ . Statistics and Decision ,2007 ( 9 : 141 (in Chinese . 孫 玲 ,李鐵克 ,劉瑞偉 . 求解 Flow shop 調(diào)度 問(wèn)題的啟發(fā)式方法 J . 統(tǒng)計(jì)與決策 ,2007 (9 :141. 3 KRO PP D H , SMUN T T L . Optimal and heuristic models for lot splitting in a flow shop J . Decision Sciences ,1990 ,21 (

8、4 : 6912709. 4 TSEN G C T , L IAO C J . A discrete particle swarm optimiza2 tion for lot2s2t reaming flowshop scheduling problemJ . Euro2 pean Journal of Oper2ational Research , 2007 ,191 (2 :3602373. 5 YOON S H , V EN TU RA J A. An application of genetic algo2 rit hms to lot st raming flow shop sch

9、eduling J . IIE Transac2 tions ,2002 ,34 (9 :7792787. 6 ELB EL TA GI E , H E GAZY T , GRIERSON D. Co mparison a2 mong five evolutionary2based optimization algorit hms J . Ad2 vanced Engineering Informatics ,2005 , 19 (1 :43253. 以問(wèn)題 m = 10 , n = 30 為例 , SFL A 和改進(jìn)算法 的 E/ T 指標(biāo)進(jìn)化曲線如圖 5 所示 。 由圖 5 可以看出 ,S

10、FL A1 ,SFL A2 和 SFL A3 與 SFL A 相比較 ,都具有較高的求解質(zhì)量和較快的收 斂速度 ,其中 SFL A1 和 SFL A2 優(yōu)化性能最好 。 由以上分析得知 : 蛙跳算法具有較強(qiáng)的全局搜 索能力 ,通過(guò)對(duì)局部極值和全局極值以及隨機(jī)產(chǎn)生 的解執(zhí)行擾動(dòng)和簡(jiǎn)化插入鄰域搜索 , 增強(qiáng)了算法的 局部探索能力 , 并提高了效率 , 平衡了算法的全局 尋優(yōu)能力和局部探索能力 。SA 的嵌入 , 賦予了優(yōu) 第6期 潘玉霞 等 : 批量流水線調(diào)度問(wèn)題的混合離散蛙跳算法 1271 7 WU Huali , WAN G Yuchun , CH EN Kunming , et al . O

11、pti2 mal design of multi2product pipeline net work by shuffled f rog leaping algorit hm J . Pet roleum Engineering Const ruc2 tion ,2008 ,34 ( 1 : 14216 (in Chinese . 吳華麗 , 汪玉春 , 陳坤 9 CH EN Gonggui ,L I Zhihuan ,CH EN Jinf u ,et al . SFL Algorit hm based dynamic optimalpower flow in wind power integ

12、rated systemJ . Auto mation of Elect ric Power Systems , 2009 , 25 (4 :25230 (in Chinese . 陳功貴 , 李智歡 , 陳金富 , 等 . 含風(fēng)電 明 ,等 . 基于混合蛙跳算法的成品油管網(wǎng)優(yōu)化設(shè)計(jì) J . 石油工 程建設(shè) ,2008 ,34 (1 :14216. 8 ZHU Guangyu , L IN Weiqing. Mounting sequential optimiza2 tion on surface mounting machine using imp roved hybrid f rog ju

13、mping algorit hm J . Chinese Journal of Const ruction Ma2 chinery , 2008 ,6 (4 : 4282432 (in Chinese . 朱光宇 , 林蔚清 . 場(chǎng)電力系統(tǒng)動(dòng)態(tài)優(yōu)化潮流的混合蛙跳算法 J . 電力系統(tǒng)自動(dòng) 化 ,2009 ,25 (4 :25230. 10 L I Yinghai , ZHOU Jianzhong , YAN G J unjie , et al . Modified shuffledf rog leaping algorit hm based on t hr2eshold selection st rategyJ . Co mp uter Engineering and Applications ,2007 ,43 (35 :19221 (in Chinese . 李英海 , 周建中 , 楊俊杰 , 等 . 一種 基于改進(jìn)混合蛙跳算法的貼片機(jī)貼裝順序優(yōu)化 J . 中國(guó)工程 機(jī)械學(xué)報(bào) ,2008 ,6 (4 :4282432. 基于閾值選擇策略的改進(jìn)混