Research On Deep Reinforcement Learning Algorithms For The Job Shop Scheduling Problem

The Job Shop Scheduling Problem is a classical scheduling problem abstracted from the manufacturing industry.A good scheduling algorithm can solve this problem efficiently under the condition of satisfying the time and space constraints,and thus create great economic value for enterprises.The "Made in China 2025" sees the innovation and transformation of traditional manufacturing industries with the help of high technology as a national strategic goal,and deep reinforcement learning with intelligent decisionmaking capabilities will help accelerate the process of achieving this goal.Currently,Job Shop Scheduling Problem is mainly solved using traditional algorithms,which have disadvantages such as poor stability and the need for complex human priori knowledge.Research on deep reinforcement learning in the field of shop scheduling is still in its infancy,and this paper explores this emerging area.This paper’s main research work is as follows.Firstly,an end-to-end intelligent scheduling policy network that meets the constraints of the Job Shop Scheduling Problem is designed.The encoder of the scheduling strategy network performs feature extraction of the problem instances,and the decoder constructs the scheduling scheme step by step.A scheduling algorithm based on the idea of dynamic planning is proposed,which can calculate the makespan for the solutions generated by the scheduling policy network,so that the solution quality of the scheduling policy network can be evaluated.A Markov Decision Process model is developed for a reinforcement learning solution to the job shop scheduling problem,setting up the states,actions,policy,and rewards of the agent.A deep reinforcement learning algorithm with a baseline mechanism is used to continuously train and optimize the scheduling policy network to improve its solving ability and thus generate scheduling solutions that allow the smallest makespan.The feasibility of the solution algorithm is tested on a selfgenerated dataset and compared with a traditional priority scheduling rule algorithm.The experimental results show that the proposed algorithm is superior in terms of solution quality and stability of the algorithm.Secondly,the decision process and update mechanism of the scheduling strategy network are optimized to further improve the solving ability of the model.The communication mechanism of the scheduling policy network is proposed to cope with the decreasing size of the problem during the scheduling process.Ablation experiment is set up to demonstrate that the inclusion of the communication mechanism helps generate higher quality scheduling solutions.In order to evaluate the model’s solving capability for a step forward,the scheduling decision network trained by deep reinforcement learning is further tested using a standard dataset.Compared to the optimal deep reinforcement learning algorithms currently available,the algorithm proposed in this paper can generate scheduling solutions with shorter makespan on some of the standard datasets and has an advantage in terms of solution time.This paper designs an end-to-end intelligent scheduling policy network that meets the constraints of the job shop scheduling problem and proposes a communication mechanism for scheduling policy network optimization,which can achieve an efficient solution to the Job Shop Scheduling Problem and is valuable for both theoretical research and practical applications.