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

摘要

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 modi-fications are added in IBFO. In the chemotaxis process, it introduces a crossover operator. During the process of reproduc-tion, it applies a hybrid strategy based on both health degree and target value of the bacterium. And for elimination pro-cess, 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.%针对零空闲流水线调度问题，建立以最大完成时间为目标的数学模型，并提出了解决问题的改进细菌觅食优化算法。在标准细菌觅食优化算法的基础上，引入了交叉优化算子、混合复制策略以及一种基于健康度和适应度共同控制的自适应迁徙概率，以加速算法的收敛过程，并有效抑制精英个体的逃逸，防止解发生退化。采用路径编码方式，通过MATLAB算例试验，表明了改进细菌觅食优化算法在求解零空闲流水线调度问题上的可行性和有效性；同时，运用两种方式产生初始解：随机方式和NEH方法，进一步验证算法的鲁棒性。