一种基于修正机制和强化学习的作业车间调度问题的优化算法

作者：苗宽; 李崇寿^*

来源：计算机科学, 2023, 50(06): 274-282.

• 调度
• 作业车间调度问题
• 强化学习
• 修正搜索算法

近年来，使用深度强化学习解决作业车间调度问题的研究主要集中于构造法，通过将作业车间调度问题视为顺序决策问题，逐步选择调度节点从而得到完整的解。尽管这种算法思想已经取得了不小的成果，但仍面临奖励构造困难、解决方案质量不高的问题，因此这一方法的发展受到制约。针对这些问题，设计了一种基于图神经网络和近端策略优化算法的强化学习构造框架。同时，针对因训练与测试数据分布不一致而带来的次优解问题，还设计了一种修正交换算子，以保证解的质量。最后，为了证明算法的有效性，在公开数据集和生成的数据集上进行了实验。实验结果表明，所提算法在中小规模实例上的结果优于目前最好的强化学习框架，不仅充分发挥了构造式强化学习框架求解迅速的优势，还通过修正机制有效缓解了次优选择问题，缩短了实例的最大完成时间。

• 单位
  西南交通大学