网络排序问题的高性能优化算法研究

项目名称： 网络排序问题的高性能优化算法研究

项目编号： No.11171106

项目类型： 面上项目

立项/批准年度： 2012

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

项目作者： 刘朝晖

作者单位： 华东理工大学

项目金额： 45万元

中文摘要： 网络排序问题考虑如何对分散的任务合理地分配资源以实现资源的最优配置，如何高效地求解网络排序问题是很多工业生产企业以及物流运输企业的迫切需要，也是当前组合最优化研究的前沿领域。本项目瞄准网络排序中的一些有代表性的富有挑战性的问题进行研究，为它们设计高效的优化算法，主要是近似算法和在线算法，这些算法可以直接应用于工业生产和物流运输路线规划，也可以与现有的算法结合起来使用，从而提高相应部门的运行效益。本项目是一项跨数学、运筹学和理论计算机科学的交叉项目，在研究中将运用和发展近年来在这些学科中出现的新技术和新方法，如随机化方法、连续化方法、PCP理论等，这些新技术、新方法的应用和发展不仅对于排序问题的研究是有意义的，而且对于推动组合最优化这门新兴的交叉学科的发展也是有意义的。

中文关键词： 排序；网络排序；旅行商问题；近似算法；在线算法

英文摘要：

英文关键词： scheduling；routing scheduling；traveling salesman problem；approximation algorithm；online algorithm