Reinforcement Learning for Solving the Job Shop Scheduling Problem Based on Traveling Salesman Problem Model

This paper delves into the Job Shop Scheduling Problem (JSSP) with the overarching goal of minimizing the makespan. A traveling salesman problem (TSP) model of JSSP and its Markov decision process (MDP) form are proposed, and the attention-based policy network is trained by a reinforcement learning (RL) framework. Our method focuses on improving the quality of the existing scheduling plan instead of learning to choose the next operation to process. The experimental outcomes derived from randomly generated instances reveal that our algorithm consistently demonstrates the minimum makespan in comparison to the six classical methods. In addition, the simulation experience on large-scale instances shows the trained policy network is size-agnostic, and our method is effective and generalized.