Dynamic Parallel Machine Scheduling With Deep Q-Network
提出一种基于深度强化学习的动态并行机器调度方法DPMS，通过设计状态、奖励和调度规则选择，在动态环境中学习最优调度策略，实验证明其有效性。
Parallel machine scheduling (PMS) is a common setting in many manufacturing facilities, in which each job is allowed to be processed on one of the machines of the same type. It involves scheduling <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> jobs on <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> machines to minimize certain objective functions. For preemptive scheduling, most problems are not only NP-hard but also difficult in practice. Moreover, many unexpected events, such as machine failure and requirement change, are inevitable in the practical production process, meaning that rescheduling is required for static scheduling methods. Deep reinforcement learning (DRL), which combines deep learning and reinforcement learning, has achieved promising results in several domains and has shown the potential to solve large Markov decision process (MDP) optimization tasks. Moreover, PMS problems can be formulated as an MDP problem, inspiring us to devise a DRL method to deal with PMS problems in a dynamic environment. We develop a novel DRL-based PMS method, called DPMS, in which the developed model considers the characteristics of PMS to design states and the reward. The actions involve dispatching rules, so DPMS can be considered a meta-dispatching-rule system that can efficiently select a sequence of dispatching rules based on the current environment or unexpected events. The experimental results demonstrate that DPMS can yield promising results in a dynamic environment by learning from the interactions between the agent and the environment. Furthermore, we conduct extensive experiments to analyze DPMS in the context of developing a DRL to deal with dynamic PMS problems.