计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (17): 191-193.DOI: 10.3778/j.issn.1002-8331.2009.17.058

• 工程与应用 • 上一篇    下一篇

求解置换流水车间调度问题的混合蚁群算法

周 鹏1,2   

  1. 1.湖北汽车工业学院 计算机系,湖北 十堰 442002
    2.西北工业大学 计算机学院,西安 710072
  • 收稿日期:2009-01-22 修回日期:2009-02-16 出版日期:2009-06-11 发布日期:2009-06-11
  • 通讯作者: 周 鹏

Hybrid ant colony algorithm for permutation flow shop scheduling problem

ZHOU Peng1,2   

  1. 1.Department of Computer Science,Hubei University of Automotive Technology,Shiyan,Hubei 442002,China
    2.School of Computer Science,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2009-01-22 Revised:2009-02-16 Online:2009-06-11 Published:2009-06-11
  • Contact: ZHOU Peng

摘要: 针对最大—最小蚂蚁系统在解决置换流水车间调度问题时易陷入局部最优的问题,引入最好—最差蚂蚁系统中的信息素变异和重置规则,提出了一种混合蚁群算法。使信息素矩阵变异并在搜索过程停滞时重置信息素矩阵以在搜索过程中引入多样性。在基准问题集上的对比实验表明,该算法比传统的蚁群算法具有更好的搜索全局最优解的能力。

关键词: 置换流水车间调度问题, 蚂蚁系统, 信息素变异

Abstract: To the problem that Max-Min Ant System(MMAS) plunges into local best situation easily when it is applied to Permutation Flow Shop Scheduling Problem(PFSP),a hybrid ant colony algorithm is proposed by incorporating the pheromone matrix mutating and restarting rule suggested in Best-Worst Ant System(BWAS).To introduce diversity in the search process,the pheromone matrix suffers mutations and a restart when the search process stops.Contrastive experiments on benchmark problems show that the hybrid algorithm has a better capability of global optimization than traditional ant colony algorithm.

Key words: permutation flow shop scheduling problem, ant system, pheromone mutatio