混合遗传蝙蝠算法求解单目标柔性作业车间调度问题

Hybrid Genetic Bat Algorithm for the Single-objective Flexible Job Shop Scheduling Problem

针对以最大完工时间最小化为目标的柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP),提出一种混合遗传蝙蝠算法(HGBA).为了提高初始种群的质量与多样性,采用三种方式相结合产生初始群体;重定义惯性权重,采用动态递减的权值来平衡局部搜索与全局搜索;针对算法易陷入局部最优解的缺点,结合遗传算法的变异操作,提出一种基于变异操作的邻域搜索算法;同时根据编码方式以及位置更新可能造成的无效解情况,利用遗传算法的交叉操作提出混合列交叉方法来完成位置更新;最后,通过三个实例测试了算法的性能,实验结果验证了提出的算法在求解FJSP时的有效性.

In this paper,a hybrid genetic bat algorithm（ HGBA） is proposed for flexible job shop scheduling problem（ FJSP） with minimizing makespan criteria. In order to improve the quality and diversity of the initial population,the initial population is generated by combining the three methods. In this paper,the inertia weight is redefined to balance local search with global search. Then based on the mutation operator of genetic algorithm,a neighborhood search of the mutation operator is proposed for shortcoming of the local optimal solution. At the same time,according to the coding method and the ineffective solution caused by updating the location,a hybrid column crossover method is proposed to update the location inspired by the crossover operator of genetic algorithm. Finally,the performance of the algorithm is tested by three examples. The experimental results verify the effectiveness of the proposed algorithm in solving the FJSP.