柔性作业车间调度的精确邻域结构混合进化算法

王家海，李营力，刘铮玮，刘江山

（同济大学机械与能源工程学院，上海201804）

生产调度优化是制造执行系统的核心功能模块，也是公认的Np-hard难题［1］。求解生产调度优化问题对于企业提高设备利用率、节约生产成本以及缩短产品制造周期具有十分重要的意义。

柔性作业车间调度问题（flexible job-shop scheduling problem，FJSP）是经典作业车间调度问题的扩展，由于其打破了工序单一设备资源的约束，使生产过程具备一定的柔性，因此，FJSP更加符合生产实际，同时问题求解也变得更加复杂，尤其是多目标FJSP（multi-objective FJSP，MOFJSP）。

近年来，以智能算法为代表的MOFJSP求解方法由于其优越的全局搜索能力和易于实现的特点得到了广泛的研究和应用。然而，仅仅使用智能算法求解问题的最优解仍有一定的局限性。混合算法已被多位学者证实往往能够得到更优越的解，尤其是混合智能算法和邻域搜索。例如：Gao等［2］混合遗传算法和变邻域搜索求解MOFJSP，结果表明，该混合算法性能优于非混合智能算法。Li等［3］混合人工蜂群算法和邻域搜索，通过设计工序移动和机器置换两类邻域搜索方法有效提升了算法的求解能力。Gong等［4］混合模因算法和邻域搜索，通过设计N1和N2两种工序邻域结构求解问题的最优解，对比试验表明，该算法性能优越。Gao等［5］混合离散和声搜索算法和邻域搜索，运用公共关键块理论，针对不同优化目标采取不同邻域策略，试验结果表明，该算法明显优于非混合算法。

尽管混合邻域搜索的智能算法已有大量研究成果，然而在进行邻域搜索时盲目、随机、过多无效移动以及仅能优化单一目标的问题仍然存在［6-7］。……