通过深度强化学习实现灵活作业车间调度中的批流优化 陈天天(Tiantian Chen) 李俊青(Junqing Li) 魏莉(Li Wei) 何俊超(Junchao He)

《Machines》:Lot Streaming Optimization in Flexible Job Shop Scheduling via Deep Reinforcement Learning Tiantian Chen, Junqing Li, Li Wei and Junchao He

【字体: 大 中 小 】 时间:2026年05月09日 来源:Machines 2.5

编辑推荐:

  摘要:本研究考虑了一种特殊版本的灵活作业车间调度问题(Flexible Job Shop Scheduling Problem),该问题在批量处理上具有相等且一致的约束条件(以下简称ECBFJSP)。这个问题涉及到多个协调方面的内容,如机床选择、工艺排序和批次分割,具有高度复杂性

  摘要:本研究考虑了一种特殊版本的灵活作业车间调度问题(Flexible Job Shop Scheduling Problem),该问题在批量处理上具有相等且一致的约束条件(以下简称ECBFJSP)。这个问题涉及到多个协调方面的内容,如机床选择、工艺排序和批次分割,具有高度复杂性,并对优化策略提出了严格要求。为了有效应对这一挑战,本研究基于改进的异构图神经网络(Enhanced Heterogeneous Graph Neural Network,EHGNN)构建了一个双重作用的深度强化学习算法框架。首先,创新性地提出了一个适用于ECBFJSP的改进异构图和EHGNN模型。通过整合工作订单优先级、机床加工能力和工艺约束等多维度节点特征,利用图形注意力网络(GATs)和长短期记忆单元(GRUs)实现了多种类型信息的动态特征聚合。该模型能够输出包含全局资源约束的上下文感知表示,大大提高了作业调度和批次划分的联合优化效率,显著增强了双重作用决策框架对ECBFJSP复杂性的适应能力。在决策机制层面,本研究设计了包括工艺排序-机床选择动作和批次划分动作的双重作用决策空间,并使用DAPPO算法协作优化双重作用策略,以确保决策过程的稳定性和效率。实验数据结果表明,与传统算法相比,所提出的智能决策框架在解决ECBFJSP问题时具有更好的调度质量,充分验证了该框架的有效性和实用性。

1. 引言
在生产管理中,批次流式处理(lot streaming)是一种广泛使用的方法,它将相同类型的作业批次分解为更小的子批次[1]。这种方法使得同一类别内的产品能够进行并行处理,显著减少了整体生产周期[2]。传统上,对于特定类型的作业,所有操作都会采用一致的批量大小计划以简化实施。尽管这种方法在流程制造和离散制造行业中得到了广泛应用,但它未能考虑到不同操作之间机床可用性的变化,尤其是在灵活作业车间环境中[3]。为了克服这一限制,为每个操作制定不同的批量大小计划对于提高机床利用率至关重要[4]。因此,探索适用于灵活制造环境的有效批量大小策略对于满足实际工业需求至关重要。

近期深度学习的进步在解决复杂现实问题方面取得了显著成就,特别是通过深度多智能体强化学习(Deep Multi-Agent Reinforcement Learning,MARL)。MARL已成功应用于多种领域,如生产调度[5,6,7,8]、自动驾驶[9,10,11]和机器人技术[12,13,14],在这些领域中,任务自然表现为多智能体系统。例如,在生产调度中,子任务协调可以被建模为智能体在动态环境中优化资源分配和任务执行。

灵活作业车间调度问题(Flexible Job Shop Scheduling Problem,FJSP)是现代制造系统中的一个著名挑战,其特点是能够为同一操作分配多台机床[15]。这种灵活性给资源分配和调度决策带来了显著复杂性。批次流式处理技术通过将作业分解为更小的子批次来简化生产流程并减少空闲时间[16]。然而,在灵活作业车间环境中管理子批次分割、机床分配和调度顺序会显著增加决策复杂性,尤其是在面对生产变量时。

