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

项目名称： 分散决策模式下的排序问题研究

项目编号： No.11271324

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 谈之奕

作者单位： 浙江大学

项目金额： 60万元

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

中文关键词： 排序；算法设计与分析；最坏情况界；；

英文摘要： 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.

英文关键词： Scheduling；Design and analysis of algorithms；Worst-case ratio；；