Abstract: To solve the distributed single machine scheduling problem, a multi-agent scheduling mechanism based on iterative price combinatorial auction was designed. In this mechanism, the constraint based language was employed to build an improved winner determination model by combining the general form of combinatorial auction with the modeling technology of machine scheduling. The global objectives of this model included system revenue and machine utilization. While failing in the current round, a bidder could increase the bidding price or relax the temporal constraints to remain in the next round of the auction. Experimental results showed that the proposed scheduling scheme outperformed the traditional combinatorial auction-based mechanism by effectively enhancing the machine utilization level without reducing the system revenue.

Key words: scheduling, multi Agent, combinatorial auction, distributed scheduling

摘要： 为解决分布式单机调度问题，设计了一种基于重复叫价组合拍卖的多主体调度机制。该机制采用基于约束的投标语言，将组合拍卖的一般形式与机器调度的建模技术相结合，建立了改进的竞胜标模型，该模型的全局目标同时兼顾了系统收益与机器利用率；在投标策略上，当前回合中未中标的投标者可以采用提高出价或放宽对时间需求的约束来参与下一回合的竞标。对该机制进行仿真实验的结果表明，与传统的单独采用组合拍卖解决机器调度问题的方法相比，该机制得到的调度方案在保证系统收益的前提下，提高了机器利用率。

关键词: 调度, 多主体, 组合拍卖, 分布式调度