An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival
An Auction-Based Approach for Multi-Agent Uniform Parallel Machine Scheduling with Dynamic Jobs Arrival
复制标题
DOI：
10.1016/j.eng.2023.09.024
复制
发表时间：
2024-06-08
期刊：
影响因子：
12.8
通讯作者：
Wang，Lihui
中科院分区：
文献类型：
--
作者：
Liu，Yaqiong;Sun，Shudong;Wang，Lihui
研究了一类多Agent调度问题，其中资源Agent拥有均匀的并行机，而竞争的工件具有动态的到达时间，属于不同的消费者Agent。所有的代理人都是自利的和理性的，目的是最大化自己的目标，导致激烈的资源竞争的消费者代理人和不愿意透露私人信息的战略行为。在这种情况下，集中式调度方法是不可行的，分散的方法被认为是处理的目标问题。本研究的目的是产生一个稳定的和合作的解决方案，具有高社会福利，同时适应消费者代理人的偏好下不完全信息。为此，开发了一种基于分散决策过程的动态迭代拍卖方法。在该方法中，建立了一个动态拍卖过程中的动态工件参与实时拍卖，并提出了一个简单的和易于实现的无价格的投标策略，以减少投标确定的复杂性。此外，一个自适应匈牙利算法被应用到解决的赢家确定问题有效。理论分析证明了所提出的方法是个体理性的，短视投标策略是消费者代理投标的弱优势策略。大量的计算实验表明，所开发的方法实现了高质量的解决方案，并表现出相当大的稳定性与众多的消费者代理和工作的大规模问题。在未来的工作中，将进一步研究考虑多个资源代理的多代理调度问题。
This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents. All agents are self-interested and rational with the aim of maximizing their own objectives, resulting in intense resource competition among consumer agents and strategic behaviors of unwillingness to disclose private information. Within the context, a centralized scheduling approach is unfeasible, and a decentralized approach is considered to deal with the targeted problem. This study aims to generate a stable and collaborative solution with high social welfare while simultaneously accommodating consumer agents’ preferences under incomplete information. For this purpose, a dynamic iterative auction-based approach based on a decentralized decision-making procedure is developed. In the proposed approach, a dynamic auction procedure is established for dynamic jobs participating in a real-time auction, and a straightforward and easy-to-implement bidding strategy without price is presented to reduce the complexity of bid determination. In addition, an adaptive Hungarian algorithm is applied to solve the winner determination problem efficiently. A theoretical analysis is conducted to prove that the proposed approach is individually rational and that the myopic bidding strategy is a weakly dominant strategy for consumer agents submitting bids. Extensive computational experiments demonstrate that the developed approach achieves high-quality solutions and exhibits considerable stability on large-scale problems with numerous consumer agents and jobs. A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.