面向鲁棒级联流水车间联合调度的方案到目标转换:一种多目标优化框架

《Expert Systems with Applications》:Scenario-to-objective transformation for robust cascaded flow-shop joint scheduling: a many-objective optimization framework

【字体: 大 中 小 】 时间:2025年12月19日 来源:Expert Systems with Applications 9.4

编辑推荐:

  李秋英|潘泉科|高亮|李伟民|杨胜祥中国上海200444,上海大学机电工程与自动化学院摘要在印刷电路板制造中,由于加工时间存在不确定性以及各阶段之间的相互依赖性,级联流水车间联合调度问题带来了巨大挑战。传统方法通常基于确定性假设或最坏情况分析,这限制了它们应对现实世界中各种变化的

  李秋英|潘泉科|高亮|李伟民|杨胜祥中国上海200444,上海大学机电工程与自动化学院摘要在印刷电路板制造中,由于加工时间存在不确定性以及各阶段之间的相互依赖性,级联流水车间联合调度问题带来了巨大挑战。传统方法通常基于确定性假设或最坏情况分析,这限制了它们应对现实世界中各种变化的能力。本研究将这种不确定性的级联流水车间联合调度问题重新表述为多目标优化问题,将每种特定场景下的完工时间视为一个独立的目标。每种场景代表了加工时间变化的不同情况,由此产生了必须同时满足的复杂约束条件,以确保调度方案的稳健性与可行性。为了解决这一问题,本研究开发了一种多种群协同进化贪婪算法,该算法通过考虑适应度因素来生成后代,并运用保持约束条件的操作来确保所有场景下解决方案的可行性。此外,还引入了一种基于知识的交互机制,以促进不同种群之间的学习,从而提高收敛速度并保持多样性。同时,还设计了两种基于贪婪算法的优化机制,以加强在有希望的区域内的搜索力度,並采用混合变异算子对最优解进行策略性扰动,避免过早收敛并推动全局探索。在基准测试实例上的大量实验表明,所提出的方法在收敛速度、多样性以及调度稳健性方面均显著优于五种现有的先进多目标进化算法,充分证明了其在处理不确定环境下的复杂约束调度问题时的有效性及实用价值。引言随着智能制造的快速发展以及对高吞吐量、高可靠性电子产品的需求不断增加,印刷电路板生产系统面临着越来越复杂的状况和更大的变化性(Fan等人,2024)。在这一背景下,一个突出的挑战就是级联流水车间联合调度问题,这类问题源于现代印刷电路板生产线中高度整合的多阶段加工流程(Wang等人,2024,Wang等人,2024)。与传统单阶段调度问题不同,级联流水车间联合调度问题涉及到两个结构上截然不同的阶段:表面贴装技术阶段和双列直插式封装阶段,这两个阶段通过自动引导车辆进行物料传输而相互连接。具体而言,表面贴装技术阶段被建模为分布式排列流水车间,而双列直插式封装阶段则采用混合流水车间配置(Wang、Pan和Sang,2024)。如图1所示,每项任务都会在可用的表面贴装技术生产线上依次经过印刷焊膏、元件放置、回流焊接以及自动光学检测等工序。完成后,半成品会通过自动引导车辆被运输到双列直插式封装加工区,在那里通过相同的并行设备完成元件安装和焊接工作。由于具有多阶段结构以及中间运输环节,级联流水车间联合调度问题带来了更多挑战,尤其是在协调各个相互连接的阶段之间的作业时,一个阶段的故障可能会直接影响下一个阶段的作业进度(Li等人,2025)。现有的研究大多是在确定性环境中探讨级联流水车间联合调度问题,即假设问题数据如任务加工时间都是固定的。然而,现实世界的制造系统本质上是动态的,往往会受到各种不确定因素的影响,包括机器故障、工人工作效率波动以及工具老化等问题(Baykaso?lu等人,2020,Chen等人,2024)。这些干扰会导致不同操作环境下的加工时间出现变化,因此确定性假设无法准确反映实际调度环境的复杂性(Wu等人,2021)。总体而言,考虑不确定性的调度方法主要分为两大类:鲁棒优化和随机优化(Jing等人,2021,Jing等人,2022)。鲁棒优化侧重于在预定义的不确定性范围内实现最坏情况下的性能,往往会导致解决方案过于保守。相比之下,随机优化则利用概率分布来描述不确定性,旨在优化各种场景下的预期性能,从而提供更为平衡且实用的视角(Wang等人,2023)。为了解决这类不确定性问题,基于场景的调度方法越来越受到关注(Fathollahi-Fard等人,2024)。这种方法考虑了不确定参数的多种可能情况, thereby提高了最终调度方案的稳健性和适应性(Liu等人,2019)。与那些专注于最坏情况性能的传统不确定性优化方法(例如最小-最大遗憾优化)(Wang等人,2018)或依赖于预定义的鲁棒性指标的方法(Jing等人,2022)不同,本研究通过考虑多种不同的不确定性场景,提出了更为全面的解决方案。该研究将原本属于NP难问题的鲁棒级联流水车间联合调度问题重新表述为带约束的多目标优化问题,将每种场景下的完工时间视为一个独立的目标。这样的建模方式能够得到一个帕累托前沿,其中包含了多种不同的权衡方案,有助于找出在不同生产条件下仍能保持稳定可靠性能的调度方案。进化算法被广泛用于解决复杂的离散优化问题。在多目标及众多目标优化领域,多种群协同进化框架展现出了强大的效能(He等人,2023,Liu等人,2023)。通过让多个子种群在不同的搜索区域内独立进化,多种群协同进化框架借助种群分解和并行进化的手段提升了搜索效率与收敛速度,而信息交流则有助于增强全局的多样性与适应性(Gong等人,2024,Yan等人,2024)。为了解决级联流水车间联合调度问题中任务加工时间存在不确定性的情形,本研究提出了一种基于场景驱动的多种群协同进化贪婪算法,该算法整合了多种特定场景下的种群,并通过基于知识的交互机制来促进种群间的协同进化。图2展示了如何将存在任务加工时间不确定性的级联流水车间联合调度问题转化为多目标优化问题,而S-MPCEGA则作为优化引擎,用于在多种不确定性场景下找到稳健的解决方案。据我们所知,这是第一项针对此类问题进行研究的工作,为处理具有不确定性的调度问题提供了一种全新的方法。本文的贡献可总结如下:(1)提出了一种新的框架,将基于场景的不确定性调度问题重新表述为多目标优化问题,将每种场景下的完工时间视为独立目标,从而能够更全面地评估在不同条件下的调度稳健性。(2)开发了一种多种群协同进化贪婪算法,以提高算法在各种不同场景下的适应性,进而提升解决方案的质量与稳定性。(3)引入了外部知识库,以便在最优个体与各个子种群之间进行知识交流,促进种群间学习,同时增强收敛速度与全局探索能力。(4)提出了一种基于适应度因素的后代生成策略,能够根据局部竞争状况动态调整搜索力度,实现有针对性且灵活的搜索过程。(5)设计了两种基于贪婪算法的优化机制,以加强在具有潜力区域的搜索力度。此外,还采用了混合变异算子对最优解进行策略性调整,从而在探索与利用之间保持平衡。本文的其余结构如下:第2节回顾相关文献,为研究奠定基础;第3节定义了多目标优化问题以及所研究的级联流水车间联合调度问题,并建立了相应的混合整数线性规划模型;第4节介绍了所提出的S-MPCEGA算法,第5节对其性能进行了分析;最后,第6节总结了主要研究成果并指出了未来的研究方向。相关研究片段多车间联合调度关于级联流水车间联合调度问题的首项研究是由Wang、Pan和Jing在2024年进行的,他们提出了一个混合整数线性规划模型,同时还设计了一种具有分解与合作机制的自适应迭代贪婪算法,用以优化总流程时间。为了进一步提高搜索效率,Wang、Pan、Sang等人又在2024年引入了一种可变迭代贪婪算法,该算法能够动态调整搜索空间,还将混合调度策略与前后向策略相结合,以此最小化完工时间。多目标优化介绍在现实世界中,许多问题都涉及到多个相互冲突的目标,需要同时加以考虑,这就促使人们形成了多目标优化问题的概念。一个包含Y个(Y≥4)需要最小化的目标的多目标优化问题可以表示为(Xie等人,2022,Yang等人,2023):minFx=f1x,f2x,?,fYx其中x代表一个解决方案的决策向量,Fx则表示该方案在所有目标下的适应度值。在多目标优化问题中,通常使用帕累托支配关系来进行解决方案的比较:一种解决方案若能使得其他所有解决方案的适应度值都降低,则称其具有帕累托优势。提出的算法为了在保证多个目标之间实现良好的探索与利用平衡的同时提升搜索效率,所提出的S-MPCEGA算法采用了多种群框架,每个子种群专门负责优化其中一个特定的目标(Xu等人,2023,Zou等人,2024)。整个种群由P=P1,P2,?,PY构成,其中每个子种群Pυ包含Nυ个个体,即N=N1,N2,?,NY。如图4和算法1所示,S-MPCEGA框架首先从……开始实验设置与性能指标S-UPT-CFJSP测试实例是根据Wang等人(2024,Wang等人,2024)的研究成果生成的,这些实例涵盖了DFPSP阶段中不同的流水线配置(h∈2,3,4)、任务数量(n∈20,50,100,200)以及机器数量(m∈5,10),同时HFSP阶段还包括s∈5,8个加工阶段以及数量为3,4台的相同并行机器τl。每种配置h,n,m,s,τl都被独立生成了5次,共计得到了480个测试实例。这里设定的不同离散场景的数量为Y=5,任务加工时间和运输时间则是通过抽样得到的。结论本文通过将加工时间存在不确定性的情况下的调度问题转化为多目标优化任务,来解决这一难题,其中每个目标对应着某种特定场景下的完工时间。为了解决这个问题,本文设计了一种具有问题意识的进化框架——S-MPCEGA,该框架结合了领域特定的启发式方法以及协同进化策略。通过协调基于适应度因素的……CRediT作者贡献声明李秋英:概念构建、方法设计、软件开发、研究实施、初稿撰写。潘泉科:方法设计、研究实施、资金获取、论文审阅与编辑、项目指导。高亮:资源提供、论文审阅与编辑。李伟民:论文审阅与编辑。杨胜祥:项目指导、论文审阅与编辑。利益冲突声明作者们声明自己不存在任何可能影响本文研究结果的已知财务利益或个人关系。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号