在线和离线折衷排序研究

Trade-off scheduling is an important research direction in scheduling theory, which received new development in recent years. For multiple criteria of scheduling, in the discrete version, trade-off scheduling asks to find all Pareto optimal points, and in the continuous version, trade-off scheduling asks to find the trade-off curve. This project studies the online and off-line trade-off scheduling under multi-criteria, which includes the classical trade-off scheduling, multi-agent trade-off scheduling and trade-off rescheduling. The goal of the project is to develop efficient polynomial-time algorithms, approximation algorithms and online algorithms, based on totally new theoretical tools. For the off-line version, we present complexity analysis, and design polynomial-time algorithms and polynomial-time approximation algorithms to generating all Pareto optimal points or trade-off curves. For the online version, based on the analysis for the interrelationships between the time potentials and the optimization criteria, we design online algorithms with good trade-off competitive ratios. In the aspect of the expression of the achievements，we will provide complete research results for off-line trade-off scheduling and establish fundamental theoretical framework for online trade-off scheduling.

折衷排序是排序领域的重要研究方向，近年来又有新的发展。针对多个排序指标，在离散情形，折衷排序要求刻画所有Pareto最优点，而在连续的情形，折衷排序要求刻画trade-off曲线。本项目研究多指标下的在线和离线折衷排序，包括经典折衷排序、多代理折衷排序以及折衷重新排序。目的是在全新的理论工具的基础上寻求有效的多项式时间算法、近似算法和在线算法。对离线情形进行复杂性分析、并设计多项式时间算法及多项式时间近似算法生成问题的所有Pareto最优点或trade-off 曲线。对在线情形在分析时间位势与优化指标之间的内在联系的基础上设计具有良好trade-off竞争比的在线算法。在成果表现方面，对离线折衷排序给出完整的研究结果，并对在线折衷排序建立基本的理论构架。

折衷排序是排序领域的重要研究方向，发展新的研究方法并用来求解各种具有理论意义和应用前景的多指标排序模型是本项目的实施要点。本项目对折衷排序进行了深入的研究，得到了较为系统的研究进展。对离线折衷排序我们在发展各种ε-约束变异方法的前提下对重新排序、双代理排序、分批排序等模型中的多个典型的折衷排序问题给出了强多项式时间算法，部分结果突破了文献中的弱多项式时间算法；在双指标排序的计算复杂性研究中我们解决了多个历史遗留问题并对以最大延迟作为基准目标的排序反问题以及具有工件最大允许错位的重新排序模型进行了系统的研究；在折衷排序的在线算法和近似算法方面，我们研究了“时间表长与加权完工时间和的折衷”、“时间表长与最大延迟的折衷”、“总完工时间和与拒绝费用的正组合”、“加工与送货两阶段排序”等排序问题，得到了性能良好的在线算法和近似算法。受本项目资助共发表SCI期刊学术论文40篇。代表性成果如下：（1）对最小化工件错位总和与时间表长的 Pareto 最优重新排序，创建了跳跃式ε-约束变异方法，并由此得到求解全部 Pareto 最优点的强多项式时间算法；（2）对工件具有到达时间并可中断最小化两个代理的最大延迟的Pareto 最优排序问题，建立了Pareto 最优排序的EDD顺序下的Pmtn-List排序结构，然后利用工件轮廓的构思确定出所有的Pareto 最优点，进而在多项式时间求解了所研究的问题；（3）证明了单机最小化总提前及延误量问题以及GDD假设下单机最小化工件加权总误工问题的强 NP-困难性，从而解决了两个上世纪80年代遗留至今的计算复杂性问题；（4）提出并研究了折衷在线排序，并对单机同时最小化时间表长与加权完工时间和的折衷在线排序问题给出了具有最好可能的Trade-off竞争比的在线算法。