双目标排序的近似算法

Bicriteria scheduling is an important research direction in scheduling theory, which received rapid development in recent years, and obtained much attention by the researchers. This project studies the two-agent scheduling problems with assignable due dates and two-agent scheduling problems with job rejection. For the related problems, we present complexity analysis, and for the NP-hard problems, based on totally new theoretical tools, we design efficient polynomial-time approximation algorithms. In the aspect of the expression of the achievements，we will provide related research results for bicriteria approximation algorithms and establish fundamental theoretical framework.

双目标排序的近似算法是排序领域的重要研究方向，近年来发展迅速，得到国内外同行的广泛关注。本项目研究工期可分配的两个代理排序问题和带有拒绝费用的两个代理排序问题。我们对相关问题进行计算复杂性分析、并对NP-困难问题在全新的理论工具的基础上寻求有效的多项式时间近似算法。在成果表现方面，对双目标排序的近似算法给出相关的研究结果，并建立基本的理论构架。

双目标排序和在线排序是排序理论中的重要研究部分，其中包括模型的建立， 问题的复杂性，NP-困难性证明，多项式时间算法的设计，近似算法的设计，在线算法的设计。我们研究了带有禁用区间的双代理标排序问题、两个工件类的双代理排序问题、工期可分配的双代理排序问题、工件可拒绝的双代理排序问题、在线排序问题等。受本项目资助共发表学术论文15篇。其中代表性成果如下：（1）对机器具有禁用区间的两个代理排序问题给出了多项式时间算法和拟多项式时间算法。(2) 对于具有提前费用的两个代理排序问题给出了多项式时间算法。（3）对具有两个工件类的两个代理排序问题给出了多项式时间算法或拟多项式时间算法。 (4) 研究了单机上具有相同工期分配和累积退化的排序问题。（5）研究了单机上带有拒绝和退化维修活动的排序。（6）对工件具有退化效应且需要考虑工件运输的在线排序问题给出了相应的在线算法。（7）对于等长工件在m台容量无限的平行批处理机上加工的在线排序问题设计出了一个最好可能的在线算法。(8) 对带有友好释放时间在线排序问题, 给出最好的在线算法。