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

摘要： 针对一类以最小化最大完工时间为目标的作业车间调度问题（Job Shop scheduling Problem，JSP），提出了一种改进型蝙蝠算法（Improved Bat Algorithm，IBA）。为了克服基本蝙蝠算法在求解该类离散组合优化问题存在的局限性，首先对编码方案进行了设计，实现了算法中离散问题的连续编码；然后采用基于G&T算法和随机生成的方法初始化种群，以提高初始解的质量。此外，还引入了变邻域搜索策略，以避免算法早熟收敛，提高IBA算法的性能。最后，基于JSP问题的基准算例进行了大量仿真对比实验，结果显示了IBA算法的可行性和有效性。

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