Abstract
The Job Shop Scheduling Problem (JSSP) remains a fundamental challenge in operations research due to its NP-hard nature. While Deep Reinforcement Learning (DRL) has recently been applied to develop smart heuristics for JSSP, most approaches rely on simple greedy inference, which often traps the solution in local optima. This paper introduces two novel search algorithms—Random Second Greedy Choice (RSGC) and Greedy Sampling (GS)—that introduce controlled randomness into the inference phase of pre-trained DRL models. By utilizing a dynamic probability function that prioritizes exploration in the early stages of the search, these methods significantly improve scheduling efficiency. Experimental results on the Taillard and DMU benchmarks demonstrate that RSGC and GS consistently outperform standard greedy and sampling methods, offering a memory-efficient alternative to complex tree searches.
Introduction
The Job Shop Scheduling Problem (JSSP) involves scheduling a set of jobs on a specific sequence of machines to minimize the total completion time, or makespan. Given its NP-hard complexity, finding optimal solutions for large-scale industrial instances is computationally prohibitive. Recent advancements have leveraged Deep Reinforcement Learning (DRL) to train Policy Networks that act as heuristics, suggesting the next task to schedule.
However, a significant gap exists in how these models are utilized during inference. Most current systems employ a "greedy" approach, selecting the action with the highest probability at each step. This strategy is prone to making short-sighted decisions that lead to suboptimal global schedules. This paper addresses this limitation by proposing search strategies that move beyond simple greedy selection to better explore the solution space.
Methods: Randomized Search Strategies
The authors propose two search algorithms designed to sit on top of a pre-trained Policy Network:
- Random Second Greedy Choice (RSGC): At each decision point, the algorithm probabilistically chooses between the highest-probability action and the second-best action.
- Greedy Sampling (GS): This method generalizes the deviation by sampling from the entire probability distribution when it decides not to follow the greedy choice.
Dynamic Probability and Exploration Timing
A key innovation of these algorithms is the use of a decreasing probability function to govern deviations. The authors posit that the Policy Network is more prone to errors at the beginning of the scheduling process. Consequently, the algorithms are designed to be more exploratory early in the search and increasingly greedy as they approach the final schedule. This "butterfly effect" approach ensures that diverse areas of the solution space are explored when decisions have the most significant impact on the final makespan.
Experimental Evaluation
The proposed methods were evaluated using a Policy Network trained on 20x20 JSSP instances using a Graph Isomorphism Network (GIN). The evaluation spanned two major public benchmarks:
- Taillard (TA) Dataset: Ranging from 15x15 to 100x20 instances.
- DMU Dataset: Standard benchmarks for testing algorithmic limits.
Results and Discussion
The experimental results indicate that RSGC and GS consistently outperform baseline methods across various problem sizes.
As shown in Table 1, the proposed algorithms achieve substantial reductions in makespan. For example, in the Ta02 instance (15x15), the baseline L2D model produced a makespan of 1544, while the RSGC algorithm reduced this to 1361—a significant improvement in scheduling efficiency. The effectiveness of these methods is even more pronounced in larger, more complex instances where standard greedy approaches typically struggle.
Key Insights
- The Value of Discrepancies: By occasionally "disobeying" the primary heuristic, the search can avoid local optima and discover superior global solutions.
- Search as a Force Multiplier: These results demonstrate that sophisticated search strategies can significantly enhance the performance of existing pre-trained models without requiring additional training.
- Memory Efficiency: Unlike Beam Search, which can be memory-intensive due to the need to store multiple environment states, RSGC and GS offer a more lightweight path to exploring the search tree.
Conclusion
This work highlights the importance of the inference strategy in DRL-based optimization. By introducing controlled randomness through RSGC and GS, the authors provide a robust framework for improving JSSP solutions. While these methods involve a trade-off in computational time due to multiple search passes, the resulting gains in schedule quality are substantial. Future research may focus on integrating these randomized strategies with other search frameworks or further optimizing the probability decay functions for industrial applications.
Summary updated