Knowledge-Augmented RL and CP for Flexible Job-Shop Scheduling

Job-shop scheduling (JSSP) and flexible job-shop scheduling (FJSP) are challenging combinatorial problems in which fast constructive policies may be limited by early decisions during schedule construction. We propose a knowledge-augmented reinforcement learning (RL) and constraint programming (CP) method that separates schedule construction from a hierarchical Destroy-to-Improve stage. A heterogeneous scheduling graph combines structural information with heuristic rules, Pattern Memory, and Repair-Aware Memory. The Destroy Policy determines where to search, an Operation-Selection Transformer scores the operations within the selected candidate to determine what to release, and CP determines how to reconstruct the resulting region while preserving feasibility. The models are trained on a moderate-scale curriculum of synthetic JSSP/FJSP instances up to $30\times 20$, yet remain effective on substantially larger benchmarks, obtaining competitive gaps with favorable quality-time trade-offs. They also transfer to flexible flow-shop scheduling without additional training. Finally, through a schedule-format adapter, the frozen Destroy-to-Improve model improves 445 of 675 schedules produced by five ReSched and DANIEL variants, without further fine-tuning.