新型计算环境下的排序问题

项目名称： 新型计算环境下的排序问题

项目编号： No.11271325

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 张国川

作者单位： 浙江大学

项目金额： 50万元

中文摘要： 排序问题是组合优化领域的一个非常活跃的分支。近年来新的计算环境为排序提出了重要挑战。绿色计算、多核计算、云计算和服务计算中出现了大量的排序模型，包括能耗有效的排序问题、带加速资源的排序问题、路由排序问题和博弈环境下的排序算法机制设计问题。在这些模型中排序起着至关重要的作用。本项目立足于这种非传统计算环境下的排序问题，研究额外约束对排序效能的影响，刻画最优解结构的变化，拓展算法手段，挖掘新的算法思想。特别地，我们将关注能耗与排序目标的依赖关系；考察加速资源下离线和在线算法的设计与分析；突破带到达时间的网络路由排序的平凡上界； 讨论博弈环境下机器的排序机制和机器/工件共同博弈的纳什均衡存在性和效率分析。争取重要算法成果。

中文关键词： 近似算法；在线算法；指数时间假设；有效多项式近似方案；排序

英文摘要： Scheduling is a very active area in combinatorial optimization.There have been quite a lot of challenging scheduling problems in the new computing environments recently. Many of them arise in green computing, multi-core computing, cloud computing as well as service computing, including energy-efficient scheduling problems, scheduling with renewable speed-up resources, routing scheduling problems and mechanism design for scheduling. Scheduling is a key issue in such models. This proposal is thus motivated by these scheduling problems from non-classical computing enviornments. We aim at the impact on scheduling issues with additional constraints, providing a complete picture on the optimal structure, generalizing the algorithmic tools, and designing new scheduling ideas. In particular, we pay attention to the relationship betwwen energy consuming and scheduling goals, investigate design and analysis of offline and online algorithms with speed-up resources, beat the trival upper bound for routing scheduling with release times, discuss the existence of a Nash equilbrium and analyze the system efficiency for the scheduling game where both machines and jobs are players. It is greatly expected to achieve significant algorithmic results.

英文关键词： approximation algorithms；online algorithms；ETH；EPTAS；scheduling