基于真实吐露贪婪机制的多Agent单机调度问题

Multi-Agent single machine scheduling based on truthful greedy mechanism

在分布式环境下,从组合拍卖的角度出发研究了多Agent的单机调度问题,设计了一种贪婪机制.该贪婪机制包括贪婪分配算法和贪婪支付算法两部分,首先贪婪分配算法以资源Agent收益最大为目标解决组合拍卖中的竞胜标问题,然后贪婪支付算法以第二价格支付的形式确定中标者应该支付的最小费用.本文证明了该贪婪机制的真实吐露性,并通过算例说明设计机制的可行性与有效性.最后进行仿真实验比较该贪婪机制与线性规划方法的求解效果,结果袁明,对大规模问题,该机制能够快速得到使系统总收益近似最优的调度方案.

This paper proposes a greedy mechanism based on combinatorial auction to solve the distributed multi-Agent scheduling problem.The greedy mechanism includes a greedy allocation algorithm and a greedy payment algorithm,where the former solves the winner determining problem with the goal of maximizing the revenues of source Agent and the latter determines the minimum fees that winners should pay in the form of second price payments.It is proved that the mechanism is truthful,and a series of numerical examples are used to illustrate the feasibility and validity of the greedy mechanism.Furthermore,a simulation experiment is done to compare the effectiveness of the greedy mechanism and the linear programming method.The result shows that the greedy mechanism can solve large-scale scheduling problems with less computational time while achieving near optimal revenues for the system.