平行机排序博弈的均衡分析与机制设计

Scheduling is one of the most active branches in operations research and combinatorial optimization, among which scheduling game is a brand new topic attracting wide attention and lively interest in current decades. Distinguished from classical scheduling with a central decision maker, jobs have a privilege to choose the machine to be processed. The change is motivated by the application of scheduling in diverse new fields ranging from network economy to information communication, etc, which gives rise to new requirement for scheduling research. The project will extensively study several new models and problems in scheduling game, mainly focus on equilibrium analysis and mechanism design. To make more concrete, inefficiency analysis of Strong Equilibrium and mixed Nash Equilibrium, study on new models with digopolistic player or job migration costs, analysis on the upper and lower bounds in the Price of Anarchy of classical coordinate mechanism, mechanism design for scheduling game with batch machines or time-dependent jobs are included. Moving forward, we will also cover cake cutting and related problems.

排序是运筹学组合最优化领域中研究最为活跃的分支之一，排序博弈是近年来受到广泛重视的排序新课题。它与经典排序的主要区别是工件可自由选择加工机器，而非由某个决策者统一安排。这一变化反映了科技社会发展对排序研究提出的新要求。本项目将深入研究若干排序博弈新模型和未解决问题，核心内容是均衡分析与机制设计。具体包括强Nash均衡和混合策略Nash均衡的有效性分析；序贯排序博弈和有垄断型参与者的排序博弈等新模型的研究；典型协调机制的性能分析与机制有效性下界研究；批排序博弈与工件加工时间可变排序博弈的机制设计，以及与排序博弈相关的一般资源分配问题。这些问题国际上的研究刚刚起步或起步不久，有较大难度，本项目将对它们进行前瞻性研究，获得创新性成果。

排序是运筹学组合最优化领域中研究最为活跃的分支之一，排序博弈是近年来受到广泛重视的排序新课题。它与经典排序的主要区别是工件可自由选择加工机器，而非由某个决策者统一安排。这一变化反映了科技社会发展对排序研究提出的新要求。本项目主要研究若干排序博弈新模型和未解决问题，核心内容是均衡分析与机制设计。我们提出了工件有级别的排序博弈问题，讨论了不同机制下Nash均衡的存在性，给出了SPT、LPT、Makespan和Random等规则下博弈Price of Anarchy（PoA）的上界和下界；对机器可增减排序博弈问题，研究了LPT，SPT，Makespan等三种确定性机制和随机机制Random下均衡的无效率性；对工件加工时间可变的排序博弈，提出了三种协调机制，针对两种社会费用给出了PoA和Price of Stability（PoS）的估计；讨论了有等级平行机的混合协调机制。研究了两台同类机已知工件总加工时间半在线排序问题，对机器速度比部分取值下的问题下界和竞争比作出了改进；研究了工件有不同大小，但有相同加工时间，以工件总完工时间为目标函数的单机和平行机批排序问题；对两台同型机，工件有不同加工时间和大小，工件完工后需用一辆容量有限的车辆运送给顾客，目标为极小化工件送达顾客的最大时间的排序问题，给出了渐近最好可能多项式时间算法。