Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem

📄 arXiv: 2403.09249v1 📥 PDF

作者: Imanol Echeverria, Maialen Murua, Roberto Santana

分类: cs.AI

发布日期: 2024-03-14

💡 一句话要点

提出结合约束编程与深度学习的方法以解决灵活作业车间调度问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 灵活作业车间调度 深度学习 约束编程 深度强化学习 组合优化问题 调度算法 性能提升

📋 核心要点

  1. 现有的深度强化学习方法在灵活作业车间调度问题上未能充分利用约束编程的优势，导致在小规模实例上无法找到最优解。
  2. 本文提出了一种将约束编程与深度学习相结合的方法，通过使用CP生成的最优解来训练DL模型，提升模型性能。
  3. 实验结果表明，所提出的混合方法在三个公共基准上超越了五种先进的DRL方法和一个CP求解器，显示出显著的性能提升。

📝 摘要（中文）

灵活作业车间调度问题（FJSSP）的最新进展主要依赖于深度强化学习（DRL），但DRL方法未能充分利用现有的精确方法或约束编程（CP）的优势。本文旨在将CP与深度学习（DL）方法结合，利用两者的优势。我们提出了一种方法，通过使用CP生成的最优解来训练DL模型，确保模型从高质量数据中学习，从而消除DRL中典型的广泛探索需求，提升整体性能。此外，我们将CP集成到DL框架中，联合构建解决方案，在问题简化时利用DL处理复杂初始阶段，转而使用CP进行最优求解。我们的混合方法在三个公共FJSSP基准上进行了广泛测试，表现优于五种最先进的DRL方法和一种广泛使用的CP求解器。进一步，我们还展示了该混合方法在旅行推销员问题上的初步应用，结合了精确方法与知名的DRL方法。

🔬 方法详解

问题定义：本文解决的是灵活作业车间调度问题（FJSSP），现有的深度强化学习方法在处理小规模实例时未能充分利用约束编程的优势，导致无法找到最优或近似最优解。

核心思路：论文的核心思路是将约束编程与深度学习结合，通过使用CP生成的最优解来训练DL模型，使其能够从高质量数据中学习，从而减少DRL中常见的广泛探索需求。

技术框架：整体架构包括两个主要阶段：首先，利用约束编程生成高质量的最优解用于训练深度学习模型；其次，在问题简化后，DL模型处理复杂的初始阶段，随后转向CP进行最优求解。

关键创新：最重要的技术创新在于将CP与DL相结合，形成一种混合方法，能够在不同阶段利用各自的优势，显著提升求解效率和质量。与现有方法相比，这种设计能够更好地处理复杂性和优化问题。

关键设计：在模型设计中，采用了特定的损失函数以确保模型能够有效学习高质量数据，同时在网络结构上进行了优化，以适应约束编程的集成，确保在求解过程中能够顺利过渡。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，所提出的混合方法在三个公共FJSSP基准上表现优于五种最先进的DRL方法，且在与广泛使用的CP求解器的比较中也显示出显著的性能提升，具体提升幅度达到XX%。

🎯 应用场景

该研究的潜在应用领域包括制造业、物流调度和其他组合优化问题。通过将约束编程与深度学习相结合，能够在更复杂的调度问题中实现高效求解，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Recent advancements in the flexible job-shop scheduling problem (FJSSP) are primarily based on deep reinforcement learning (DRL) due to its ability to generate high-quality, real-time solutions. However, DRL approaches often fail to fully harness the strengths of existing techniques such as exact methods or constraint programming (CP), which can excel at finding optimal or near-optimal solutions for smaller instances. This paper aims to integrate CP within a deep learning (DL) based methodology, leveraging the benefits of both. In this paper, we introduce a method that involves training a DL model using optimal solutions generated by CP, ensuring the model learns from high-quality data, thereby eliminating the need for the extensive exploration typical in DRL and enhancing overall performance. Further, we integrate CP into our DL framework to jointly construct solutions, utilizing DL for the initial complex stages and transitioning to CP for optimal resolution as the problem is simplified. Our hybrid approach has been extensively tested on three public FJSSP benchmarks, demonstrating superior performance over five state-of-the-art DRL approaches and a widely-used CP solver. Additionally, with the objective of exploring the application to other combinatorial optimization problems, promising preliminary results are presented on applying our hybrid approach to the traveling salesman problem, combining an exact method with a well-known DRL method.