Integrating Q-Learning with Branch and Bound for the Job Shop Scheduling Problem

The integration of machine learning (ML), particularly reinforcement learning (RL), techniques with classical optimization methods has shown significant potential in addressing the computational challenges of complex combinatorial problems. This paper presents a novel approach that enhances the Branch and Bound (B&B) algorithm with Q-learning, a type of model-free RL, applied to the Job Shop Scheduling Problem (JSSP). While B&B is a powerful method for finding optimal solutions, its computational demands are often prohibitive for large instances. By incorporating Q-learning into the B&B framework (BBQL), the proposed method learns to prioritize promising branches, thereby improving search efficiency and reducing computational overhead. We evaluate BBQL against the classic B&B algorithm on standard JSSP benchmarks. Experimental results indicate that BBQL achieves better makespan results with significantly lower computational costs, highlighting the potential of reinforcement learning to enhance traditional optimization frameworks in scheduling applications. This research offers insights into how AI-driven guidance can improve exact optimization methods, providing a scalable solution to complex scheduling challenges.