基于萤火虫算法的零等待流水线调度优化  

A Hybrid Glowworm Swarm Algorithm for No-wait Flow-shop Scheduling Problem

作　　者：李永林[1] 叶春明[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《机械设计与研究》2013年第6期50-54,共5页Machine Design And Research

基　　金：国家自然科学基金资助项目(71271138);教育部人文社会科学规划基金项目(10YJA630187);上海市一流学科项目(S1201YLXK)资助项目(S30504)

摘　　要：萤火虫算法是一种新颖的仿生智能算法,针对以最小化制造期为目标的零等待流水线调度问题,提出了一种基于萤火虫算法的混合优化方法。首先设计了一种IMM编码用于实现萤火虫编码与工件排序的转换以使萤火虫算法能够解决调度问题;其次用启发式算法对初始种群进行随机替换,以提高种群的质量和分散度;最后针对群体易于早熟和局部搜索能力的不足,结合迭代贪婪算法和Pairwise算法对最优个体进行改进并用Metropolis准则决定是否接受改进结果。在21个Benchmark问题上进行算法仿真,从求解质量和运行时间两方面验证了该混合优化方法的性能。This paper proposes an effective hybrid glowworm swarm optimization（GSO） algorithm for the no-wait flow-shop scheduling problem （NWFSP） with makespan criterion. Firstly, a IMM coding mechanism is proposed to transform continuous variables into job permutation so that the GSO can be applied to solve NWFSP. Secondly, the initial population is randomly replaced with heuristic algorithm in order to improve the population quality and dispers on. Finally, a strategy combined with iterative greedy method and Pairwise is employed to escape premature and to improve local searching, then Metropolis criterion is adopted to decide whether to accept the improved result. Simulations with 21 Benchmark validate efficiency and superiority of the proposed algorithm.

关 键 词：零等待流水线调度 萤火虫算法 制造期 迭代贪婪算法 Pairwise算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]