分散决策模式下的排序问题研究

Scheduling is one of the most active branches in operations research and combinatorial optimization, among which scheduling in a decentralized decision-making mode 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 characterized by extremely high spontaneity and lack of authority, ranging from network economy to information communication, etc, which gives rise to new requirement for scheduling research. The project will extensively study several new scheduling models and problems in a decentralized setting, mainly focus on algorithm design and worst-case analysis. To make more concrete, design and analysis of local scheduling policies, performance evaluation and efficiency analysis for scheduling regarding self-interest behavior and semi-decentralized decision-making situations are included. Moving forward, we will also cover some scheduling problems in real application involving competition and cooperation.

排序是运筹学组合最优化领域中研究最为活跃的分支之一，分散决策模式下的排序问题是近年来受到广泛重视的排序新课题。它与经典排序的主要区别是工件可自由选择加工机器，而非由某个决策者统一安排。这一变化反映了网络经济和信息通讯等排序新应用领域高度自发性和利益多样化等新特征对排序研究的客观要求。本项目将深入研究若干分散决策排序新模型和新问题，核心内容是算法设计和最坏情况分析。具体包括局部排序规则的设计与分析，半分散决策模式问题，以及以工件为主体的排序性能分析等。我们还将研究应用领域一些涉及竞争和合作的具体排序问题。这些问题国际上的研究刚刚起步或起步不久，有较大难度，本项目将对它们进行前瞻性研究，获得创新性成果。

排序是运筹学组合最优化领域中研究最为活跃的分支之一，分散决策模式下的排序问题是近年来受到广泛重视的排序新课题。它与经典排序的主要区别是工件可自由选择加工机器，而非由某个决策者统一安排。这一变化反映了网络经济和信息通讯等排序新应用领域高度自发性和利益多样化等新特征对排序研究的客观要求。本项目深入研究了若干分散决策排序新模型和新问题，核心内容是算法设计和最坏情况分析。主要成果包括：给出了不同类机SPT局部规则以极小化makespan为目标的问题的最坏情况界的下界，并证明了其在一定意义下的最优性；研究了以每台机器总完工时间最大值为社会费用的排序问题，给出了SPT算法的最坏情况界和改进算法；给出了SPT算法求解以总完工时间为目标函数的带机器维护时段平行机排序问题的最坏情况界，当两台机器均有维护时段且维护时段不重叠时SPT是最好可能的多项式时间近似算法；给出了同型机以极小化makespan和极大化机器最小负载为社会费用的排序博弈PoA以工件最大加工时间与最小加工时间比值为参数的参数紧界；对带机器激活费用的排序博弈问题的Nash均衡有效性进行了分析，给出了PoA和PoS的参数上界和下界；讨论了双社会费用问题算法性能的评价指标等。