一种结合强化学习的扩展图形方法,用于具有物料转移的分布式作业车间调度问题

《JOURNAL OF MANUFACTURING SYSTEMS》:An extended graphical method with reinforcement learning for distributed job shop scheduling problems with transfers

【字体: 大 中 小 】 时间:2025年12月31日 来源:JOURNAL OF MANUFACTURING SYSTEMS 14.2

编辑推荐:

  林黄|王东林|赵世奎 南京航空航天大学机械与电气工程学院,南京210016,中国 摘要 现代制造业通常需要跨多个工厂进行协作,因为专业设备分散且加工能力存在差异。在这种情况下,作业必须在不同的地点进行处理,而跨工厂转移会显著影响调度性能。本文研究了带有转移的分布式作业车间调度

  
林黄|王东林|赵世奎
南京航空航天大学机械与电气工程学院,南京210016,中国

摘要

现代制造业通常需要跨多个工厂进行协作,因为专业设备分散且加工能力存在差异。在这种情况下,作业必须在不同的地点进行处理,而跨工厂转移会显著影响调度性能。本文研究了带有转移的分布式作业车间调度问题,并提出了一种扩展图方法与强化学习(EGMRL)来有效解决该问题。EGMRL的主要创新有四点:首先,在图方法中引入了转移区,能够明确建模工厂内部和工厂之间的运输时间;其次,开发了一种分层路径搜索算法来加速路径探索,从而在保持准确性的同时提高计算效率;第三,基于Q学习的自适应策略根据工厂间状态动态指导作业的删除和重新插入,增强了在不同问题规模下的适应性;最后,集成了一种禁忌搜索模块作为局部改进策略,以细化工厂级别的调度并防止过早收敛。在240个扩展基准实例和一项实际工程案例研究中的综合实验表明,EGMRL在解决方案质量和稳定性方面始终优于四种竞争算法。

引言

