来源:Engineering 发布时间:2025/7/22 10:48:08
选择字号:
智能制造新方案:动态拍卖算法破解多代理调度难题 Engineering

论文标题:An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival

期刊:Engineering

DOI:https://doi.org/10.1016/j.eng.2023.09.024

微信链接:点击此处阅读微信文章

加拿大工程院院士、瑞典皇家理工学院教授王力翚团队与西北工业大学工业工程与智能制造工信部重点实验室团队合作在动态多代理制造调度领域开展深入研究,相关成果以“An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival”为题发表于《Engineering》,刘亚琼为第一作者。该研究提出的分布式动态迭代拍卖方法(DIA),为解决复杂制造环境下多主体资源竞争与动态工件调度问题提供了新方案。

在当今客户需求个性化、生产系统复杂化的趋势下,多代理并行机调度成为智能制造的关键问题。传统集中式调度方法依赖全局信息,难以满足代理自利性带来的私有信息保护需求,也无法适应工件动态到达的实时性挑战。像云计算资源分配、电动车充电站调度等场景中,多个利益主体竞争有限资源,且工件到达时间和加工需求不确定,对调度算法的分布式决策、动态适应和隐私保护能力提出了更高要求。论文聚焦的 “动态工件到达的多代理同类并行机调度问题(MUPMSP-D)”,面临代理自利性与信息不对称、动态性与实时性、计算复杂度高等难题。

针对这些挑战,研究团队提出了一种分布式动态迭代拍卖方法,以生成具有高社会福利的、稳定的、协同调度方案。方法主要包括动态拍卖程序、投标决策、定标决策和投标更新策略四个部分。在方法的每个阶段,代理的私有信息都得到了保护。其中,动态拍卖程序确保工件在到达之后即可参与拍卖;投标决策和更新中的无价格属性投标策略,克服了在拍卖中对不断增加的工件进行投标的挑战,显著降低了计算成本;在定标决策阶段,研究团队提出了一种自适应匈牙利算法高效对WDP进行高效求解。通过理论分析,证明了该法的两个特性:个体理性以及短视策略是竞标者投标的弱占优策略。

为验证 DIA 的有效性,研究团队在2240个算例上进行了四种实验。结果表明,所提方法能够生成高质量的解决方案,特别是在大规模问题上表现出良好的稳定性。对于具有更多客户代理和工件的问题,方法需要更多的迭代拍卖轮次来生成具有高社会福利的解决方案。

文章指出,尽管提出的DIA方法具有上述优势,但该方法也存在一些不足。求解定标决策问题的算法2的时间复杂度为 O(J³)。当工件总数J足够大时,方法会产生一定的计算成本。此外,文章尚未对所提方法在实际企业中的应用进行验证。

文章表示,未来将进一步以拍卖方法为基础理论,研究多代理调度方法的实际应用。比如,在实际中,往往存在多个客户代理和多个资源代理。针对此问题,计划提出一种基于双边拍卖理论的多对多谈判过程。同时考虑与多个资源代理相关的距离和物流成本。问题难度的增加使得投标决策和定标决策的复杂性大大增加。因此,需要进一步优化相关决策算法,同时降低算法时间复杂度。

文章信息:

An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival

基于拍卖理论的动态多代理同类机调度算法

作者:

刘亚琼, 孙树栋, 申高攀, Xi Vincent Wang, Magnus Wiktorsson, Lihui Wang*

引用:

Yaqiong Liu, Shudong Sun, Gaopan Shen, Xi Vincent Wang, Magnus Wiktorsson, Lihui Wang. An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival. Engineering, 2024, 35(4): 32–45

开放获取论文:

https://doi.org/10.1016/j.eng.2023.09.024

更多内容

钱锋院士:智能流程制造助力双碳目标——实现碳达峰和碳中和目标的流程制造数字化转型

李培根、李新宇、高亮等:智能制造

芯片电路设计新进展:布局优化精确算法助力成本降低

Engineering最新影响因子11.6

Engineering征稿启事:人工智能赋能工程科技

 
 
 
特别声明:本文转载仅仅是出于传播信息的需要,并不意味着代表本网站观点或证实其内容的真实性;如其他媒体、网站或个人从本网站转载使用,须保留本网站注明的“来源”,并自负版权等法律责任;作者如果不希望被转载或者联系转载稿费等事宜,请与我们接洽。
 
 打印  发E-mail给: 
    
 
相关新闻 相关论文

图片新闻
中国学者研究入选联合国可持续发展案例 人工智能在黄石公园下发现8.6万次地震
研究发现调控甜瓜成熟的两个关键转录因子 月壤取水 可产燃料
>>更多
 
一周新闻排行
 
编辑部推荐博文