计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (17): 255-258.

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

改进细菌觅食算法解决零空闲流水线调度问题

李丽娟,吴  晓,王志龙   

  1. 西南交通大学 机械工程学院,成都 610031
  • 出版日期:2015-09-01 发布日期:2015-09-14

Research of no-idle flow shop scheduling based on improved bacteria foraging optimization algorithm

LI Lijuan, WU Xiao, WANG Zhilong   

  1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
  • Online:2015-09-01 Published:2015-09-14

摘要: 针对零空闲流水线调度问题,建立以最大完成时间为目标的数学模型,并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上,引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率,以加速算法的收敛过程,并有效抑制精英个体的逃逸,防止解发生退化。采用路径编码方式,通过MATLAB算例试验,表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性;同时,运用两种方式产生初始解:随机方式和NEH方法,进一步验证算法的鲁棒性。

关键词: 零空闲流水线调度, 细菌觅食优化算法, NEH启发式算法, 自适应迁徙概率, 鲁棒性

Abstract: For No-Idle Flow shop Scheduling problem (NIFS) with the target of maximum makespan, a new solution named Improved Bacteria Foraging Optimization algorithm (IBFO) is proposed in this paper. Compared to BFO, 3 modifications are added in IBFO. In the chemotaxis process, it introduces a crossover operator. During the process of reproduction, it applies a hybrid strategy based on both health degree and target value of the bacterium. And for elimination process, it puts forward a self-adaption probability instead of a constant data. It tests IBFO through 6 different size Taillard problems by MATLAB, the results indicate that IBFO is feasible and effective. Further, in order to test the algorithm’s robustness to initial value, two methods are applied to get the initial bacterium population: random and NEH method.

Key words: No-Idle Flow shop Scheduling(NIFS), Bacteria Foraging Optimization algorithm(BFO), NEH heuristic algorithm, self-adaption migration probability, robustness