最大加权完工时间排序博弈问题的协调机制

摘要

研究以最小化最大加权完工时间为目标的排序博弈问题的协调机制.相应的排序博弈模型中,有m台平行机和行个工件,工件j的加工时间为pj,权重为wj.每个工件可自主选择机器进行加工,它的目标是最小化自身的完工时间,全局的目标是最小化最大加权完工时间.本文针对该问题设计协调机制,证明该机制的纳什均衡存在且唯一,并证明该机制的无秩序代价为2-1/m.