关键词: 作业车间调度问题；最大完工时间；蝙蝠算法；G&, T算法；变邻域搜索策略

Abstract: For the Job Shop scheduling Problem（JSP） with the objective of minimizing the makespan, an Improved Bat Algorithm（IBA） is proposed in this paper. To overcome the drawback of the basic BA in solving this kind of discrete?combination?optimization problem, the encoding scheme is designed first to realize the continuous encoding of the discrete problem. A population initialization method is adopted based on the G&T algorithm and the random rule to improve the quality of the initial solutions. In addition, a variable neighborhood search strategy is introduced to avoid the premature convergence and enhance the performance of the proposed IBA. Finally, extensive simulations are conducted based on benchmark instances of the JSP. The results show that the IBA is feasible and effective.

Key words: job shop scheduling problem, makespan；bat algorithm, G&T algorithm；variable neighborhood search strategy