排序若干新问题的算法设计与分析

排序理论是运筹学组合最优化领域中研究最为活跃的分支之一。本项目将深入研究来源于生产计划调度，物流和供应链管理等实践中的几类排序新问题，例如，带不精确信息的半在线排序，有一个或多个参数的半在线排序，多阶段集成排序问题，复杂机器环境下的排序问题等等，每一类问题都包含了丰富的排序模型。对其中的离线情形，本项目将探讨它们的计算复杂性、（完全）多项式时间近似方案的存在性或难近似性，以及快速近似算法的设计；对其中的在线、半在线情形，本项目将探讨如何设计具有最好可能竞争比的算法，这些都是组合最优化问题的核心研究内容。对上述几类排序新问题，国际上的研究刚刚起步或起步不久，有较大难度。本项目将对它们进行前瞻性研究，获得创新性成果。