计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (17): 52-56.DOI: 10.3778/j.issn.1002-8331.2010.17.015

• 研究、探讨 • 上一篇    下一篇

基于蛙跳算法的零空闲流水线调度问题优化

王亚敏1,潘全科1,冀俊忠2,包 云1   

  1. 1.聊城大学 计算机学院,山东 聊城 252059
    2.北京工业大学 多媒体与智能软件技术北京市重点实验室,北京 100234
  • 收稿日期:2009-12-15 修回日期:2010-05-10 出版日期:2010-06-11 发布日期:2010-06-11
  • 通讯作者: 王亚敏

Optimizing solution for solving no_idle permutation flow shop scheduling problem based on shuffled frog leaping algorithm

WANG Ya-min1,PAN Quan-ke1,JI Jun-zhong2,BAO Yun1   

  1. 1.College of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
    2.Beijing Municipal Key Lab of Multimedia and Intelligent Software Technology,Beijing University of Technology,Beijing 100234,China
  • Received:2009-12-15 Revised:2010-05-10 Online:2010-06-11 Published:2010-06-11
  • Contact: WANG Ya-min

摘要: 针对零空闲流水线调度问题,以E/T指标最优为优化测度,提出了一种蛙跳求解算法。首先,该算法采用新的个体产生方法,扩展传统蛙跳算法的求解模型。其次,使用带有启发式策略的种群初始化方法优化初始解性能。再次,借助基于种群多样性的方法进行排序和分组,并通过部分随机初始化策略保持种群多样性。最后,结合一种简单而有效的邻域搜索算法,达到局部探索和全局搜索之间的平衡,进而提高收敛速度。在若干benchmark问题上的仿真实验表明了所提算法的有效性。

关键词: 蛙跳算法, 零空闲流水线调度, 邻域搜索, 种群多样性

Abstract: A Shuffled Frog Leaping Algorithm(SFLA) is proposed to solve the No_Idle permutation Flow Shop(NIFS) scheduling problems with minimum of the penalties of the E/T criteria.First,the algorithm adopts a new method of individual production to extend the traditional model of SFLA.Second,it uses heuristic method to construct the initial solution.Third,it applies new sorting way based on the diversity of the population and some restart mechanism to avoid loosing diversity.Last,a simple but effective local search algorithm is developed to incorporate into the SFLA to stress the balance between global exploration and local exploitation,and to improve the speed of convergence.The algorithm employs the simple neighborhood search to improve the speed of convergence.The experimental results show that the proposed algorithm is effective and efficient for different scale benchmarks of NIFS.

Key words: shuffled frog leaping algorithm, no_idle permutation flow shop, neighborhood search, population diversity

中图分类号: