用图模型实现动态多目标调度，可按需求生成可行解
GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization
- 基于异构图结构设计扩散求解器，按约束类型选择性传播信息
- 在3个典型调度问题上达100%可行性，多目标误差低于0.20%
- 适合需要快速生成高质量多目标调度方案的研究者与工程师
现有神经组合优化求解器将解搜索建模为对最优决策的模仿，本质上限制于单目标最小化和静态约束。我们提出GOAL，一种基于关系图表示的条件扩散求解器，通过条件化人类指定的目标实现可控决策生成。引入异构图编码，不同边类型对应不同类约束，定义图神经网络的消息传递结构，使信息根据每类约束的语义选择性传播。GOAL在三个具有不同约束复杂度的经典调度基准上实例化并评估：流水车间问题（FSP）、作业车间调度问题（JSP）和柔性作业车间调度问题（FJSP）。在不修改架构的情况下，展示跨结构差异约束场景和问题类型的泛化能力。在所有三个基准上，GOAL在最多20个工件、60个操作的问题规模下达到100%解可行性，并在多个目标上实现接近零的平均绝对百分比误差（低于0.20%），解决方案质量与推理速度均优于NSGA-II和MOEA/D，最快提升达25倍。
原文摘要 · Abstract (English)
Existing neural combinatorial optimization solvers frame solution search as imitation of optimal decisions, inherently limiting their utility to single-objective minimization and static constraints. We propose GOAL, a conditioned diffusion solver over relational graph representations that enables controllable decision generations by conditioning on human-specified objectives. We introduce a heterogeneous graph encoding in which distinct edge types, corresponding to different classes of constraints, define the message passing structure of the graph neural network, which allows information to propagate selectively according to the ontology of each constraint. GOAL is instantiated and evaluated on three canonical scheduling benchmarks of various constraint complexity: the Flow Shop Problem (FSP), the Job Shop Scheduling Problem (JSP), and the Flexible Job Shop Scheduling Problem (FJSP). Generalization is demonstrated across structurally distinct constraint regimes and problem types without architectural modification. On all three benchmarks, GOAL achieves 100% solution feasibility and near-zero MAPE (below 0.20%) on multiple objectives for problem sizes up to 20 jobs and 60 operations, outperforming NSGA-II and MOEA/D in both solution quality and inference speed by up to 25x.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。