周鑫

摘  要：在实际的柔性作业车间调度中，不但工件需要加工时间，而且工件在各个机器之间利用AGV（自动导引小车）转移也需要占用一定的时间，因此对柔性作业车间调度中考虑AGV运输时间的研究更具有实际意义。针对此问题，本文建立含有AGV的柔性作业车间调度的数学模型，针对问题自身特点对遗传算法进行改进，引入局部搜索策略加强局部寻优能力，将模拟退火算法作为局部搜索策略加入全局搜索中，增强了算法的收敛性能。通过在仿真实验平台上的实验数据结果可以看出，本算法有比较好的效果。

关键词：遗传算法;柔性作业车间调度;模拟退火;自动引导小车

中图分类号：TP301     文献标识码：A

Abstract： In the actual flexible job-shop scheduling， it is more of practical significance to consider transportation time of Automatic Guided Vehicle （AGV） in flexible job-shop scheduling Research， because workpieces not only require processing time， but also take a certain amount of time to be transferred between machines using AGV. Aiming at this problem， this paper proposes to establish a mathematical model of flexible job-shop scheduling with AGV and improve genetic algorithm according to characteristics of the problem. Local search strategy is introduced to strengthen the local optimization ability， and simulated annealing algorithm is added as a local search strategy to global search in order to enhance algorithm convergence performance. Experimental data from simulation experiment platform show that this algorithm is comparatively effective.

Keywords： genetic algorithm; flexible job-shop scheduling; simulated annealing; automatic guided vehicle

1   引言（Introduction）

FJSP是公認的NP难问题，所以FJSP一直是国内外学者研究的热点[1]。这个问题从20世纪90年代Bruker等人提出后，国内外的专家学者进行了深入广泛的研究。FJSP是JSP的扩展，JSP工件的工序所在的加工机器是固定的，FJSP更加符合实际车间中的生产环境。目前求解FJSP的主要智能算法有遗传算法[2]、免疫算法[3]、粒子群算法[4]、蚁群算法[5]等。张国辉等[6]使用随机初始化种群优化方法。赵诗奎[7]等基于设备均衡的策略并运用均匀设计的思想优化了种群的初始化方法。张立果[8]等针对多目标的柔性作业车间调度问题提出新的交叉策略来进行求解。在实际的生产环境中，工件在不同的加工机器之间通过AGV小车进行搬运。

对于AGV参与集成车间调度问题的研究也得到一些学者的广泛研究，付建林等[9]对AGV和车间调度之间的融合调度方法——AGV调度优化问题做了一个分类，为研究AGV融合车间调度的学者提供了学习的建议。……