改进细菌觅食算法求解柔性作业车间调度问题  

Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem

作　　者：吴秀丽[1] 张志强[1] 杜彦华[1] 闫瑾[1] 

机构地区：[1]北京科技大学机械工程学院,北京100083

出　　处：《计算机集成制造系统》2015年第5期1262-1270,共9页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(51305024);北京市自然科学基金资助项目(4133087);中央高校基本科研业务费资助项目(FRF-TP-14-031A2)~~

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]