在智能制造中,有效地调度FJSP中的操作以实现成本降低和效率提升是一个关键挑战。主要的决策难点包括确定最优批次大小、子批次排序以及在满足设置时间和能耗等约束条件的同时进行机床分配[17]。在这些目标中,最小化生产周期(makespan)是本研究的主要优化目标[18]。此外,应用深度强化学习(Deep Reinforcement Learning,DRL)算法来解决FJSP问题仍然是一个具有挑战性的课题。

为了应对这些挑战,开发了一种专为FJSP环境中的批次流式处理设计的新型多智能体决策系统(Multi-Agent Decision-Making System,MADMS)。该系统利用多智能体近端策略优化(Multi-Agent Proximal Policy Optimization,MAPPO)算法来优化子批次调度和资源分配[19]。其核心是一个创新的多特征图融合网络(Multi-Feature Graph Fusion Network,MFGFN),该网络处理异构的离散图结构以提取局部和全局特征。这使得智能体能够做出实时、动态的决策,并有效协调它们的行动,以实现局部和全局优化目标,如最小化生产周期和减少空闲时间。将批次流式处理与MAPPO等MARL技术相结合,为FJSP固有的复杂性提供了一个有前景的解决方案。

本文的余下部分组织如下:第2节详细阐述问题陈述和模型构建;第3节介绍所提出的方法;第4节展示实验结果和分析;第5节总结研究结果并讨论未来方向。

2. 文献综述
2.1. 带有批次流式处理的灵活作业车间调度
灵活作业车间调度问题(FJSP)是制造系统中的一个经典优化问题,通常涉及两个子问题:机床分配和作业排序。当引入批次流式处理时,由于作业被分解为更小的子批次,会增加一层复杂性,需要决定子批次的大小、排序和机床分配。为了解决这些挑战,Gomez Urrutia等人[20]研究了一个综合考虑设置时间和设置成本的集成批次大小和作业车间调度问题,证明了适当的批次流式处理在减少生产延迟和成本方面的重要性。最近,Fan等人研究了在重新配置场景下的FJSP,其中包含了子批次之间的机床调整,以提高生产灵活性[21]。这些研究共同强调了批次流式处理在提高生产效率的同时解决实际调度约束方面的必要性。

Zhang等人[22]根据两个标准将批次流式处理问题分为四类:(1)子批次大小相等与不等;(2)批量大小政策一致与不一致。其中,子批次大小相等且所有操作采用统一批量大小政策的做法在研究和实践中得到了广泛应用。这种方法简化了实施过程,并确保了稳定的调度性能,特别适合需要同步工作流程以减少空闲时间的生产系统。相比之下,更灵活或可变的批量大小政策引入了额外的复杂性,在研究中受到的关注相对较少。然而,对于许多现实世界的制造环境来说,相等且一致的批量大小仍然是首选,因为其简单性、可靠性和与实际约束的一致性。

本研究在之前的工作基础上,专注于在FJSP中优化相等且一致的批量大小处理,并采用了批次流式处理框架。特别是,这项工作解决了设置活动和顺序依赖的设置时间等关键挑战,旨在进一步提高调度效率并减少生产周期。最近关于批次流式处理和FJSP的研究还强调了高级计算技术(如动态强化学习[19]和混合元启发式方法[18])在解决复杂调度问题方面的潜力。这些技术为将相等且一致的批量大小处理与现代优化方法相结合以进一步提高生产效率提供了坚实基础。

2.2. 批次流式作业车间调度中的启发式调度规则
在作业车间调度领域,批次流式处理——即将作业分解为更小的子批次以允许任务重叠——已被广泛研究,以提高生产效率。启发式调度规则如最短处理时间(Shortest Processing Time,SPT)、最长处理时间(Longest Processing Time,LPT)、先进先出(First-In-First-Out,FIFO)、剩余操作数量最少(Minimum Operation Processing Number Remaining,MOPNR)和剩余工作数量(Number of Work Remaining,NWKR)已被应用于优化这些过程。

