在线和离线折衷排序研究

项目名称： 在线和离线折衷排序研究

项目编号： No.11271338

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 原晋江

作者单位： 郑州大学

项目金额： 60万元

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

中文关键词： 折衷排序；在线排序；Pareto 最优点；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.

英文关键词： Trade-off scheduling；Online scheduling；Pareto optimal points；Trade-off curve；Competitive ratio