用记忆增强网络提升流水线调度优化效率,比现有方法更优。
Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling
- 构建异构图模型精准表示工序与机器分配关系
- 通过历史轨迹记忆提升策略网络决策能力,减少迭代次数
- 适合智能制造中动态调度场景,尤其对复杂生产流程有效
工业4.0推动智能制造向大规模定制和动态生产发展,对柔性作业车间调度(FJSP)提出更高要求。现有基于深度强化学习(DRL)的方法多采用构造性策略,虽有效但难达近似最优解。相比之下,改进型方法通过邻域搜索更接近最优解,但在FJSP的柔性机器分配下面临状态表示、策略学习与搜索效率难题。本文提出记忆增强型改进搜索框架MIStar,采用新型异构析取图显式建模机器上的工序序列,实现精确解表示;设计记忆增强异构图神经网络(MHGNN)提取特征,利用历史轨迹提升策略网络决策能力;并引入并行贪心搜索策略,加快解空间探索。在合成数据和公开基准上的实验表明,MIStar显著优于传统手工启发式方法及主流DRL构造类方法。
原文摘要 · Abstract (English)
The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。