批量流水线调度问题的混合离散蛙跳算法_图文

1、 1270 计算机集成制造系统 第 16 卷 对几种算法的 M S D 进行比较 , 结果如表 4 所示 。 表4 SFLA 及其改进算法的 MSD 比较 n ×m 化过程在各状态具有可控的概率突跳特性 , 是避免 算法早熟收敛的有力手段 。 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 结束语 本文根据 L FSP 的特点 , 在传统蛙跳算法模型 的基础上 ,提出了离散蛙跳算法 。结合插入邻域搜 索算法 ,以及扰动策略和模拟退火思想对 SFL A 算 法进行改进 。仿真实验表明了所得算法的优越性 。 将蛙跳算法用于解决组合优化问题 , 是进一步研究 的内容 。 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 大部分优于或等于 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 算法的性能 ,提高了求解质量 。 ( 2 对于所有测试问题 , 混合算法的 MSD 均优 参考文献 : 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 相比具有较强的稳定性 。 ( 3 对于 13 种不同规模的问题 , 三种混合算法 中 ,SFL A1 和 SFL A2 的求解质量和稳定性均优于 SFL A3 ,其中 SFL A2 表现得更为突出 。 41 21 2 SFL A 和改进算法的 E/ T 指标进化曲线 于遗传算法的批量 Flow2shop 调度问题研究 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 调度 问题的启发式方法 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. 以问题 m = 10 , n = 30 为例 , SFL A 和改进算法 的 E/ T 指标进化曲线如图 5 所示 。 由图 5 可以看出 ,S

10、FL A1 ,SFL A2 和 SFL A3 与 SFL A 相比较 ,都具有较高的求解质量和较快的收 敛速度 ,其中 SFL A1 和 SFL A2 优化性能最好 。 由以上分析得知 : 蛙跳算法具有较强的全局搜 索能力 ,通过对局部极值和全局极值以及随机产生 的解执行扰动和简化插入邻域搜索 , 增强了算法的 局部探索能力 , 并提高了效率 , 平衡了算法的全局 寻优能力和局部探索能力 。SA 的嵌入 , 赋予了优 第6期 潘玉霞 等 : 批量流水线调度问题的混合离散蛙跳算法 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 . 陈功贵 , 李智欢 , 陈金富 , 等 . 含风电 明 ,等 . 基于混合蛙跳算法的成品油管网优化设计 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 . 朱光宇 , 林蔚清 . 场电力系统动态优化潮流的混合蛙跳算法 J . 电力系统自动 化 ,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 . 中国工程 机械学报 ,2008 ,6 (4 :4282432. 基于阈值选择策略的改进混