SPT优先处理处理时间最短的作业,旨在减少平均流动时间并提高吞吐量。相反,LPT关注处理时间最长的作业,这有助于平衡机床工作负载并最小化生产周期[23]。FIFO按照作业到达顺序进行调度,确保实施的公平性和简单性。MOPNR选择剩余操作数量最少的作业,而NWKR选择剩余工作最少的作业,这两种策略都旨在加快关键任务的完成并提高整体流动效率[18]。在作业车间调度的批次流式处理背景下,这些启发式规则已被整合到各种算法中以应对复杂的调度挑战。例如,Pan等人提出了一种离散人工蜂群算法用于批次流式流水线调度问题,利用启发式规则指导搜索过程找到最优解[18]。这些研究表明,无论独立使用还是作为更复杂算法的组成部分,启发式规则在优化作业车间调度环境中的批次流式处理方面都发挥了重要作用。启发式规则的选择取决于具体的运营目标,如最小化生产周期、平衡工作负载或减少流动时间,应当与生产系统的独特要求相匹配。

总之,将SPT、LPT、FIFO、MOPNR和NWKR等启发式规则整合到批次流式处理策略中已被证明能有效提高作业车间环境中的调度效率和生产力。正在进行的研究继续改进这些方法,旨在开发更具适应性和智能性的调度系统,以应对现代制造过程的动态复杂性。

2.3. 基于DRL和MARL的调度方法
最近,深度强化学习(Deep Reinforcement Learning,DRL)和MARL在解决灵活作业车间调度问题(FJSP)方面取得了显著进展,特别是在应对其动态和去中心化特性方面。作为自适应框架,DRL将深度学习的感知能力与强化学习的决策框架相结合,使智能体能够通过将FJSP建模为马尔可夫决策过程(Markov Decision Process,MDP)来学习有效的调度策略。例如,Zheng等人提出了一种基于深度Q网络(Deep Q-Nets,DQNs)的DRL方法,用于处理带有作业插入的动态FJSP问题,其中调度状态信息被设计为通用调度规则[24]。这种方法显著减少了由动态作业到达引起的全局延迟,并展示了对变化调度条件的适应性。Lei等人提出了一种基于图神经网络的深度强化学习框架,将问题建模为多个马尔可夫决策过程(Multiple Markov Decision Process,MMDP),并利用多指针网络实现了高质量调度,并对大规模实例具有强大的泛化能力[25]。Song等人提出了一种基于异构图神经网络架构的新DRL方法,用于处理灵活作业车间调度的复杂性,将操作选择和机床分配整合到一个复合决策中,在多样化的大规模实例上实现了卓越的性能和效率[26]。

除了单一智能体的DRL方法外,MARL作为一种强大的框架,已被用于解决FJSP的去中心化特性,其中多个智能体协作同时优化操作排序和机床分配。例如,Jing等人提出了一种基于图的多智能体强化学习系统(Graph-Based Multi-Agent Reinforcement Learning System,GMAS),采用集中学习、分散执行的(Centralized-Learning, Decentralized-Execution,CLDE)结构,利用图卷积网络(Graph Convolutional Networks,GCNs)将FJSP建模为 Probabilistic Directed Acyclic Graph,并在动态和复杂的场景中实现了卓越的性能[27]。这种方法增强了状态表示和智能体协作,在大规模FJSP实例上取得了卓越的性能。同样,Zhang等人提出了DeepMAG,一种结合DRL和MARL的模型,使用多智能体图来解决FJSP中的作业排序和路由问题,使得协作智能体的效率和服务效果超越了现有技术[28]。Zhang等人提出了一种基于DRL的多智能体制造系统,结合了边缘计算和契约网络协议来高效处理动态调度,在随机和资源扰动环境中实现了稳健的性能[29]。Peng等人提出了一种带有双Q值混合(Double Q-Value Mixing,DQMIX)算法的MARL框架,用于解决扩展FJSP中的双重灵活性和变化运输时间问题,在复杂和大规模场景中实现了卓越的准确性、稳定性和泛化能力[30]。近年来还开发了其他强化算法来解决不同类型的调度问题[31,32,33,34,35]。

2.4. 文献分析
从文献分析可以看出,目前的大多数优化算法都存在局限性。例如,启发式方法在计算复杂性方面效率较高,但它们容易陷入局部最优解。DRL算法在效率方面也很高效,但在使用DRL解决FJSP问题时,需要设计更高效的架构。