随着产品定制需求的增长和市场波动性的增加,制造系统变得越来越复杂。传统的集中式生产模式受到严格资源分配和响应延迟的限制,难以满足动态环境中的灵活性和敏捷性要求。在这种背景下,分布式制造作为一种有前景的解决方案应运而生。通过实现多个工厂之间的协作,分布式制造促进了资源共享和能力互补,从而显著提高了企业在动态环境中的响应能力和生产灵活性[1]。然而,分布式制造模式也引入了新的调度挑战。其中,分布式作业车间调度问题(DJSP)是一个典型的例子[2]。在这个问题中,n个作业必须在F个工厂中处理,每个工厂本质上构成了一个独立的作业车间调度问题(JSP)[3]。当n = 1时,DJSP退化为经典的JSP。由于JSP已知是NP难问题,而DJSP除了处理工厂内部调度外,还需要在多个工厂之间分配作业,因此变得更加复杂,同样也是NP难问题。
大多数关于DJSP的研究假设每个作业只能在单个工厂内处理[4],[5],[6]。然而,这种假设忽略了跨工厂协作的现实。实际上,由于产品复杂性、劳动力成本和工艺专业化等因素,作业处理往往需要多个工厂之间的合作。例如,在航空发动机的涡轮叶片制造中,一个工厂可能使用增材制造来形成毛坯,然后必须将其转移到另一个工厂进行高精度CNC铣削[7]。同样,在电子产品制造中,精密组件的加工和最终产品的组装通常分布在不同的工厂中。在上述情况下,单个工厂无法独立完成整个加工过程,因此跨工厂转移变得不可避免。由于工厂间转移时间通常比工厂内部机器转移时间更长,其对完工时间的影响不容忽视,必须将其纳入调度模型中。为此,本文研究了带有转移的DJSP(DJSPT),旨在最小化完工时间。
鉴于启发式算法在解决NP难问题方面的优势,它们受到了广泛关注。其中,图方法(GM)由Akers(1956年)首次提出[8],是最早的启发式算法之一。GM的基本思想是将机器冲突映射到二维平面上的矩形障碍物上,从而将调度问题转化为最短路径搜索问题。半个多世纪后,Gon?alves和Resende[9]将GM扩展到多作业场景,并提出了著名的BRKGA算法,该算法更新了57个JSP基准实例的最佳解决方案。然而,过去十年中对GM的研究有限,主要是由于两个原因:首先,其应用范围狭窄,缺乏能够处理运输、顺序依赖性、机器灵活性或劳动力可用性等额外约束的变体;其次,其计算效率低下:正如Gon?alves和Resende所指出的,GM在大多数情况下占运行时间的90%以上,主要是因为路径搜索非常耗时。
总之,可以识别出两个重要的研究空白:首先,现有研究大多忽略了现代制造环境中日益普遍的跨工厂协作处理的实际需求;其次,尽管GM在解决经典JSP方面取得了显著突破,但它仍然存在效率低下问题,并且缺乏有效处理转移约束的能力,从而限制了其在更现实分布式调度场景中的适用性。受这些问题的启发,本文做出了以下贡献:
  • (1)
    通过在图模型中引入转移区,提出了扩展GM来处理工厂内部和工厂之间的转移,使GM能够解决带有转移约束的调度问题。
  • (2)
    设计了一种新的分层路径搜索算法,以显著提高GM在转移约束场景下的路径搜索效率。
  • (3)
    通过将Q学习与GM集成,开发了一种自适应方法,其中状态由工厂完成时间的差异定义,强化学习动态指导作业的移除和重构,以提高适应性和鲁棒性。
  • 本文的其余部分组织如下:第2节回顾相关文献;第3节介绍问题表述和数学模型;第4节介绍图方法和提出的路径搜索算法;第5节详细说明混合算法框架;第6节和第7节分别提供实验结果和结论。

    章节片段

    关于DJSP的研究

    随着经济全球化的推进和以客户为导向的定制趋势的增长,制造系统已逐渐从集中式向分布式模式演变。因此,分布式作业车间调度问题(DJSP)已成为学术界和工业界的研究热点。这个问题不仅涉及在多个工厂之间分配作业,还需要在每个工厂内进行详细调度。因此,DJSP非常复杂,并被归类为

    问题描述

    传统的分布式作业车间调度问题(DJSP)通常假设所有作业必须在单个工厂内完成。然而,实际上,由于专业设备的分散和加工能力的差异,一些作业往往需要在多个工厂之间协作处理。在这种情况下,当作业从一个工厂转移到另一个工厂时,必须明确计算跨工厂转移时间。同样,当作业在

    图建模和路径解码

    图方法(GM)最初由Akers(1956年)提出,用于解决两作业JSP[8]。后来,Gon?alves和Resende(2014年)将GM扩展到多作业JSP场景[9]。如图2所示,GM模型通过将机器冲突映射为几何障碍物来构建。在图2a中,X轴的下方表示由作业J1和J2组成的调度方案,而Y轴的左侧表示作业J4。当X轴和Y轴上的操作需要相同的机器时,

    算法框架

    在本节中,我们介绍了基于强化学习的扩展图方法(EGMRL)来解决DJSPT。EGMRL的总体框架如算法1所示。该算法包括四个主要组成部分:初始解生成、基于图方法的搜索、局部搜索和接受标准。在图搜索阶段,使用GM-T移除并重构一部分作业,从而实现作业级别的全局搜索。然而,关键挑战

    实验设计

    本节设计了五组实验。第一组专注于EGMRL的参数调整。第二组评估算法各个组件的性能。第三组实验测试初始解对算法的影响。第四组将EGMRL与其他代表性算法进行比较。第五组将所提出的算法应用于大学内的两个智能制造实验室,以验证其有效性。

    结论和未来工作

    本文提出了一种混合调度算法EGMRL,它结合了转移图建模、分层路径搜索和基于强化学习的自适应机制来解决DJSPT。主要贡献如下:
  • (1)
    提出了一种转移约束图方法,以扩展经典GM,使其能够处理DJSPT中的工厂内部和工厂之间的转移。
  • (2)
    为了加速路径搜索并降低计算成本,我们开发了一种分层路径搜索算法,实现了
  • CRediT作者贡献声明

    王东林:撰写 – 审稿与编辑,撰写 – 原稿,监督。林黄:撰写 – 审稿与编辑,撰写 – 原稿,方法论,数据整理。赵世奎:方法论,资金获取。

    利益冲突声明

    作者声明他们没有已知的可能会影响本文报告工作的竞争性财务利益或个人关系。

    致谢

    本研究得到了国家自然科学基金(授权号:52275490)的支持。
    相关新闻
    生物通微信公众号
    微信
    新浪微博

    热点排行

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

      版权所有 生物通

      Copyright© eBiotrade.com, All Rights Reserved

      联系信箱:

      粤ICP备09063491号