基于遗传约束编程的资源受限作业调度
内容提要
本文综述约束规划与进化算法在调度优化中的应用，涵盖变量排序、强化学习、超启发式、课程分配和原油调度等问题，并提出多种混合方法以提升求解质量与效率。
延伸解读
监督学习优化变量搜索顺序
文章提到一种基于监督学习的变量排序策略，通过分类与回归模型预测问题实例的最优解，从而优化约束规划求解器的变量搜索顺序。该方法在工厂车间问题中表现优异，且与传统的基于领域的方法结合的混合策略效果更佳。这提示读者，机器学习可以辅助传统求解器提升效率，但混合方法可能比单一方法更有效。
强化学习端到端解决调度问题
文章介绍了一种结合约束编程和强化学习的端到端调度问题解决方法，仅需约束编码和小实例训练，在七个JSSP数据集上评估，能在相同时间限制内找到比静态PDRs和CP求解器更高质量的解决方案。这表明强化学习有潜力自动学习调度策略，减少对人工启发式的依赖，但需注意其泛化能力和训练成本。
超启发式自动发现优先级规则
文章提及一种基于MAP-Elites的超启发式方法，用于自动发现RCPSP的高效优先级规则，并与传统GPHH和人类专家规则比较，在多样性和性能上均有显著改进。这展示了超启发式在自动化设计规则方面的优势，可能减少人工设计规则的工作量，但实际应用时需考虑计算开销和问题适应性。
大规模原油调度的双阶段进化算法
针对大规模原油调度问题，文章提出启发式规则驱动的双阶段进化算法，包括全局搜索和局部优化，通过修复策略处理不可行解。实验表明该算法在合理时间内优于数学规划方法和元启发式算法。这为处理复杂工业调度问题提供了新思路，但读者需注意其依赖于经验操作知识设计的启发式规则，迁移到其他场景可能需要调整。
Q&A
基于监督学习的变量排序策略如何优化约束规划求解器？
该策略通过分类与回归模型预测问题实例的最优解，从而优化约束规划求解器的变量搜索顺序，在工厂车间问题中表现优异，且与传统的基于领域的方法结合的混合策略效果更佳。
强化学习如何用于端到端解决调度问题？
该方法基于约束编程和强化学习，通过神经网络架构和训练算法，仅需约束编码和小实例，在七个JSSP数据集上评估，能在相同时间限制内找到比静态PDRs和CP求解器更高质量的解决方案。
MAP-Elites超启发式方法在RCPSP中有什么优势？
该方法用于自动发现RCPSP的高效优先级规则，与传统的GPHH和人类专家的优先级规则相比，在多样性和性能方面都有显著改进。
大学课程分配问题中混合演化算法如何生成最佳课表？
该算法针对大学课程分配问题的约束和困难，生成最佳的课程分配方案，构建相关约束为每位教员准备无冲突且高效的课表，减轻手动分配工作量，在准确性和时间效率上优于基本优化算法。
深度Q学习和异构图神经网络如何用于约束编程的值选择启发式？
该通用学习过程结合深度Q学习算法、定制奖励信号和异构图神经网络架构，用于在约束编程求解器中获取值选择启发式，在图着色、最大独立集和最大割问题上实验表明，能找到更接近最优解的更好解决方案，而无需大量回溯。
大规模原油调度问题（LSCOSPs）如何通过双阶段进化算法解决？
针对LSCOSPs，开发了启发式规则驱动的双阶段进化算法（DSEA/HR），包括全局搜索和局部优化。全局搜索设计基于经验操作知识的启发式规则生成初始种群并加速收敛；局部优化提出修复策略将不可行解移动到可行区域。实验表明DSEA/HR在合理时间内优于现有数学规划方法和元启发式算法。
