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

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

作　　者：Yaqiong Liu Shudong Sun Gaopan Shen Xi Vincent Wang Magnus Wiktorsson Lihui Wang 

机构地区：[1]Department of Industrial Engineering,Northwestern Polytechnical University,Xi’an 710072,China [2]Key Laboratory of Industrial Engineering and Intelligent Manufacturing,Ministry of Industry and Information Technology,Xi’an 710072,China [3]Department of Production Engineering,KTH Royal Institute of Technology,Stockholm 10044,Sweden

出　　处：《Engineering》2024年第4期32-45,共14页工程（英文）

基　　金：supported by the National Natural Science Foundation of China(51975482);the China Scholarship Council.

摘　　要：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 realtime 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 largescale problems with numerous consumer agents and jobs.A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.

关 键 词：Multi-agent scheduling Decentralized scheduling AUCTION Dynamic jobs Private information 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]