这些研究共同强调了DRL和MARL在推进调度方法学方面的变革性影响。DRL在处理单一智能体框架中的动态决策方面展现了其优势,而MARL实现了智能体之间的去中心化协作,解决了操作和机器之间的相互依赖性问题。尽管取得了这些进展,仍然存在一些挑战,包括有效表示调度状态、代理之间的协调以及可扩展性以应对大规模问题实例。未来的研究应侧重于整合先进的神经架构,如基于图的模型和分层学习框架,以进一步提高动态和复杂制造环境中调度解决方案的鲁棒性和效率。

3. 研究方法论
所考虑问题的数学模型可以在[36]中找到。所提出的DRL方法的过程流程图如图1所示,左侧是异构析取图部分,用于表示三个状态,而右侧是多代理决策系统,其中包含多特征图融合网络以获得全局状态嵌入。

3.1. 基本概念
近端策略优化(PPO)是一种广受欢迎的强化学习算法,以其简单性和性能之间的平衡而闻名。它属于策略梯度方法类别,旨在通过最小化更新期间新旧策略之间的差异来优化代理的策略。PPO通过引入一种剪裁机制来限制策略更新,以防止策略发生过度大的变化,从而帮助稳定学习过程并提高收敛性。PPO的核心目标是通过优化以下损失函数来最大化预期累积奖励:
在这里, 是新旧策略之间的概率比, 是优势函数, 是一个控制剪裁范围的小超参数。PPO已在单代理环境中得到广泛应用,并在各种环境中取得了最先进的结果,特别是在连续控制任务中。其强大的性能和处理高维状态空间的能力使其成为多代理系统的基础。
在PPO在单代理环境中的成功基础上,MAPPO将这种方法扩展到完全合作的多代理系统。在MAPPO中,每个代理都维护自己的策略,但在执行决策时使用全局信息在集中式训练框架中进行训练。这种方法在多个代理共同努力实现共同目标的情况下特别有效,例如在去中心化部分可观察马尔可夫决策过程(Dec-POMDPs)中。

MAPPO利用了PPO中剪裁目标函数的核心概念,通过限制每次更新期间策略变化的程度来稳定策略更新。然而,在多代理设置中,每个代理必须在其策略中考虑联合行动和整体系统目标。在集中式训练阶段,所有代理都可以访问全局状态信息,从而能够更好地协调和优化其各自的策略。在去中心化执行阶段,代理依赖局部观察,独立做出决策,但决策方式与全局目标保持一致。MAPPO中每个代理的损失函数遵循与PPO相同的原理,但适应了多代理场景。代理的目标由以下公式给出:
其中 是代理 的新策略与旧策略之间的比率; 是优势函数; 是用于限制策略更新步长的剪裁参数。

通过集中式训练,代理可以利用完整的环境信息并协调行动以优化整体性能,例如在合作环境中最小化总完成时间。一旦训练完成,代理进行去中心化执行,这意味着它们根据局部观察独立行动,但其行动与训练期间学到的共享目标保持一致。MAPPO促进了多个代理的协调,确保它们有效地一起工作以实现整体系统目标,同时优化各自的策略。

在完全合作的多代理环境中,如灵活作业车间调度,MAPPO为代理提供了一种有效的方式来协调他们的行动,利用局部和全局信息来优化系统性能。

3.2. Dec-POMDP建模
FJSPLS是一个连续的、复杂的决策任务,需要在多个时间步骤中顺序决策来解决每个实例。在每个时间步骤,多个代理使用局部观察为可执行的动作分配优先级指数。然后,使用采样或贪婪解码策略,代理选择动作并将它们组合成一个联合动作来完成调度任务。
FJSPLS可以被建模为一个去中心化部分可观察马尔可夫决策过程(Dec-POMDP),由元组定义。这里, 是全局状态空间,代理无法直接观察;相反,他们通过局部观察获得有限的信息。动作集 是二维的,其中 对应于 的动作空间, 对应于 的动作空间。
状态转移函数 定义了从一个状态 到下一个状态 的转移概率,基于联合动作,其中 是调度代理的动作, 是批量流代理的动作。奖励函数 根据全局状态 和联合动作 提供反馈,确保两个动作都与整体任务目标保持一致。折扣因子 控制了决策制定中未来奖励的权重。通过这种方式构建问题,Dec-POMDP框架捕捉了两个代理如何基于局部观察协调他们的行动,以在信息不完整的情况下实现全局目标。状态、动作和奖励的Dec-POMDP结构定义如下:

