Abstract: Aiming at Non-deterministic Polynomial (NP) feature of Flexible Job Shop Scheduling Problem (FJSP),an Improved Bacteria Foraging Optimization Algorithm (IBFOA) was proposed.An integrated strategy was adopted to solve the two sub-problems of FJSP which were machine assignment problem and operation scheduling problem simultaneously.The mapping relationship between problem and algorithm was established by representing bacteria unit as process string.Aiming at the general bacteria and the current optimal individual,a multiple chemotaxis operation was put forward to improve the local search ability of basic BFOA.In the reproduction,a reproduction threshold value and a death threshold value were set to determine which bacterium to be reproduced so that the historical knowledge was inherited.In the elimination and dispersal,a modified Longest Processing Time (LPT) heuristic rule was proposed to guide the dispersal to avoid the blindness in new areas.The experiment results showed that IBFOA could balance the exploration and the exploitation abilities perfectly,and could solve the FJSP effectively and efficiently.

Key words: flexible job shop scheduling problem, bacteria foraging optimization algorithm, multiple chemotaxis, reproduction, elimination and dispersal

摘要： 针对柔性作业车间调度问题的NP难特性,提出一种改进的细菌觅食优化算法。采用集成法策略同时求解柔性作业车间调度问题的机器分配和工序调度子问题。将细菌个体表示为工序串,建立问题和算法的映射关系;分别针对普通细菌个体和当前最优个体设计了多重趋化操作,以增强算法的局部搜索能力;复制操作设置繁殖阈和死亡阈,以提高对历史经验的继承程度;迁移/驱散操作中,结合改进的LPT启发式规则,提出带倾向性的迁移/驱散操作方式。采用正交试验对算法的重要参数进行了优化配置,通过搜索算子优化效果对比实验证明了正交试验的结论;进行了收敛性能对比实验,证明算法具有优秀的全局开发能力和局部探索能力;典型算例实验结果表明,该算法能够有效求解柔性作业车间调度问题。

关键词: 柔性作业车间调度问题, 细菌觅食优化算法, 多重趋化, 复制, 迁移/驱散