工业5.0背景下考虑工时预算的汽车制造多模式资源受限项目调度问题
《iScience》:Multi-mode resource-constrained project scheduling problem considering man-hour budget for automotive manufacturing in Industry 5.0
【字体:
大
中
小
】
时间:2026年09月26日
来源:iScience 4.5
编辑推荐:
**亮点**
- 在汽车焊接单元中考虑工时预算的多模式资源受限项目调度问题(MRCPSP)
- 三阶段自适应模拟退火(TS-ASA)框架改善节拍时间
- 在真实案例中,相比基于规则的基线,实现了13.54%的完工时间缩减
**摘要**
受工业5.0范式的启发,将人机协作
**亮点**
- 在汽车焊接单元中考虑工时预算的多模式资源受限项目调度问题(MRCPSP)
- 三阶段自适应模拟退火(TS-ASA)框架改善节拍时间
- 在真实案例中,相比基于规则的基线,实现了13.54%的完工时间缩减
**摘要**
受工业5.0范式的启发,将人机协作(HRC)引入汽车白车身(BIW)焊接岛,提供了巨大的灵活性,但也带来了关键挑战:如何在严格不可再生的劳动力成本下平衡生产效率。为应对这一挑战,本研究探讨了刚性工时预算下的多模式资源受限项目调度问题(MRCPSP)。本文提出了一种三阶段自适应模拟退火(TS-ASA)框架,以解决优化问题中固有的结构性预算死锁问题。该框架集成了三种专门机制。在标准数据集上的广泛验证表明,该框架相比经典元启发式算法具有更优越的鲁棒性。此外,基于真实轿车焊接数据的工业案例研究表明,与基于规则的基线相比,TS-ASA实现了13.54%的节拍时间缩减。这一改进将有助于构建高性能制造系统,并为未来实际生产带来巨大收益。
**图形摘要**
**引言**
随着工业5.0的到来,制造业正从自动化向人机协作转型,生产灵活性逐渐提高。智能制造业研究呈爆炸式增长,作为该领域的代表性行业,汽车制造业整合了多种先进技术。然而,受Manzini等人所述的多品种、小批量实际需求的影响,在此情况下,白车身(BIW)焊接工序的效率是生产中的瓶颈问题,因为它依赖于有限资源的最优调度,以实现成本、资源和时间的最优配置方案。轿车主焊接岛工作站是焊接车间中最大的工作站,也是汽车生产流程中的瓶颈工序,因为机器人执行长时间焊接,同时还有手动辅助操作。资源约束、任务优先级约束和节拍时间约束构成了其在离散制造环境中的独特特征,与其他生产系统中的问题明显不同。考虑到协同性、非线性和高度复杂的权衡,遗传算法(GA)、粒子群优化(PSO)和模拟退火(SA)等元启发式算法已成为解决此类优化问题的标准方法。在复杂的BIW焊接环境中,标准元启发式算法容易出现过早收敛,即种群失去多样性并陷入次优解。
作为传统调度方法中的经典算法,启发式方法适用于解决NP难问题。在调度领域,自然元素启发式算法和扩展遗传算法(EGA)等几种成熟理论已被广泛用于分析资源分配并阐明其影响。对于生产前的资源分配研究,Zhang等人提出了一种线性规划驱动的进化方法,并展示了显著优势。在多任务机床加工环境中,Mieczyslaw和Mariusz在工艺规划中引入了非线性方法,实现了时间缩减和机器利用率提高。随着启发式算法的兴起,资源调度研究进入了一个新阶段。在不确定的环境中,Zhang等人提出了一种结合区间值直觉模糊熵权法(IVIFEW)的扩展遗传算法来解决调度问题,结果表明该方法有助于获得最优解。在产品设计阶段,Zhao等人采用混合元启发式算法缩短了设计时间。对于产品开发过程中的资源调度问题,Liu和Duan基于贝叶斯网络和蚁群算法建立了优化模型,结果表明该方法能有效解决问题。考虑到资源之间可能存在约束,Li等人提出了一种异构机器人的任务分配框架,结果表明该框架可灵活应用于各种场景。Kang等人引入静态与动态任务分配策略的组合,以考虑机器人资源约束下的调度问题。这些研究共同为启发式算法在资源调度中的应用提供了重要见解,集体强调了启发式方法对不确定性的适应能力。基于规则的启发式方法计算速度快,但决策受时间预算限制。在多模式调度环境且具有严格不可再生工时预算的情况下,这些启发式方法无法评估全局成本和时序,可能会在非关键并行任务上耗尽劳动力预算,导致资源死锁和不良结果。
智能优化算法为调度问题提供了多种有效解决方案。Yang等人改进了GA,Li和Tang提出了语义级组件调度方法,结果表明这些方法在解决调度问题中表现良好。对于航空航天领域的资源分配,Zhou等人提出了一种基于知识图谱的设备配额优化方法,最终实现了资源优化。改进的萤火虫算法和改进的隐马尔可夫模型等调度方法在制造车间中也取得了显著成果。Mateus等人采用优先级识别算法并完成了资源分配,贪心启发式算法在资源分配中表现出令人满意的效果,通过可插拔调度机制改进了资源利用率和作业处理时间。Wang等人引入了基于非支配排序遗传算法III(NSGA-III)的集成多目标优化模型,实现了分配策略的优化。结合嵌套PSO方法的NSGA-III算法在解决资源调度问题中表现优越。以优化时间和工人总数为目标,考虑优先级关系、资源可用性和资源数量等分配约束,Zhou和Bian建立了混合整数规划模型,结果表明生产线平衡性能显著提高。为实现生产线上的动态制造,Li等人开发了一种多模态生产线制造知识图谱(PLMKG),提高了生产线智能化水平。Wang等人提出了一种用于复杂资源分配的深强化学习方法,避免了基于模型的方法在非结构化装配场景中的局限性,提高了基于学习方法的训练效率,并减轻了策略泛化性能。Zhang等人开发了一种多目标离散蜜蜂算法,并通过实际场景分析证明了该方法的有效性和优越性。学者们将自适应算法与优化算法相结合,以提高方案性能。
尽管传统智能优化算法表现出卓越的全球搜索能力,但对于本文研究的多模式资源受限项目调度问题(MRCPSP),这些算法在任务排序与模式分配之间的耦合上表现不佳。在刚性预算约束下,算子可能生成不可行解,难以实现全局最优。因此,需要设计一种自适应分配机制,以实现资源分配和模式选择。
对于人机协作(HRC)场景中的资源调度问题,Zhang等人提出了一种高效的多目标离散蜜蜂算法,用于解决不确定环境下装配线中的人机协作问题,从而实现人机合作。针对飞机总装线(AFALs)的联合优化问题,Zheng等人提出了一种嵌入遗传算法用于资源再分配,实现了工期和成本的优化。近年来,深强化学习和端到端机器学习模型等先进数据驱动方法显示出解决复杂调度问题的潜力,为训练提供了毫秒级的推理速度。为提高制造系统的生产效率,学者们研究了人工工作者与机器人系统之间的动态任务再分配。Zhu等人提出了一种制造系统的动态重构优化方法,结果表明该方法能够合理地将任务分配给工人和机器人,并在智能制造系统中实现合理配置。然而,这些方法的有效性在很大程度上依赖于大规模、高保真的历史数据进行离线训练。在动态工业环境中,由于各种意外情况,生产经常中断,导致训练数据不可靠,影响方法性能。
此外,虽然HRC在资源调度方面在某些研究场景中展现了一定优势,但在离散制造系统下对工时预算的考虑尚未受到广泛关注。表S1总结了之前的资源调度综述。基于此总结,本研究提出了一种三阶段自适应模拟退火(TS-ASA)框架,并提供了考虑复杂制造系统调度中预算约束因素的调度方案。
现有大多数研究聚焦于可再生的机器而忽略了全局预算约束,普通的贪心策略可能导致预算过早下降。本文提出了一种基于反馈的TS-ASA模型,带有惩罚函数,并引入了动态邻域算子(DNO)、自适应冷却调度(ACS)和重启机制(RM),在激进探索和开发之间切换。图1展示了算法在实际汽车生产场景中的工作机制实例。分析流程包含四个部分:(1)工作站工艺分解,分析该工作站将处理哪个部件;(2)工作站特征与约束分析,解决工作站中的资源、任务和约束;(3)剖析资源分配与任务执行之间的交互机制,然后建立相关数学模型;(4)将前述数学模型输入TS-ASA算法,从而指导工作站内的资源调度。
**图1** 算法在实际生产场景中工作机制的实例
(A) 工作站工艺分解,(B) 工作站特征与约束分析,(C) 基本数学模型构建,以及 (D) TS-ASA算法应用。
**结果**
**实验设置**
参考Kolisch和Sprecher提供的实验实例,我们采用MRCPSP,具体为J20子集,该子集被广泛认为是计算调度领域的标准基准。我们随机选择10组实例,每组实例分别运行30次。为评估TS-ASA算法获得解的质量,我们使用最佳相对误差(BRE)、平均相对误差(ARE)、最差相对误差(WRE)、标准差(SD)等指标。
为在真实制造环境中验证所提出的TS-ASA的有效性,我们利用从轿车BIW主焊接装配工作站收集的数据,包括n=43个任务和8种不同资源类型(自动导引车[AGV]、R1–R7)。43个任务的拓扑逻辑由BIW的实际装配顺序确定,要求将侧板和顶梁固定到底板总成上,随后安装侧板,最后安装顶梁。这种刚性拓扑逻辑受资源需求影响,造成生产瓶颈,并成为调度网络中的关键拓扑。参数设置详见表S2。对于标准参数,模式0的加工时间取自生产线上测量的标准节拍时间。分配给资源R3和R4的任务配置了替代协作模式(模式1),可将节拍时间缩短30%,但产生10单位的工时成本。总工时预算严格设定为Cr=80。需要注意的是,缩短的节拍时间已考虑了人机协作过程中切换或协作引起的附加时间开销。该改进代表保守净收益而非理论效率提升。为弥合建模与实际生产之间的差距,所提出的TS-ASA框架被用作实际部署中的基准。当实际操作因人工波动或设备故障而超过阈值时,调度窗口暂时冻结,系统更新剩余任务拓扑、当前机器可用性和剩余关键工作预算。
**消融实验**
为验证算子对局部搜索的增强效果,本节通过消融实验比较了所提框架的性能。比较旨在确认算法模型中每个算子的必要性。我们进行了包含TS-ASA、GRAS-ACS-RM、GRAS-DNO-RM、GRAS-DNO-ACS和基本SA的实验,其中GRAS代表基本SA机制。每个目标算法运行100次,最大迭代次数设为1000。
图2展示了各算法最优解的收敛曲线,表1则提供了ARE、STD及其他关键指标的重要作用洞见。
**图2 不同算法的收敛曲线**
| 算法 | 平均最大完工时间 | 平均标准差 | ARE (%) | WRE (%) |
|------|------------------|------------|---------|---------|
| TS-ASA | 1,647.9 | 1.80 | 0.00 | 0.00 |
| GRAS-ACS-RM | 1,706.3 | 85.79 | 8.63 | 5.44 |
| GRAS-DNO-RM | 1,655.7 | 87.13 | 0.26 | 0.48 |
| GRAS-DNO-ACS | 1,664.6 | 17.92 | 0.56 | 1.01 |
| Basic SA | 1,685.1 | 79.16 | 3.42 | 2.67 |
**表1 消融实验对比**
图2表明,与基本模拟退火算法相比,ACS和RM算子显著提升了解质量和收敛性能,但其性能远不及包含DNO算子的其他算法。去除DNO导致效率显著下降,平均最大完工时间从1,647.9(TS-ASA)飙升至1,706.3(无DNO算子)。虽然去除ACS和RM后的平均成本与TS-ASA相当,但其解质量明显较差。TS-ASA实现了最低的ARE和最小的STD,显著优于无RM的算法(ARE为1.01%)。这证实了RM成功促使算法跳出深层局部最优,增强了最终解的精度和稳定性。分析中获得的最佳全局解为1,647.90秒。这些发现验证了所提方法在处理复杂调度问题时实现了计算效率与解精度之间的最优平衡。
为增强所提TS-ASA算法框架的严谨性,对DNO(ρ)和ACS(L_check)机制中的参数进行了敏感性分析,分别设定为{0.1, 0.3, 0.6}和{20, 50, 100}。表S3展示了分析结果。
研究发现,较低的探索阶段阈值ρ会导致过早收敛,使算法陷入次优完工时间的解。不适当的L_check会导致方差稳定但延长收敛时间。结果证实了所选参数的合理性,即ρ = 0.3和L_check = 50。
为评估所提TS-ASA的优化效率,我们引入了确定性构造启发式算法——贪心模式下的先进先出(FIFO-GM)作为基准。FIFO规定任务严格按照拓扑可用性进行调度。该算法优先处理入度为零的任务,不考虑关键路径或未来瓶颈。GM算法采用短视消耗策略,遍历任务序列,只要剩余工时预算充足,就为任何符合条件的任务选择加速模式。FIFO-GM基准在完全耗尽预算的情况下实现了1,906.00秒的最大完工时间,而TS-ASA在相同的预算约束下实现了显著更短的最大完工时间1,647.90秒,改进幅度约为13.54%。基于规则的启发式方法通常短视地将不可再生资源消耗在具有现有时间松弛的并行任务上,而TS-ASA则持续评估成本-时间权衡,确保人工干预仅压缩前驱关系中最大的完工时间。
### 不同算法的比较与评估
本节将TS-ASA算法与其他算法(即GA、离散粒子群优化(DPSO)和分布估计算法(EDA))的性能进行比较,以评估和验证TS-ASA的有效性。选择这些算法作为基准的原因如下:GA能够实现有效的全局搜索;DPSO具有快速收敛和并行搜索能力;至于EDA,它能够自适应地学习优质解的分布并避免过早收敛。
为确保公平和合理的比较,GA、DPSO和EDA在前述部分所定义约束的共同搜索空间上运行。候选解编码为(V_seq, V_mode)。为保持比较研究的公正性,我们调整了比较算法的参数以实现一致性。单点搜索的训练迭代次数设为1,000次,群体搜索设为100代、10个粒子,以确保评估次数的公平性。为保证算法公平性,比较方法(GA、DPSO和EDA)的超参数在BIW调度环境中进行评估,每个算法平均执行30次独立运行。结果如表S4所示。
GA参数设置如下:交叉率为0.8,变异率为0.2。DPSO的惯性权重为0.4,认知因子为1.5,社会因子为1.5。EDA参数设置如下:截断比率为0.1,学习率为0.3。为便于比较算法性能,每个实例运行30次。如图3所示,TS-ASA在一定程度上实现了比其他方法更快的求解速度。最值得注意点是,30次独立试验表明,所有方法都能找到相同的最佳解。尽管如图2表所示GA实现了比其他方法更短的计算时间,但GA的平均C_max高于其他方法。此外,所提方法的计算时间也短于其他方法,为0.4659秒。
**图3 四种算法收敛曲线对比**
| 方法 | 平均C_max | 最佳C_max | 标准差 | 平均时间(秒) |
|------|-----------|-----------|--------|----------------|
| TS-ASA | 1,647.9 | 1,647.9 | 0.00 | 0.4659 |
| GA | 1,665.9 | 1,647.9 | 39.98 | 0.3827 |
| DPSO | 1,647.9 | 1,647.9 | 0.00 | 0.7724 |
| EDA | 1,651.9 | 1,647.9 | 15.52 | 2.2188 |
**表2 与其他算法的对比**
图4提供了使用所提算法获得的最优解的甘特图。总之,TS-ASA的优异性能证实了该策略能够产生最稳健且高质量的调度方案。TS-ASA算法能够实现解决实际问题的高效解。
**图4 TS-ASA算法下最优解的甘特图**
为评估所提TS-ASA算法的性能和鲁棒性,我们在MRCPSP的J20基准集上与精确求解器(Gurobi)进行了比较。与标准单模态实例不同,多模态资源约束项目库(MMLIB)的J20实例通过引入灵活的执行模式和异构资源约束,使问题具有更高的复杂度,属于NP-hard问题。我们独立选取了10个实例来比较Gurobi和所提TS-ASA的性能。所提TS-ASA的最大迭代次数设为1,000次。结果表明,TS-ASA在10个实例上均获得了最优解和快速计算速度,平均最优性差距为0%,如表3所示。
| 实例 | TS-ASA运行时间(秒) | Gurobi运行时间(秒) | 官方最优解 | TS-ASA最佳值 | 最优性差距(%) |
|------|----------------------|----------------------|------------|-------------|----------------|
| j2012_2 | 0.0002 | 78.567 | 0.0021 | 4290 | 61.9 | 0 |
| j2012_5 | 0.0002 | 67.679 | 0.0125 | 3795 | 62.3 | 0 |
| j2016_3 | 0.0002 | 79.435 | 0.0272 | 8724 | 53.1 | 0 |
| j2016_9 | 0.0002 | 79.742 | 0.0099 | 2846 | 51.8 | 0 |
| j2018_2 | 0.0002 | 77.634 | 0.0035 | 6054 | 32.7 | 0 |
| j2018_5 | 0.0002 | 35.974 | 0.0073 | 0729 | 12.3 | 0 |
| j2018_10 | 0.0002 | 34.244 | 0.0062 | 3631 | 52.7 | 0 |
| j2019_1 | 0.0002 | 37.930 | 0.0172 | 0595 | 42.5 | 0 |
| j2019_4 | 0.0002 | 34.483 | 0.0033 | 0567 | 42.0 | 0 |
| j2019_7 | 0.0002 | 60.174 | 0.0050 | 7259 | 43.0 | 0 |
**表3 四种算法性能指标对比**
在实际焊接车间中,产品周期时间逐渐缩短,个性化市场需求导致生产线上的生产配置不断变化,导致工业生产环境中数据稀缺。本文提出的TS-ASA实现了良好的性能。
### 仿真分析
为确保调度框架的准确性,在Tecnomatix仿真平台上建立了虚拟调试环境。3D模型包括机器人、电极磨削器、夹爪放置架、线束、格栅、两层钢结构平台、定位夹具、滑台框架、地轨车及实物建模部件。随后,将由TS-ASA算法生成的理论优化序列输入到该校准的Tecnomatix模型中。图5展示了现实场景与模拟轿车主焊岛工作站的对比。通过数据交换,虚拟环境可以为实际生产场景提供解决方案,而现实场景有助于完善虚拟环境中的模型。本质上,虚拟环境与实际场景之间的交互形成了一个反馈回路,促进虚拟模型和现实生产过程持续改进,从而提升规划准确性和运营适应性。仿真结果表明,建立的仿真模型能够在时间内有效完成相应的生产工艺,提高了生产规划阶段的准确性和效率。
**图5 仿真平台和实际生产现场下的主焊岛工作站**
### 讨论
本文研究了人机协作汽车BIW焊接与装配岛的资源约束调度问题。该研究解决了在不可再生工时预算约束下最小化最大完工时间的挑战。为求解这一NP-hard问题,建立了混合整数线性规划模型。随后,提出了TS-ASA框架。与传统元启发式方法不同,TS-ASA引入了双向量DNO来协同探索序列空间和模式空间。此外,集成了ACS和RM以维持种群多样性。使用真实轿车焊接案例和标准基准进行了验证。计算结果表明,所提TS-ASA优于基于规则的FIFO-GM基准,实现了13.54%的周期时间减少。
TS-ASA在工业5.0范式中的效用在于其作为决策工具的应用。当动态预算分配模型面临动荡(如紧急订单导致的人工成本通胀)时,所提模型可以通过模拟不同级别的工时预算来识别生产瓶颈。对于因劳动力短缺导致可用工时减少的情况,资源重新分配结合该框架可以实现生产平稳运行。这验证了TS-ASA将有限工时分配给关键路径上瓶颈任务的能力,而非消耗资源。对数据集的统计分析进一步证实了所提算法相较于GA、DPSO和EDA等方法具有优越的稳定性和鲁棒性。
### 研究局限性
尽管本研究通过工时预算考虑了人工参与,但该方法在更广泛的范式下存在一定局限性,因为仅通过减少成本和人工参与量将其转化为定量资源约束是不够的,从而忽略了工业5.0环境中的人本因素。未来研究将聚焦于将TS-ASA框架扩展至多目标优化场景,如明确平衡能耗与生产效率之间的权衡。此外,探索处理随机扰动的动态重新调度机制仍是实际应用的一个前景方向。
### 资源可用性
**通讯作者:** 请求进一步信息和资源的请求应联系通讯作者张邦城(zhangbangcheng@ccut.edu.cn),并将由通讯作者履行。
**材料可用性:** 本研究未产生新的独特材料。
**数据和代码可用性:** 本文报告的所有数据将由通讯作者在请求时共享。所有原始代码公开可在 https://data.mendeley.com/datasets/gswbxhjmnw/1 获取。重新分析本文报告数据所需的任何附加信息均可向通讯作者请求。
### 致谢
本研究由吉林省重大科技专项和长春市(项目编号20250306008ZD)部分资助。
### 作者贡献
概念设计:B.Z.和Q.X.;方法论:Q.X.和B.L.;调查研究:Q.X.和L.L.;初稿撰写:Q.X.;撰写——审阅与编辑:B.Z.;资金获取:B.Z.、Z.G.和X.Y.;资源:Y.S.和Z.G.;监督:B.Z.
### 利益声明
作者声明无竞争利益。
### STAR★方法
**关键资源表**
| 试剂或资源 | 来源 | 标识符 |
|------------|------|--------|
| 沉积数据 | 实验数据、仿真输出、场景定义、输出 | 本文;Mendeley Data | Mendeley Data: https://doi.org/10.17632/gswbxhjmnw.1 |
| 软件和算法 | Python | Python Software Foundation | https://www.python.org |
| | PyTorch | Meta AI | https://pytorch.org |
| | gurobipy | Gurobi Optimization | https://gurobi.com |
### 方法细节
**问题描述**
与传统刚性汽车生产线任务绑定于特定机器不同,白车身总装与焊岛具有工艺灵活性和人机协作特征。为捕捉上述操作灵活性,将该问题抽象为多模态资源约束项目调度问题。设调度时间为T,问题由任务集J = {1, …, n}组成,其中每个任务i可以特定模式m ∈ M_i执行。核心优化目标是为每个任务确定开始时间S_i和执行模式y_im。假设标准加工时间为确定性值,用于生成初始离线预测计划。目标是最小化最大完工时间,即生产周期时间。
传统调度模型假设任务与资源之间存在静态映射,无法表示涉及人机协作的BIW主焊岛的动态特性。工时约束作为不可再生资源纳入,可在自动化模式和协作模式之间动态切换以解决瓶颈。
我们假设存在J = {1, …, n}个任务,每个任务具有执行模式M_i,同时存在可再生资源集K和不可再生资源集R。在建立MILP模型之前,建立以下假设。一旦任务以选定模式开始,必须不间断运行至完成。任务一旦开始,执行模式不可更改。规划班次内的资源容量已知且固定。
本研究的目的是在满足所有优先约束和资源约束的前提下,确定每个任务的开始时间和执行模式,以最小化循环时间。相关概念和假设如下。集合:J,任务索引集合;Mi,任务i的可用执行模式集合,其中m=0表示选择;m=1表示选择协作加速模式;P,优先关系;K,可再生资源;R,不可再生资源;T,加工时间。Ωr,共享同一可再生资源r并要求确定执行顺序的参数。
参数:dim,任务i以模式m执行时的加工时间;qimk,任务i以模式m执行时对可再生资源k的占用量;cimr,任务i以模式m执行时的人时消耗量;Qk,可再生资源k的容量;Cr,资源r的总人时预算。
变量:Si,任务i的开始时间,Si≥0;yim,若任务i选择模式m则等于1,否则等于0;ximt,若任务i以模式m执行且在时刻t处于活跃状态则等于1,否则等于0;zijr,若任务i在资源r上先于任务j处理则等于1,否则等于0;Ci,任务i的完成时间。
基于上述定义,构建混合整数线性规划模型如下。
(1) Z = min Cmax(目标函数,最小化最大完工时间)
(2) ∑(m∈Mi) yim = 1(每个任务必须且只能被分配至一种执行模式。在实际的BIW焊装岛中,该约束规定操作必须通过标准自动化或协作加速模式执行,不得含糊或同时分配)
(3) ∑(i∈J), ∑(m∈Mi) cimr·yim ≤ Cr(确保所选模式产生的累计熟练人时或其他不可再生资源消耗不超过全局上限Cr。这保证了加速人工干预所消耗的人时不超过给定生产班次的人工预算)
(4) Sj ≥ Si + ∑(m∈Mi) dim·yim(后继任务j的开始时间严格受前驱任务i的完成时间约束。任务持续时间取决于所选模式yim)
(5) ∑(i∈J), ∑(m∈Mi) qimk·ximt ≤ Qk(所有当前活跃任务对可再生资源的总需求不得超过瞬时可用容量Qk。这转化为车间设备的物理限制,表明对特定资源的需求在任意时刻不得超过其物理可用量)
(6) Ci = Si + ∑(m∈Mi) dim·yim(保证任务完成时间等于开始时间加上所选模式下的加工时间)
(7) Sj ≥ Ci ? M(1 ? zijr), ?(i,j) ∈ Ωr
(8) Si ≥ Cj ? M·zijr, ?(i,j) ∈ Ωr(若两个任务竞争同一资源,则不能重叠执行)
(9) Cmax ≥ Si + ∑(m∈Mi) dim·yim(确保全局制造跨度大于等于任何已执行任务的实际完成时间)
上述MILP模型可用于寻找最优调度方案,但具有优先约束和资源竞争的调度问题属于NP-Hard问题,精确方法的缺点如时间和计算负载不可避免。因此,有必要依赖启发式方法等高级方法,以产生高质量解。然而,模拟退火算法在处理实际问题时容易陷入早熟收敛和搜索空间探索效率低下的困境,因此我们提出一种混合启发式方法以求取最优解。
所提方法
我们定义了一种表示方案,将调度序列与资源模式选择解耦。在汽车BIW焊装岛中,调度涉及满足优先约束的任务处理顺序以及模式选择,例如自动化模式与人工协作模式,以平衡循环时间和人时成本。为此,我们构建任务序列向量Vseq,表示拓扑优先级的排列,即任务索引的排列{j1, j2, …, jn}。若任务ja在Vseq中出现在jb之前,则解码器尝试优先调度ja。模式分配向量Vmode中,第i个元素Vmode[i]∈Mi对应任务i所选的执行模式。例如,Vmode[i]=1表示任务i以加速协作模式执行。该多模式资源约束调度问题的搜索空间由上述双向量定义,可独立或协同调整优先级和资源配置。
解码过程按Vseq定义的顺序遍历任务。对于每个任务i,根据Vmode[i]中的值检索持续时间dim和资源消耗cimr。最早开始时间ESi计算为所有前驱任务完成时间的最大值与所选可再生资源最早可用时间的较大者。
由于BIW焊装岛的刚性拓扑和预算约束,随机初始化会产生不可行序列。初始时,候选列表填充没有未解决前驱任务的任务,从列表中随机选择一个任务并附加到序列向量中,此迭代选择持续进行直到所有任务被调度。为满足预算限制,模式向量初始设置为基线状态,即所有任务分配至标准自动化模式,该模式消耗零额外人时。随后,随机贪心算子迭代选择符合条件的任务并将其更新为协作加速模式。此升级过程在累计不可再生资源消耗达到预定义预算边界时停止。
为生成初始任务序列向量Vseq,我们采用基于拓扑的构造启发式方法。设Rset为可用任务集合,Rset = {j∈J | dj = 0},其中入度dj表示未调度前驱任务的数量。每一步中,从Rset中随机选择一个任务i并附加到Vseq中。任务i调度后,其后继任务的入度减一。同时,模式分配向量Vmode通过为每个任务随机选择一个有效执行模式m∈Mj进行初始化。
标准模拟退火搜索过程可能收敛至安全解,或陷入不可行区域。为导航受约束的解空间,我们提出三阶段自适应模拟退火(TS-ASA)算法。结合自适应策略,SA已被证明是近年来解决资源调度问题的有效方法。解X的目标值E(X)定义为制造跨度加上对预算违规的动态惩罚。算法结构分为三个自适应阶段,以平衡模式空间探索与序列空间开发,分别为动态邻域算子(DNO)、自适应冷却调度(ACS)和重启机制(RM)。表S1展示了三阶段自适应模拟退火算法的伪代码。
在标准调度问题研究中,动态邻域算子主要关注任务序列交换,但在本场景中,我们引入DNO在早期阶段采用序列-模式策略,后期阶段聚焦序列调整。搜索进度ρ = k/Kmax,其中Kmax为最大迭代次数,k为当前迭代次数。我们定义模式变异概率πmode(ρ),控制对Vmode的模式翻转操作和对Vseq的序列移位操作。该概率随搜索进行而衰减,将焦点从结构探索转向拓扑开发:
πmode(ρ) = πhigh,若ρ < ρexpl
πmode(ρ) = πlow,若ρ ≥ ρexpl
其中ρexpl为探索阶段阈值。在早期阶段(ρ < 0.3),设置πhigh = 0.7以积极探索不同的资源成本配置,例如在自动化模式和协作模式之间切换。在后期阶段,πlow降至0.05以固定资源分配并专注于优化任务序列。
模拟退火算法对冷却时间高度敏感,传统冷却率适应性较差,通常依赖基于迭代阈值或目标停滞的衰减。考虑到人时约束,我们提出一种感知的自适应冷却调度(ACS),ACS根据在检查间隔Lcheck上计算的接受率racc来调节冷却率αk:
racc = (1/Lcheck) × ∑(ki=k?Lcheck到k) I(Acceptedi)
其中I(·)为指示函数,若移动被接受则等于1,否则等于0。温度更新规则旨在维持种群多样性:
Tk+1 = Tk·αfast,若racc > rhigh
Tk+1 = Tk·αslow,若racc < rlow
Tk+1 = Tk·αbase,其他情况
其中Lcheck = 50,rhigh = 0.4,rlow = 0.1。冷却率αfast = 0.90,αslow = 0.99,αbase = 0.98。所提ACS通过监控实时接受率来调节温度,使算法能够在不违反预算约束的情况下持续探索成本-时间的帕累托前沿。
传统重启机制完全随机化状态以逃离局部最优。为解决预算被非关键任务锁定导致的资源死锁问题,我们引入RM算子来监控滑动窗口W内目标值的标准差σW,计算如下:
σW = √(1/|W| × ∑(v∈W)(v ? μW)2)
其中v表示窗口内的适应度值,μW为均值。若σW < ε且迭代计数在安全范围内k < 0.75Kmax,则触发重启。与随机重置不同,重启操作保留最佳历史解Xbest但施加高强度扰动,随后进行温度重新加热:
Tnew = F(Xbest)·τ
其中τ = 0.2为重新加热因子。该机制保留关键路径的序列同时实现随机重新分配,有效平衡了收敛速度和全局搜索能力。
由于不可再生的 人时 预算Cr,搜索过程中的中间解可能违反预算边界。为在不丢弃近似可行解的前提下促进边界探索,针对解X制定基于惩罚的适应度函数F(X):
F(X) = Cmax(X) + Ω·max(0, ∑(i∈V) cim·yim ? Cr)
其中Cmax(X)为通过前向解码计算的制造跨度,Ω为足够大的惩罚系数以惩罚预算超额。
DNO在扰动任务排列的同时保持几何优先约束。它通过权重偏置提取和边界插入机制运作,使用轮盘赌机制选择一个任务进行扰动,然后执行可行窗口计算,随后选择任务并随机插入到新的有效位置。ACS算子和RM算子扰动执行模式以探索成本-时间权衡,使算法能够在资源边界上获得良好解。
量化与统计分析
本研究报道的所有定量结果均源自计算调度实验和工业案例模拟。所有统计和定量细节均已报告。
主要性能指标为制造跨度,记为Cmax,单位为秒。次要指标包括平均资源成本、最佳相对误差、平均相对误差、最差相对误差、标准差、收敛行为、平均计算时间和最优性差距。对于J20 MRCPSP基准实验,随机选择10组基准实例,每组实例运行30次;此处n表示每个基准条件下独立随机算法运行次数。对于工业BIW案例,调度实例包含n=43个任务;此处n表示调度任务数而非生物或临床重复样本。在消融实验中,每个算法变体运行n=100次,最大迭代1,000次;n表示独立随机优化运行次数。在TS-ASA、GA、DPSO和EDA之间的比较中,每个算法在共同的受约束搜索空间下评估n=30次独立运行。对于精确求解器比较,10个独立选择的MMLIB J20实例与Gurobi及官方最优值进行评估;此处n表示基准问题实例数。
随机化仅用于计算实验设计和随机优化过程,包括基准实例的随机选择、基于拓扑的随机初始化、随机贪心模式分配、轮盘赌扰动以及模拟退火中的随机接受。基准实例数量和重复运行次数的选择旨在评估随机调度算法的解质量、鲁棒性和计算效率。
所有算法均使用Python 3.9实现和执行。精确求解器比较中,J20基准验证使用Gurobi Optimizer 12.0.3。
补充信息 (1)
PDF (375.97 KB)
文档S1。表S1–S4和数据S1