Rethinking Neural Combinatorial Optimization for Job Scheduling Problems via Transition-Aware Dual-Scale Solver

Neural scheduling policies face a representation–computation trade-off: compact candidate features can leave important action-induced changes implicit, whereas encoding complete successor states repeatedly processes largely unchanged information. Meanwhile, dependencies accumulate across decisions, while competition must be resolved among a changing set of feasible candidates, requiring both persistent context and detailed local comparison. To address these challenges, we propose the Transition-Aware Dual-Scale Solver (TADS). TADS combines a transition-complete action representation with a dual-scale encoder. For each feasible action, a task-specific compiler records the induced state changes as sparse typed edits. These edits reconstruct the canonical successor from the current state, while an order-invariant encoder maps each edit set to a transition embedding. The dual-scale encoder compares candidates through global–local reasoning. Global recurrent memory integrates the residual-state summary with the previously executed transition embedding to maintain context across decisions. Conditioned on this context, relation-aware local attention compares candidate transition embeddings and their scheduling relationships to guide action selection. The selected transition embedding feeds the next memory update, allowing subsequent decisions to account for the committed change. Experiments with independently trained policies across six scheduling formulations demonstrate competitive solution quality on synthetic test sets and public benchmarks.