在线排序问题的算法设计与竞争比分析

在线排序问题是考虑对在线到达的任务如何合理安排，使得资源达到最优配置，它是组合最优化的前沿研究领域，有许多富有挑战性的待解决问题，本项目旨在选择其中一些富有挑战性的问题进行研究，重点研究在线平行机排序、在线作业排序、在线批处理排序、在线随机排序、在线多代理排序和在线路线排序问题，设计这些问题的最优或高效的在线算法，解决一些难点问题。同时，在研究实践中，发展并提出新的研究方法，探索和研究实例转换法、等待策略法、平移法和贪婪区间法等新方法的普遍适用性，这些新方法的发展和完善在排序理论研究和实践上都具有重要意义。本项目属于运筹学、管理科学和理论计算机科学的交叉研究领域，属于问题驱动的应用基础研究，不仅有很强的应用背景，而且有相当的研究难度，其研究进展不仅能丰富排序理论与应用的内容，而且会促进相关领域，甚至是组合最优化理论的发展，对推动交叉学科的研究也十分有意义。

本项目对在线批处理排序、在线作业排序、在线平行机排序、在线随机排序、在线多代理排序问题、在线路线问题及排序反问题进行了较为深入系统研究，对这些问题设计了较为高效或者最优的算法，分析了算法的竞争比或者性能比。特别是对目标为极小化加工总长的平行批处理机在线排序问题和两台机器流水作业在线排序问题的研究，得到了最好的具有创新性的研究成果；对多代理排序问题的近似算法的设计与性能分析，拓广了多代理排序的研究内容；关于在线dial-a-ride问题，主要是基于实际问题的理论与应用研究，既得到了一些有价值的理论结果，也解决了实际问题。本项目基本完成了项目的预期目标，取得了一些有突破的研究成果，在国内外学术刊物上发表论文16篇，其中SCI学术期刊论文11篇。同时在项目的支持下，培养了博士毕业生3名，硕士毕业生6名。