全局状态。全局状态 是使用来自异构图的特征张量构建的,该图由操作、机器和作业节点组成。每种类型的节点包含特定特征,捕获灵活作业车间系统的当前状态。这些特征在调度过程中动态更新,代理利用这些节点的嵌入来做出决策。全局状态 包括以下节点的嵌入,每种类型的节点都由特定特征表征:
操作节点(8个特征):(1) 完成比率:操作的已完成子批次与总子批次的比率;(2) 邻近机器数量:连接到操作的机器节点数量;(3) 处理时间:包括计划内和计划外的批次的总处理时间(实际和估计);(4) 未计划操作数量:操作所属作业的未计划操作数量;(5) 完成时间:每个作业的估计或实际完成时间;(6) 开始时间:操作开始处理的时间;(7) 剩余子批次数量:操作尚未安排的子批次数量;(8) 剩余零件数量:尚未处理的零件数量。
机器节点(3个特征):(1) 邻近操作数量:连接到机器的操作数量;(2) 可用时间:机器开始新任务的下一个可用时间;(3) 利用率:机器的利用率,反映其当前工作负载。
作业节点(4个特征):(1) 作业零件数量:作业的总零件数量;(2) 最大批次数量:作业可能的最大子批次数量;(3) 实际批次数量:作业当前划分的实际子批次数量;(4) 作业完成时间:基于开始和时间的所有作业的最大完成时间。
局部观察。每个代理从特定节点特征接收局部观察。
1. 调度代理观察:调度代理观察操作和机器节点的特征。关于操作进度、机器可用性和工作负载的信息帮助代理做出调度决策。
2. 批量流代理观察:批量流代理观察操作和作业节点的特征。这使代理能够根据当前作业状态和操作进度做出如何分割或组合作业批次的决策。

联合行动。采用[10]中的联合决策方法,同时完成操作选择和机器安排。具体来说,动作 被定义为步骤t时的一个合格的操作-机器对。动作集 随着环境的变化而演变,包括所有适当的对。因此, 。的动作空间取决于 的动作。当 选择一个操作时,如果该操作所属的作业尚未确定分割策略,则 将为该作业建立分割策略。的离散动作空间 的大小等于 。每个离散动作对应于所选操作将被均匀分割成的子批次数量。如果所选操作所属的作业已经确定了分割策略,则 将为空。

状态演变。状态转移函数通常表示为一个条件概率,描述了系统在给定联合动作的情况下从当前状态 转移到新状态 的过程。状态转移函数的形式表达式为:
奖励 shaping。子批次操作和机器的选择和调度直接影响完成时间。因此,奖励函数定义为当前调度步骤中的估计(或实际)完成时间与上一步骤的完成时间(实际)之间的差异。这种差异作为改进的度量,其中完成时间的减少会导致正奖励,而增加会导致负奖励。这种设计鼓励代理通过他们的协调调度和批量分割行动来最小化完成时间。

