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

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.