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

1、 1270 計算機集成制造系統(tǒng) 第 16 卷 對幾種算法的 M S D 進行比較 , 結果如表 4 所示 。 表4 SFLA 及其改進算法的 MSD 比較 n ×m 化過程在各狀態(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 結束語 本文根據(jù) L FSP 的特點 , 在傳統(tǒng)蛙跳算法模型 的基礎上 ,提出了離散蛙跳算法 。結合插入鄰域搜 索算法 ,以及擾動策略和模擬退火思想對 SFL A 算 法進行改進 。仿真實驗表明了所得算法的優(yōu)越性 。 將蛙跳算法用于解決組合優(yōu)化問題 , 是進一步研究 的內(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 和三種混合算法可知 : 對于所 有測試問題 ,混合算法的 M RPI 大部分優(yōu)于或等于 SFL A 。SFL A1 , SFL A2 和 SFL A3 的平均 M RPI 分別為 01 006 7 ,01 006 5 和 01 012 1 , 遠遠小于 SF2 L A 的 01 015 1 。這表明嵌入

5、局部搜索能有效改善 SFL A 算法的性能 ,提高了求解質(zhì)量 。 ( 2 對于所有測試問題 , 混合算法的 MSD 均優(yōu) 參考文獻 : 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 . 周亞勤 ,李蓓智 , 楊建國 . 基 于 SFL A 。其中 SFL A1 , SFL A2 和 SFL A3 的平均 MSD 分別為 5 253

6、1 36 ,3 5441 65 和 12 5411 76 ,遠遠 小于 SFL A 的 62 0671 98 ,說明改進的算法與 SFL A 相比具有較強的穩(wěn)定性 。 ( 3 對于 13 種不同規(guī)模的問題 , 三種混合算法 中 ,SFL A1 和 SFL A2 的求解質(zhì)量和穩(wěn)定性均優(yōu)于 SFL A3 ,其中 SFL A2 表現(xiàn)得更為突出 。 41 21 2 SFL A 和改進算法的 E/ T 指標進化曲線 于遺傳算法的批量 Flow2shop 調(diào)度問題研究 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)度 問題的啟發(fā)式方法 J . 統(tǒng)計與決策 ,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. 以問題 m = 10 , n = 30 為例 , SFL A 和改進算法 的 E/ T 指標進化曲線如圖 5 所示 。 由圖 5 可以看出 ,S

10、FL A1 ,SFL A2 和 SFL A3 與 SFL A 相比較 ,都具有較高的求解質(zhì)量和較快的收 斂速度 ,其中 SFL A1 和 SFL A2 優(yōu)化性能最好 。 由以上分析得知 : 蛙跳算法具有較強的全局搜 索能力 ,通過對局部極值和全局極值以及隨機產(chǎn)生 的解執(zhí)行擾動和簡化插入鄰域搜索 , 增強了算法的 局部探索能力 , 并提高了效率 , 平衡了算法的全局 尋優(yōu)能力和局部探索能力 。SA 的嵌入 , 賦予了優(yōu) 第6期 潘玉霞 等 : 批量流水線調(diào)度問題的混合離散蛙跳算法 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 . 陳功貴 , 李智歡 , 陳金富 , 等 . 含風電 明 ,等 . 基于混合蛙跳算法的成品油管網(wǎng)優(yōu)化設計 J . 石油工 程建設 ,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 . 朱光宇 , 林蔚清 . 場電力系統(tǒng)動態(tài)優(yōu)化潮流的混合蛙跳算法 J . 電力系統(tǒ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 . 李英海 , 周建中 , 楊俊杰 , 等 . 一種 基于改進混合蛙跳算法的貼片機貼裝順序優(yōu)化 J . 中國工程 機械學報 ,2008 ,6 (4 :4282432. 基于閾值選擇策略的改進混