DRL-Transformer solves open shop scheduling, scaling from 10x10 to 100x100
Trained on small benchmarks, this AI scheduler generalizes to massive 100x100 problems without retraining.
Open shop scheduling (OSSP) is notoriously NP-hard—exact methods break down as jobs and machines multiply. A team from Louisiana State University (Ardali, Nyelele, Knapp) now proposes a Transformer-based policy trained via deep reinforcement learning (DRL) that sidesteps the need for hand-tuned heuristics. The encoder-decoder architecture uses multi-head attention and processes only the processing-time matrix as input. Training on small Taillard benchmarks (up to 10x10) yields schedules within 15–30% of known optimal makespans, a solid baseline for a learned approach.
The real surprise comes at scale. Without any retraining, the same policy was tested on randomly generated instances ranging from 40x40 to 100x100 jobs-and-machines. It achieved average gaps of 12.89–15.12% relative to standard lower bounds. Against classical dispatching rules—SPT, LPT, MWKR, and EST—the Transformer matched EST within a modest margin while decisively outperforming SPT and LPT. This suggests that a feature-light, DRL-trained Transformer can generalize dramatically beyond its training regime, offering a practical, no-tuning alternative for manufacturers and logistics planners facing large scheduling workloads.
- Trained only on small Taillard instances (max 10x10), the Transformer generalizes to random 100x100 problems without retraining.
- On large instances (40x40 to 100x100), the method achieves average makespan gaps of 12.89–15.12% relative to a standard lower bound.
- Outperforms classical dispatching rules SPT and LPT, and remains competitive with EST—a top heuristic—across all scales.
Why It Matters
A generalizable, feature-light scheduler could streamline manufacturing and logistics logistics, cutting the need for problem-specific tuning.