3.3. 异构析取图(HDG)和HGFE
作业-操作-机器异构图。所提出的JOM-HG旨在模拟灵活作业车间调度环境中作业、操作和机器之间的关系。每种作业类型在图中对应一条独特的路径,从作业节点开始,然后是一系列操作节点,表示完成作业所需的步骤。每个作业节点都连接到同一路径上的相应操作节点,捕捉作业与其操作之间的依赖关系。此外,机器节点仅连接到它们能够处理的操作节点。这种图结构不仅表示操作的流动,还反映了机器分配的灵活性,使得调度和批量分割任务的决策更加精确。如图1所示,保留了作业节点集、操作节点集和连接弧集,并添加了一组机器节点,每个机器对应一个。析取弧集 终止了操作-机器弧和作业-机器弧。每个元素 是一个无向弧,将操作节点 与兼容的机器节点连接起来。每个元素 是一个有向弧,将作业节点 与所有对应的操作节点连接起来。
根据上述定义,本文将每个全局状态 表示为一个增强的析取图,其中 动态变化。当作业的特定操作的所有子批次都完全处理完毕后,相应的J-O边将被移除以获得 。对于每个步骤t,让 称为操作的可用机器, 称为要处理的操作数量。 表示机器 的静态相邻操作。作业原始特征向量、操作原始特征、机器原始特征和弧原始特征 被定义为步骤t的状态。

HGFE。HGFE通过3阶段节点特征嵌入和池化来提取全局观察信息。如图2所示,这些阶段包括嵌入机器节点、操作节点和作业节点。在第一阶段,通过消息聚合更新机器嵌入,在第二阶段更新操作嵌入,在第三阶段更新作业嵌入。图2. 3阶段节点嵌入的流程图。机器节点嵌入:机器节点嵌入结合了图注意力网络(GATs),通过应用注意力机制自动学习机器和操作节点的重要性。由于每台机器只连接到一个操作,我们将处理时间沿弧线整合到机器特征中,如 所示。表示测量 自信息的重要性的注意力系数,表示所有相邻操作对 重要性的注意力系数。公式中出现的两个矩阵用于线性映射原始特征。这两个矩阵是通过以下消息聚合函数计算得出的。

(1)操作节点嵌入:定义了六个MLP(分别表示为...),并实现了LeakyRELU激活函数。 和 分别代表操作前节点和后节点的原始特征。由于...,所有与 相邻的机器的状态信息是使用公式计算得出的。操作节点嵌入的计算过程如下:

(2)作业节点嵌入:作业节点嵌入与机器节点嵌入类似,旨在使每个作业节点能够从操作节点获取关键信息。 代表衡量自身信息重要性的注意力系数, 代表衡量所有相邻操作重要性的注意力系数。公式中出现的这两个矩阵也用于线性映射原始特征。嵌入的计算公式如下:

(3)池化和连接:在执行了L轮三阶段节点特征嵌入之后,分别对三种类型的节点嵌入特征向量应用均值池化。此过程之后进行连接,以获得增强型析取图状态的全局状态特征。

