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

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

网络排序问题考虑如何对分散的任务合理地分配资源以实现资源的最优配置，如何高效地求解网络排序问题是很多工业生产企业以及物流运输企业的迫切需要，也是当前组合最优化研究的前沿领域。本项目对一些有挑战性和代表性的网络排序问题进行研究，得到了一些高性能的优化算法，主要是近似算法和在线算法。研究线形网络上带有正则目标函数的车辆路径问题，证明了通常的Min-max问题是多项式时间可解的，而Min-sum问题是NP困难但是伪多项式时间可解的，而相应的多机问题能够归结为解O(n)或O(n^2)个单机问题，因此也是多项式时间或伪多项式时间可解的。研究树形和环形网络上工件有就绪时间和服务时间约束的单车辆调度问题，就车辆需要返回出发点的情形设计了性能比为9/5和12/7的近似算法，就车辆不需要返回出发点的情形设计了性能比为27/14和12/7的近似算法。研究在线QTSP（Quota Traveling Salesman Problem），针对网络结构为对称与非对称，为半直线、直线或任意，旅行商是否需要返回出发点等不同情形，都给出了最优的下界和算法，从而比较系统、完整地解决了这个问题。得到了半直线上在线不返回TSP的下界2，从而证明了Bonifaci提出的竞争比为2的算法是最优的。研究CTSP（Clustered Traveling Salesman Problem），就进入和离开每个群的节点不指定的情形设计了性能比为13/6的近似算法。研究图的圈覆盖问题的几种变形：MMCCP（Min-Max Cycle Cover Problem），RMMCCP（Rooted Min-Max Cycle Cover Problem）和MCCP（Minimum Cycle Cover Problem），就这些问题得到了在性能比和复杂性方面较现有算法皆有改进的近似算法。研究有机器合法性约束的平行机在线排序问题，就工件实时到达，有嵌套、层次（或服务等级）、树形合法性约束的多种情形设计了最优算法。研究工件列表到达、有服务等级约束的同类机半在线排序问题，就两台机器，已知最优值、工件总尺寸或最大尺寸、尺寸上下界等情形，给出了最优算法；就m台同类机在线可分问题，给出了机器有2或3个服务等级时的最优算法。