用统一图结构实现线性复杂度调度,让强化学习在大规模生产中高效推理。
Scalable Production Scheduling: Linear Complexity via Unified Homogeneous Graphs
- 将不同节点映射到统一潜空间,用标准同质图网络建模资源竞争。
- 在大规模场景下保持零样本泛化,关键在于任务-机器比接近1时的结构饱和。
- 适合需要快速部署、跨规模通用的工业调度系统开发者使用。
在真实工业场景中高效求解作业车间调度问题,需兼具计算轻量与拓扑鲁棒性的策略。尽管强化学习在自动化派工规则方面展现出潜力,但现有模型常因二次图复杂度或异构层架构开销而面临可扩展性瓶颈。本文提出一种统一图框架,通过基于特征的同质化将不同节点角色投影至共享潜空间,使标准同质图同构网络以线性复杂度捕捉复杂资源争用,确保大规模工业应用下的低延迟推理。实证结果表明,该框架达到当前最优性能,并具备一致的零样本泛化能力。我们发现,任务-机器比($\/mathcal{J} \approx \/mathcal{M}$)是政策有效性的主要驱动因素,而非绝对问题规模。据此提出结构饱和假说:在临界拥堵实例上训练的策略($\/mathcal{J} \approx \/mathcal{M}$)能内化尺度不变的冲突解决逻辑,将大规模矩形实例视为饱和子问题的顺序拼接。该方法避免了昂贵的规模特异性再训练,防止对统计捷径的过拟合,为动态生产环境中强化学习解决方案的部署提供了稳健高效的路径。
原文摘要 · Abstract (English)
Efficiently solving the Job Shop Scheduling Problem in real-world industrial applications requires policies that are both computationally lean and topologically robust. While Reinforcement Learning has shown potential in automating dispatching rules, existing models often struggle with a scalability bottleneck caused by quadratic graph complexity or the architectural overhead of heterogeneous layers. We introduce a unified graph framework that employs feature-based homogenization to project distinct node roles into a shared latent space. This allows a standard homogeneous Graph Isomorphism Network to capture complex resource contention with linear complexity, ensuring low-latency inference for large-scale industrial applications. Our empirical results demonstrate that our framework achieves state-of-the-art performance while exhibiting consistent zero-shot generalization. We identify the job-to-machine ratio as the primary driver of policy effectiveness, rather than absolute problem size. Based on this, we propose a hypothesis of structural saturation, demonstrating that policies trained on critically congested instances ($\mathcal{J} \approx \mathcal{M}$) learn scale-invariant resolution strategies. Agents trained at this saturation point internalize invariant conflict-resolution logic, allowing them to treat massive rectangular instances as a sequential concatenation of saturated sub-problems. This approach eliminates the need for expensive scale-specific retraining and prevents overfitting to statistical shortcuts, providing a robust and efficient pathway for deploying RL solutions in dynamic production environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。