多阶段集成排序和退化机器环境下排序的理论研究

排序论是运筹学和组合最优化领域最为活跃的研究分支之一，而多阶段集成排序和退化机器环境下排序是来源于工业生产、作业调度、物流和供应链管理等实践中的两类新兴排序问题，而每一类问题都包含了丰富的排序模型，例如，协同考虑工件加工、储存和运输的集成排序，机器带有不可行区间的排序，平行批处理机批容量随时间变化的排序等等。对于离线排序问题，进行计算复杂性研究，和NP-困难问题的近似算法，包括（完全）多项式时间近似方案的存在性或难近似性研究，以及对在线排序问题，设计具有良好竞争比的在线算法等等，这些都是排序论目前的核心研究内容。本项目以探讨多阶段集成排序和退化机器环境下排序问题的计算复杂性、多项式近似方案的存在性或难近似性、以及在线算法为主要研究内容。通过分析可行排序和最优排序的局部和整体结构性质，在计算复杂性分析，近似算法和在线算法的设计等方面做出一些创新性的研究成果。

多阶段集成排序，复杂机器环境下的排序和多代理排序等是在工业生产、作业调度、物流和供应链管理等实践中，有所遇到的种种问题的推动下而提出来的几类新型排序模型。本项目针对这几类新型排序模型中的两代理排序，集成工件加工和投送排序，机器带有不可行区间排序和工件加工时间变化的排序等依次展开研究。首先，我们系统的研究了批处理机环境下的两代理排序，对于不同的指标函数或者给出多项式时间算法，或者说明其难解性，即给出NP-难证明；其次，对于机器有维修区间，极小化加权总完工时间的一台批处理机器排序，给出了一般NP-难的证明。关于带有相同维修区间的平行机在线排序，目标函数是极小化最大工件完工时间，区别讨论了维修区间长度和最大工件加工时间关系情形，分别给出了具有竞争力的在线算法；然后，我们研究了工件加工时间随开始加工时间等比例增大的排序问题，极小化总的加权完工时间，当机器有两个不可行区间时，该问题没有近似比为常数的多项式时间算法，对于只有一个维修区间的情形，给出了一个FPTAS算法；最后，我们考虑了工件加工完毕需要投送的单机排序问题，目标是极小化车辆完成运输的时间，分析了该问题的计算复杂性，同时构造了一个3/2近似算法。除此之外，我们还研究了其他一些类型的排序，例如，对于经典单机误工排序问题，我们纠正了KIM算法最优性的证明；考虑了工件就绪时间是离散可压缩的排序问题，这里工件需要支付一定的费用才可以使其就绪时间压缩。