工件可拒绝的折衷排序和在线排序

Scheduling with rejection is a new-type scheduling in recent years which can be widely applied in make-to-order production system. In the last ten years, it has received more and more attentions from many foreign and domestic researchers and a large number of results in this topic were obtained. However, in almost all literature, the objective is to minimize the sum of processing costs of the accepted jobs and rejection penalty of the rejected jobs, and all jobs arrive in the off-line setting or in the on-line over-list setting. In this project, we focus on the trade-off scheduling problems for all Pareto optimal solutions or the on-line over-time scheduling problems. To solve these problems, we must provide some new methods and new skills to design some optimal algorithms, approximation algorithms and on-line algorithms.

工件可拒绝排序是近年来出现的一种新型排序，它在订货生产系统中有着广泛的应用。近10年来已经吸引了众多国内外研究人员的关注，大量的相关结果也不断涌现。然而，绝大多数文献考虑的目标都是最小化接收工件的加工费用与拒绝工件的拒绝费用之和，并且工件是离线到达或者是按列表在线到达的。本项目主要集中于研究目标为求解所有Pareto最优解的折衷排序，以及工件按时间在线到达的在线排序。为了求解这类问题，需要提出一些新的方法和技巧用以设计一些最优算法、近似算法和在线算法。

工件可拒绝排序是近年来出现的一种新型排序，它在订货生产系统中有着广泛的应用。近10年来已经吸引了众多国内外研究人员的关注。但是，仍然有很多的未解问题有待解决。为了求解这一类问题，我们必须提出一些新的方法和技巧用以设计一些最优算法、近似算法和在线算法。本项目的主要研究内容包括：(1) 复杂性分类；(2)近似算法和在线算法设计；(3) 多(双)目标情形。目前，在本项目的资助下，我们已经有6篇论文在国际SCI期刊上发表或者已接收待发表，主要成果如下：.1. 对最小化最大流程的工件可拒绝排序问题，当机器数量是固定的常数时(甚至等于1)，我们证明了该问题在一般意义下是NP-困难的并且给出了一个全多项式时间近似方案；当机器数量不确定时，我们证明了该问题是强NP-困难的并给出了一个有效的近似算法。该结果被国际SCI期刊《Journal of Systems Science and Complexity》接收待发表。2. 对两台机器流水作业排序问题，我们证明了三种特殊的离线问题也是NP-困难的，这改进了前人的结果。对在线问题，我们给出了最好可能的竞争比为2的在线算法。该结果被国际SCI期刊《Journal of Combinatorial Optimization》接收待发表。3. 对两台机器自由作业排序问题，我们证明该问题是NP-困难的，并给出了有效的近似算法。这解决了前人提出的一个未解问题。该结果被国际SCI期刊《OR Spectrum》接收待发表。4. 对最小化最大提前的单机排序问题，我们证明了该问题是NP-困难的并给出了动态规划算法和有效的近似算法。该结果被国际SCI期刊《Journal of Combinatorial Optimization》接收待发表。