通过多任务遗传编程实现带目标偏好的多目标动态灵活车间调度

多目标动态灵活作业车间调度的突破性研究:一种通过多任务学习优化目标偏好遗传规划的创新方法

背景介绍

动态灵活作业车间调度(Dynamic Flexible Job Shop Scheduling, DFJSS)是一个重要的组合优化问题,在制造、仓储等领域的生产过程具有广泛的实际应用。例如,它被用于优化制造过程中的任务分配或仓库的订单拣选工作。该问题的核心是如何在动态环境中,为多个机器和多个作业执行灵活的任务分配和操作排序决策,从而最大化某些效率指标或最小化时间成本。然而,这个问题的复杂性极高,尤其是当任务动态到达或机器发生故障时,传统的优化方法往往面临计算复杂度和实时性不足等问题。

近年来,遗传规划(Genetic Programming, GP)作为一种超启发式方法,被广泛用于为动态灵活作业车间调度问题生成调度启发式规则。这些规则作为优先级函数,能够高效地支持实时决策。然而,研究人员发现在学习这些调度启发式规则时,其规则大小(size of rule,即规则节点数量)与规则的有效性(effectiveness)常常是潜在冲突的两个目标:更复杂的大型规则通常具有更高的有效性,而小规则虽然易于理解、计算高效,却可能无法产生理想的调度结果。

传统基于主导关系(dominance-based)的多目标优化算法,比如NSGA-II(Nondominated Sorting Genetic Algorithm II),在优化有效性和规则大小目标时容易偏向更易优化的规则大小。这种偏向导致大量小但无效的规则被保留,而效能良好的大型规则却容易在进化中被舍弃。这种“目标偏好不均的多目标优化问题”(multiobjective optimization with biased objectives)成为研究的一大挑战。

为了克服这些困难,论文作者提出了一种通过多任务学习(multitask learning)机制优化目标偏好的多目标遗传规划算法,旨在以知识共享的方式同时提升规则的有效性与宜用性,从而在动态调度领域取得突破性进展。


论文来源

此研究由Fangfang Zhang(通讯作者)、Gaofeng Shi、Yi Mei和Mengjie Zhang完成,研究者分别来自Victoria University of Wellington的“数据科学与人工智能中心(Centre for Data Science and Artificial Intelligence)”以及Emerson公司。论文发表在2025年1月的《IEEE Transactions on Artificial Intelligence》第六卷上,是多目标优化和遗传规划领域的重要贡献。


研究设计与工作流程

论文的研究设计分为以下几个重要步骤:

1. 背景与问题建模

研究从动态灵活作业车间调度问题的约束条件和目标出发,建模了一个包含两个互为冲突目标的多目标优化问题:规则大小(规则节点数量)和规则有效性。基于广泛使用的调度实例,该研究设计了目标优化环境,提出了三个主要的效能目标:最大流动时间(max-flowtime)、平均流动时间(mean-flowtime)和平均加权延迟时间(mean-weighted tardiness)。目标函数的数学定义明确,并针对动态到达的新任务和机器资源分配约束进行了模拟。

2. 算法框架与创新设计

提出了一种基于多任务遗传规划的全新算法“VMT_αNSGP”(Variable Multi-task α-Nondominated Sorting Genetic Programming)。该算法的具体流程如下:

  • 任务划分与子种群设计:将算法种群划分为两个子种群,分别对应两个任务:

    • 主任务:优化动态灵活作业调度问题的有效性与规则大小,采用基于α主导的多目标优化。
    • 辅助任务:利用传统主导关系进行优化,以偏向小规则的搜索。
  • α主导关系设计:通过动态调整α值的方式平衡目标偏好,赋予有效性更多关注。在大小为规则有效性较不均衡的场景中,该方法对主任务的搜索性能进行了显著优化。

  • 知识共享机制:设计了一种基于规则大小范围的知识共享策略。在进化过程中,不同子种群通过交叉操作共享相似规则大小范围内的个体,增强小规则的有效性。

  • 多样性控制与探索-利用平衡:采用熵值(Entropy)作为种群多样性评估指标,确保算法在早期保留较高种群多样性以进行探索,而在后期维持适度多样性以深入利用。

3. 实验设计

研究基于5000个作业、10台机器构建动态模拟场景,设置了不同利用率(例如0.75, 0.85, 0.95)条件,评估算法在九种目标组合下的性能表现。系统训练与测试分离,并采用独立的随机种子生成新的调度实例进行验证。同时,指标如超体积(Hypervolume, HV)和逆代距离(Inverted Generational Distance, IGD)用于评估多目标结果。


主要研究结果

  1. 优化性能:在九种不同场景下,VMT_αNSGP在HV和IGD的表现上均显著优于NSGP、αNSGP_A等对比算法。特别是,在高复杂度场景下,该方法的改进尤为显著。

  2. 高质量的Pareto前沿:VMT_αNSGP生成的Pareto前沿全面覆盖了规则有效性与规则大小的冲突区域,与对比算法相比,显然更具优势。

  3. 规则简单性与解释性:相比传统大规则,该算法增强了小规则的有效性。VMT_αNSGP最终获得的规则在复杂性有所提高的同时,仍能保持其可理解性和计算快速性。

  4. 多样性与稳定性:VMT_αNSGP在算法早期阶段维持了更高的种群多样性,之后多样性逐渐收敛,从而兼顾了探索与利用。


研究结论与意义

该论文提出了一种新颖的多目标遗传规划算法,充分利用多任务学习机制,应对了动态调度过程中大小规则偏好优化的难题。研究首次展示了如何通过任务分离与知识共享机制,有效提升小规则的有效性,而不用维护复杂的档案结构。这不仅在理论上是对多目标优化和调度启发式规则学习的重要补充,更为实际的生产调度问题提供了更高效、更可解释的优化方法。

研究亮点

  1. 创新性框架:通过结合任务分离和多任务学习方法,该算法为解决目标偏好过度问题提供了全新路径。
  2. 高效性与解释性结合:实现了效能与规则宜用性的高效平衡。
  3. 广泛适用性:该方法适用于其他类似的动态优化问题,如弧路由与仓储管理。

展望

未来研究可以探索更复杂的目标结构,例如三目标优化场景,并进一步分析路由规则与排序规则大小之间的更精细关联。此外,多任务学习机制在其他领域的应用同样充满潜力。