Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem
This addresses the complexity and time inefficiency of traditional methods for job shop scheduling, offering a promising approach for practical applications, though it is incremental as it builds on existing reinforcement learning and transformer architectures.
The study tackled the job shop scheduling problem by proposing an attention-based reinforcement learning method, which achieved results surpassing recent studies and outperforming common heuristic rules, with the trained learners being repurposable for larger-scale problems not in the initial training set.
Job shop scheduling problems represent a significant and complex facet of combinatorial optimization problems, which have traditionally been addressed through either exact or approximate solution methodologies. However, the practical application of these solutions is often challenged due to the complexity of real-world problems. Even when utilizing an approximate solution approach, the time required to identify a near-optimal solution can be prohibitively extensive, and the solutions derived are generally not applicable to new problems. This study proposes an innovative attention-based reinforcement learning method specifically designed for the category of job shop scheduling problems. This method integrates a policy gradient reinforcement learning approach with a modified transformer architecture. A key finding of this research is the ability of our trained learners within the proposed method to be repurposed for larger-scale problems that were not part of the initial training set. Furthermore, empirical evidence demonstrates that our approach surpasses the results of recent studies and outperforms commonly implemented heuristic rules. This suggests that our method offers a promising avenue for future research and practical application in the field of job shop scheduling problems.