基于蝙蝠退火算法的无等待流水线调度问题研究

无等待流水线调度问题(no-wait flow shop scheduling problem,NWFSP)是一类比较重要的复杂生产调度问题,并已经被证明是典型的NP问题.蝙蝠算法(Bat algorithm,BA)是一种较新颖的群体智能算法.本文针对蝙蝠算法在求解无等待流水线调度问题上的不足,提出一种蝙蝠退火算法,它通过采用ROV的编码方式以实现离散问题的连续编码,同时为了避免算法早熟现象引入了模拟退火算法.算法采用基于NEH的局部搜索规则,在很大程度上提高了算法的性能.利用标准Car问题和Rec问题算例进行仿真实验,结果表明了改进算法的可行性和有效性.

A Bat Annealing Algorithm for Solving the No- wait Flow Shop Scheduling Problem

NWFSP（ no - wait flow - shop scheduling problem）, as one of the most important problem in the complex production scheduling, has been proved to be a typical NP hard problem. The Bat Algorithm （BA） is a kind of new swarm intelligence algorithm. In order to resolve the inadequacies when solve no - wait FSP, a bat annealing algo- rithm is proposed. The algorithm uses the encoding of the ROV to achieve continuous encoding of the discrete prob- lem. In order to avoid the phenomenon of precocious, the algorithm combined with simulated annealing algorithm. The NEH local search greatly improve the performance of the algorithm. By doing a simulation of the Car and Rec problem, it turns out that the proposed algorithm is feasible and effective.