计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (21): 35-38.

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

求解批量流水线调度问题的蜂群算法

桑红燕1,2,潘全科2,任立群3   

  1. 1.聊城大学 数学科学学院,山东 聊城 252059
    2.聊城大学 计算机学院,山东 聊城 252059
    3.聊城市人民医院,山东 聊城 252000
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-21 发布日期:2011-07-21

Artificial bee colony algorithm for lot-streaming flow shop scheduling problem

SANG Hongyan1,2,PAN Quanke2,REN Liqun3   

  1. 1.School of Mathematics Science,Liaocheng University,Liaocheng,Shandong 252059,China
    2.School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
    3.Liaocheng Hospital,Liaocheng,Shandong 252000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-07-21 Published:2011-07-21

摘要: 针对批量流水线调度问题,提出了一种改进的人工蜂群算法来优化最大完成时间。该算法运用NEH方法产生初始解,采用混沌遍历的方法生成新的邻域解。为了跳出局部最优,使用最优解的插入扰动来替换一些连续若干步不能改进的解来提高算法的全局搜索能力。采用自适应的局部搜索加强算法的局部搜索能力。仿真试验表明了所得算法的可行性和高效性。

关键词: 批量流水线调度, 最大完成时间, 人工蜂群算法, 微粒群优化, 局部搜索

Abstract: An Improved Artificial Bee Colony(IABC) algorithm is presented for solving the Lot-streaming Flow Shop Scheduling Problem(LFSP) with the objective of minimizing the maximum completion time,i.e.,makespan.In the proposed IABC algorithm,the famous NEH heuristic is used to produce an initial solution,and the chaos is employed to generate a new candidate.In order to avoid trapping into local optima,the solution not improved in a number of generations in the population is replaced by the perturbation of the best solution found so far.In addition,a self-adaptive local search is presented and imbedded in the IABC algorithm to balance the exploitation and exploration.The computational results show that the IABC algorithm is effective and efficient for the LFSP.

Key words: lot-streaming flow shop scheduling, maximum completion time, artificial bee colony algorithm, particle swarm optimization, local search