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

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