Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (23): 248-254.DOI: 10.3778/j.issn.1002-8331.2105-0299

• Engineering and Applications • Previous Articles     Next Articles

Job Shop Scheduling Problem Based on Deep Reinforcement Learning

LI Baoshuai, YE Chunming   

  1. Business School, University of Shanghai for Science & Technology, Shanghai 200093, China
  • Online:2021-12-01 Published:2021-12-02

深度强化学习算法求解作业车间调度问题

李宝帅,叶春明   

  1. 上海理工大学 管理学院,上海 200093

Abstract:

This paper proposes a method to deal with the changeable scheduling environment. This method combines the learning ability of deep neural network with the decision-making ability of reinforcement learning. The approach regards the job shop scheduling problem as a sequential decision-making problem. Deep neural network fits the value function. Scheduling state is represented as a matrix form for input. Some of scheduling rules are used as the action space to directly select the behavior strategy. It sets the reward function related to machine utilization, interacts with the environment to obtain the best scheduling rules for each decision point. The results on the OR-Library show the effectiveness of the algorithm.

Key words: reinforcement learning, deep reinforcement learning, job shop scheduling, deep Q network

摘要:

由于传统车间调度方法实时响应能力有限,难以在复杂调度环境中取得良好效果,提出一种基于深度Q网络的深度强化学习算法。该方法结合了深度神经网络的学习能力与强化学习的决策能力,将车间调度问题视作序列决策问题,用深度神经网络拟合价值函数,将调度状态表示为矩阵形式进行输入,使用多个调度规则作为动作空间,并设置基于机器利用率的奖励函数,不断与环境交互,获得每个决策点的最佳调度规则。通过与智能优化算法、调度规则在标准问题集上的测试对比证明了算法有效性。

关键词: 强化学习, 深度强化学习, 作业车间调度, 深度Q网络