两台平行机排序博弈问题的协调机制

Coordination Mechanism of Two Parallel Machines Scheduling Game Problem

排序理论是组合最优化理论的重要组成部分,如果在排序过程中有一个系统管理员来安排相应任务,那么往往会得到比较理想的解。但是,随着互联网的发展,在许多排序过程中由系统管理员来强加控制是不可行的,因为互联网的用户具有独立性和自利性,他们"自私"地追求自身的利益最优,而不在乎是否造成社会资源的浪费。若没有合理的资源使用机制,这种自利性往往会使结果与理论最优值偏差巨大。因此设计合理的机制以影响、引导独立和"自私"的用户的选择从而减少社会资源的浪费将具有重大的理论意义。本文针对如下排序博弈模型:具有2台平行机,工件是局中人,工件的策略是对机器的选择,工件的目标是最小化它的完工时间,全局目标是最小化最大完工时间,探讨SPT-LPT机制(SPT-LPT机制是指一台机器按工件加工时间的不减顺序排序,另一台机器按工件加工时间的不增顺序排序),首先研究了SPT-LPT机制下相应排序博弈问题的纳什均衡解的情况,其次证明了当工件数不小于4时,SPT-LPT机制下的无秩序代价为4/3。

Scheduling theory is an important part of the theory of combinatorial optimization. If there is a system administrator to arrange tasks in scheduling processing, it may get an ideal solution. However, with the development of the Internet, many scheduling process imposed by the system administrator to control is not feasible. It is because the systems consist of many independence self-interest agents who ＂ selfishly＂ pursue their own optimal and do not care about the waste of social resources. If there is no reasonable mechanism for the use of resources, the self-interest may lead to large deviation between the results and the theoretical optimal value. Designing a reasonable mechanism to influence and guide the independent and selfish agents to decvease the waste of social resources will be of great theoretical significance. We considered the following scheduling game problem. There were two parallel machines and n jobs. Each job was a player and its strategy set was of the two machines. The objective of an agent was to minimize its own completion time. The global objective was to minimize the maximum completion time of the jobs. SPT-LPT mechanism was a coordination mechanism that one of the machines schedules the jobs that choose to be processed on it in the order of increasing processing time, and the other schedules the jobs that choose to be processed on it in the order of decreasing processing time. We first analized the Nash E- quilibrium solutions of the SPT -LPT mechanism and then showed that the price of anarchy of SPT-LPT mechanism was 4/3 when there were at least 4 jobs.