3.4. 多个代理的联合决策制定
为 和 设计了两个策略网络。对于每个动作,将作业、操作、机器和 的相应嵌入张量进行连接。随后,将连接后的张量输入到 中,以获得时间步t的动作得分(如公式(5)所示。所有不可行动作对的概率被设置为0。所有可行动作的得分使用softmax函数进行归一化(如公式(6)所示)。

(5)
(6)

对于每个动作,将相同的连接张量输入到 中,以获得时间步t的得分(如公式(7)所示。所有可行动作的得分使用softmax函数进行归一化(如公式(8)所示)。如果 之前选择了分解操作,那么 在时间t将不再选择分解动作。

3.5. 网络结构和训练
本文的网络架构如图3所示,包括HGFE、双代理策略网络和一个评论家网络。 和 分享相同的框架,但独立训练。 和 分别负责FJSPLS中的子任务。在逻辑上,它们将对方视为外部环境的一部分。在训练过程中,它们采用交替训练方法:在训练 时, 的参数固定;在训练 时, 的参数固定。本文通过梯度上升最大化预期累积奖励,并依次优化两个代理。DAPPO算法如算法1所示。

算法1:DAPPO
1. 初始化:调度代理策略网络的参数;分批代理策略网络的参数;调度代理策略网络的参数;分批代理策略网络的参数;评论家网络的参数;熵损失系数;策略损失系数;裁剪系数。
2. 生成B个案例;
3. 初始化状态;
4. 根据调度代理策略网络,使用分批代理策略网络获取实时动作对;
5. 获取奖励和下一个环境信息;
6. 找到优势估计函数和策略比率;
7. 如果 ,则终止;
8. 计算裁剪代理目标;
9. 计算熵目标;
10. 计算双代理损失函数;
11. 结束;
12. 对于PPO,执行以下操作:
a. 计算两个决策代理的损失函数并更新相应的网络参数;
b. 结束;
13. 输出:调度代理策略网络的参数;分批代理策略网络的参数。

图3. 网络架构。

4. 结果与讨论
为了验证前一篇文章中设计的算法的有效性,本节使用计算实验来评估算法在解决方案质量、解决方案效率和泛化性能方面的表现。实验首先描述了随机生成的实例和公共基准实例的具体情况。实验中涉及的示例范围广泛,包括根据本文方法生成的不同规模的实例,以及在实际中广泛使用的公共基准实例。

4.1. 实验实例
在ECBFJSP相关研究领域,目前没有经典的公共数据集,示例涉及许多参数,这些参数的具体值存在显著差异。基于此,本文使用训练集示例、验证集示例和测试集示例进行研究。具体来说,本文根据表1中指定的分布方法进行抽样。对于不同的规模,使用不同的随机数种子生成50个问题实例,并将其用作测试样本。此外,在每轮训练开始时,将生成一组与训练样本相同规模的50个验证示例。每个实例的训练时间设置为s。

表1. 随机和验证实例的分布。
为了评估所提算法的有效性和鲁棒性,扩展了著名的Brandimarte基准示例以包含批量流信息,从而获得了示例集Mk1_LS到Mk10_LS。这些示例的批量大小根据正态分布设置。经过这一修改后,基准示例更加完整,可以用来测试为批量流灵活作业车间调度问题设计的相关算法。

4.2. 实验参数配置
模型参数设置如下:在EHGNN模块中,工作订单、工艺和机床节点的嵌入向量的维度d设置为8,MLP的隐藏单元数量配置为128,隐藏层的数量确定为2;对于两种策略网络结构,使用具有3个隐藏层和128个隐藏层维度的MLP架构进行构建。对于DAPPO算法,总迭代次数为1000次,每轮并行处理20个ECBFJSP示例,并在每次迭代后使用Adam优化器更新网络参数。学习率、网络更新期间数据重用的数量和折扣系数分别设置为3。在损失函数系数中,裁剪系数=0.2,策略损失系数和熵损失系数分别为0.5和0.02。

4.3. 基准方法
对于批量流灵活作业车间调度,需要工艺-机器分配规则和分批策略来完成任务调度计划。需要注意的是,使用所有调度规则作为基准方法是不现实的。本文选择了五种代表性的调度规则作为基准方法,分批策略是随机相等和一致的分批。具体来说,这些规则包括:SPT + Random、FIFO + Random、NWKR + Random、LPT + Random和MOPNR + Random。为了直观比较不同方法的性能,定义了相对差距的公式。

4.4. 随机示例上解决方案质量的分析
本节使用小型和中型示例进行训练和测试,以验证模型的有效性和可行性。DADRL方法的训练过程在六个小型和中型示例(10 × 6、10 × 10、15 × 4、15 × 8、20 × 5和20 × 10)的训练中显示出良好的稳定性并收敛。图4选择了10 × 6和10 × 10的训练曲线进行展示。曲线是基于各自规模的100个验证集示例的平均完成时间绘制的。分析后发现,未经人类干预的智能代理可以通过自身的解决经验自主学习高质量的调度策略。

表2. 实验结果
为了验证所提算法在随机示例上的泛化能力,对20 × 15、30 × 5和30 × 10等中大型示例进行了评估。具体实施过程如下:首先在20 × 10规模的示例上完成DADRL模型训练,然后直接将训练好的模型应用于20 × 15、30 × 5和30 × 10等中大型示例进行测试。如表2中的实验结果所示,在中等和大型示例的测试场景中,该模型的性能优于基线调度规则和启发式方法。结果表明,在所有示例中,我们的算法均达到了最低值,凸显了其最佳性能。传统调度规则通常较高,在某些场景中超过50%,且调度效率明显低于我们的算法;尽管HGA和GA的效率相对较低,但仍然与我们的算法存在差距,并且在解决时间上有明显劣势。这个实验充分验证了本文算法在解决ECBFJSP问题上的有效性和优越性。

4.5. 扩展基准示例上的解决方案质量分析
为了验证所提算法的有效性和鲁棒性,本节优化并改进了经典的Brandimarte基准示例,并加入了批量流机制。具体来说,这些示例是基于真实Brandimarte基准示例的规模参数和[15,18]的批量规模参数使用正态分布标准进行初始化的。这种改进使基准系统更加完整,可以系统地测试为带有批量流功能的ECBFJSP设计的算法。虽然引入了额外的复杂性和挑战性元素,但它能更准确地再现实际应用场景中的复杂调度问题。该实验从改进后的Brandimarte基准中选择了10个示例,并整合了批量流功能,以适应批量处理、连续生产等工业调度需求。实验基于MOPNR + Random、SPT + Random、FIFO + Random、NWKR + Random和本文提出的DADRL模型算法的比较分析,以最小化完成时间为优化目标,该指标作为调度领域的核心参数,用于表征完成所有调度任务所需的总时间。图6显示了十个改进后的基准示例中六种方法的完成时间分布。从Mk1_LS到Mk10_LS示例的比较中可以看出,“我们的”算法的对应折线通常位于较低水平,执行时间通常低于MOPNR + Random等其他比较算法,尤其是在Mk8_LS示例中优势尤为显著;其他算法的折线波动较大,峰值执行时间明显高于“我们的”算法。这充分表明,“Ours”算法在处理每个示例时不仅具有更高的执行效率,还具有更稳定的时间控制性能,并且明显优于传统算法。图6显示了多种方法在扩展实例中的完工时间线图。图7中的箱线图直观地展示了六种方法的执行时间分布特征,包括MOPNR + Random、SPT + Random、FIFO + Random、NWKR + Random、LPT + Random和DADRL方法:DADRL算法的橙色水平线(中位数)显著低于其他方法,说明其平均执行时间最短,调度效率更高;同时,其箱高最短,上下界范围最窄,表明在不同实例中的执行时间波动很小,稳定性明显优于其他算法。相比之下,传统的算法如MOPNR + Random和SPT + Random不仅中位数较高,而且箱体较大,数据分布更分散,执行时间波动范围广,反映出稳定性和效率的双重缺陷。总之,所提出的DADRL算法在执行效率和结果稳定性方面均超越了传统算法,表现出更出色的调度性能。图7显示了不同方法在扩展实例中的完工时间箱线图。

4.6 实验讨论
通过与五种高效启发式算法(包括SPT + Random、FIFO + Random、NWKR + Random、LPT + Random和MOPNR + Random)以及两种高效元启发式算法(包括GA和HGA)的实验比较,证实了所提算法的有效性和高效性。与现有方法相比,主要科学创新点如下:(1) 通过整合工作订单优先级、机床加工能力和工艺约束等多维节点特征,并借助GATs和GRUs实现了各种类型信息的动态特征聚合,从而增强了搜索能力。(2) 采用DAPPO算法协同优化工艺排序-机器选择动作和批量分割动作的双动作决策空间,确保了决策过程的稳定性和效率。然而,如何提高全局和局部搜索能力仍然是最重要的挑战之一。因此,引入更高效的网络结构以捕获更多有用特征将是有帮助的。此外,在进化过程中还应考虑更多特定于问题的知识。

5. 结论
本研究探讨了具有均匀且一致批量约束的柔性作业车间调度问题的一个特殊版本。为了解决这个问题,基于增强异构图神经网络(EHGNN)的双动作深度强化学习算法框架被应用于此问题。通过整合工作订单优先级、机床加工能力和工艺约束等多维节点特征,并借助GATs和GRUs,可以捕获全局和局部特征。然而,所提出的算法仍存在许多局限性,需要在未来的工作中进行改进,例如:(1) 如何设计一种具有强学习策略鲁棒性和高泛化能力的高效算法;(2) 如何设计一种能够同时表示全局和局部特征的高效奖励函数。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号